Примеры рекурсивных функций

Question

Можно ли предложить примеры программирования, иллюстрирующие рекурсивные функции? Есть обычные старые лошади, такие как серия Фибоначчи и Башни Ханоя, но ничего кроме них было бы интересно.

Answer 1

Мой личный фаворит Binary Search

Edit: Кроме того, дерево-ВТП. Например, прокрутка файловой структуры папки.

Answer 2

• Факториал
• обходе дерева в глубину (в файловой системе, в игровом пространстве, или любом другом случае)

Answer 3

Написать recursive descent parser!

Answer 4

Implementing Graphs от Guido van Rossum имеет некоторые рекурсивные функции в Python для поиска путей между двумя узлами в графах.

Answer 5

This illustration на английском языке, а не фактический языка программирования, но полезно для объяснения процесса в нетехнических образом:

 
A child couldn't sleep, so her mother told a story about a little frog, 
    who couldn't sleep, so the frog's mother told a story about a little bear, 
    who couldn't sleep, so bear's mother told a story about a little weasel 
     ...who fell asleep. 
    ...and the little bear fell asleep; 
    ...and the little frog fell asleep; 
...and the child fell asleep. 

Answer 6

Моего любимого рода, Merge Sort

(Favorite, так как я может запомнить алгоритм и, это не так уж плохо по производительности)

Answer 7

Как насчет того, чтобы обратить вспять строку?

void rev(string s) { 
    if (!s.empty()) { 
    rev(s[1..s.length]); 
    } 
    print(s[0]); 
} 

Понимание этого помогает понять рекурсию.

Answer 8

Еще несколько «обычных-подозреваемых» являются Quicksort и слиянием

Answer 9

Вот пример я разместил на этом сайте некоторое время назад для рекурсивной генерации дерева меню: Recursive Example

Answer 10

Как о чем processing lists, как :

• карта (и andmap, ormap)
• складки (foldl, foldr)
• фильтр
• и т.д ...

Answer 11

волосатый пример, который я знаю Кнута Man or Boy Test. Как и рекурсия, он использует функции Алгола определения вложенных функций (замыканий), ссылок на функции и дуализма констант/функций (вызов по имени).

Answer 12

interpreter design pattern - довольно хороший пример, потому что многие люди не указывают рекурсию. Код примера, указанный в статье Википедии, хорошо иллюстрирует, как это можно применить.Тем не менее, гораздо более простой подход, который до сих пор реализует паттерн интерпретатор является ToString функция для вложенных списков:

class List { 
    public List(params object[] items) { 
     foreach (object o in items) 
      this.Add(o); 
    } 

    // Most of the implementation omitted … 
    public override string ToString() { 
     var ret = new StringBuilder(); 
     ret.Append("("); 
     foreach (object o in this) { 
      ret.Append(o); 
      ret.Append(" "); 
     } 
     ret.Append(")"); 
     return ret.ToString(); 
    } 
} 

var lst = new List(1, 2, new List(3, 4), new List(new List(5), 6), 7); 
Console.WriteLine(lst); 
// yields: 
// (1 2 (3 4) ((5) 6) 7) 

(Да, я знаю, что это не так легко определить шаблон интерпретатора в приведенном выше коде, если вы ожидаете, функция Eval ... но на самом деле шаблон интерпретатора не говорит нам о том, что называется функцией или даже о том, что она делает, и книга GoF явно перечисляет вышеприведенное в качестве примера упомянутого шаблона.)

Answer 13

Из мира математики, имеется the Ackermann function:

Ackermann(m, n) 
{ 
    if(m==0) 
    return n+1; 
    else if(m>0 && n==0) 
    return Ackermann(m-1, 1); 
    else if(m>0 && n>0) 
    return Ackermann(m-1, Ackermann(m, n-1)); 
    else 
    throw exception; //not defined for negative m or n 
} 

Он всегда заканчивается, но он дает очень большие результаты даже для очень маленьких входов. Аккерманн (4, 2), например, возвращает 2 - 3.

Answer 14

Как насчет тестирования строки для палиндрома?

bool isPalindrome(char* s, int len) 
{ 
    if(len < 2) 
    return TRUE; 
    else 
    return s[0] == s[len-1] && isPalindrome(&s[1], len-2); 
} 

Конечно, вы могли бы сделать это с помощью петли более эффективно.

Answer 15

На мой взгляд, рекурсия имеет смысл знать, но большинство решений, которые могут использовать рекурсию, также могут быть выполнены с использованием итерации, а итерация намного эффективнее.

Что тут сказать, рекурсивный способ найти элемент управления в вложенном дереве (например, ASP.NET или Winforms):

public Control FindControl(Control startControl, string id) 
{ 
     if (startControl.Id == id) 
      return startControl 

     if (startControl.Children.Count > 0) 
     { 
      foreach (Control c in startControl.Children) 
      { 
       return FindControl(c, id); 
      } 
     } 
     return null; 
} 

Answer 16

Перевести индекс столбца таблицы с именем столбца.

Это сложнее, чем кажется, потому что столбцы таблицы не обрабатывают цифру «0» правильно. Например, если вы берете A-Z в качестве цифр при увеличении с Z до AA, это будет похоже на переход от 9 до 11 или от 9 до 00 вместо 10 (в зависимости от того, является ли A 1 или 0). Даже Microsoft Support example ошибочно делает что-то большее, чем AAA!

Рекурсивное решение работает, потому что вы можете возвращаться на эти новые границы. Эта реализация в VB.Net, и относится к первой колонке («A») в качестве индекса 1.

Function ColumnName(ByVal index As Integer) As String 
    Static chars() As Char = {"A"c, "B"c, "C"c, "D"c, "E"c, "F"c, "G"c, "H"c, "I"c, "J"c, "K"c, "L"c, "M"c, "N"c, "O"c, "P"c, "Q"c, "R"c, "S"c, "T"c, "U"c, "V"c, "W"c, "X"c, "Y"c, "Z"c} 

    index -= 1 'adjust index so it matches 0-indexed array rather than 1-indexed column' 

    Dim quotient As Integer = index \ 26 'normal/operator rounds. \ does integer division' 
    If quotient > 0 Then 
     Return ColumnName(quotient) & chars(index Mod 26) 
    Else 
     Return chars(index Mod 26) 
    End If 
End Function 

Answer 17

Для того, чтобы understandrecursion, нужно сначала понять recursion.

Answer 18

Когда-то давно, и не так давно, ученики начальной школы учились рекурсии с использованием логотипа и черепаховой графики. http://en.wikipedia.org/wiki/Turtle_graphics

Рекурсия также отлично подходит для решения головоломок путем исчерпывающего судебного разбирательства. Существует своего рода головоломка, называемая «заполнить» (Google it), в которой вы получаете сетку, такую ​​как кроссворд, и слова, но никаких подсказок, никаких нумерованных квадратов. Однажды я написал программу, использующую рекурсию для издателя головоломок, чтобы решить головоломки, чтобы убедиться, что известное решение было уникальным.

Answer 19

Рекурсивные функции отлично подходит для работы с recursively defined datatypes:

• натуральное число равно нулю или преемником другого натурального числа
• список является пустой список или другой список с элементом перед
• дерево является узлом с некоторыми данными и ноль или более других поддеревьев

т.д.

Answer 20

Как уже говорилось, многие примеры канонической рекурсии являются академическими.

Некоторые практические применения я Ve сталкивался в прошлом, являются:

1 - Перемещение по структуре дерева, такие как файловая система или реестр

2 - Манипулирование управления контейнера, который может содержать другие элементы управления контейнерными (например, панели или групповые ящики)

Answer 21

Реальный пример - проблема с калькуляцией стоимости материалов.

Предположим, у нас есть производственная компания, которая выпускает конечные продукты. Каждый продукт описывается списком его частей и временем, необходимым для сборки этих частей. Например, мы производим ручные электрические сверла из корпуса, двигателя, патрона, переключателя и шнура, и это занимает 5 минут.

Учитывая стандартную стоимость рабочей силы в минуту, сколько стоит производство каждого из наших продуктов?

О, кстати, некоторые части (например, шнур) приобретаются, поэтому мы знаем их стоимость напрямую.

Но мы фактически сами изготавливаем некоторые части. Мы делаем двигатель из корпуса, статора, ротора, вала и подшипников, и это занимает 15 минут.

И мы делаем статор и ротор из штамповок и проволоки, ...

Таким образом, определение стоимости готового продукта фактически составляет обхода дерева, которое представляет все целое к списку посещающих части отношений в наших процессах. Это хорошо выражено с помощью рекурсивного алгоритма. Конечно, это можно сделать итеративно, но основная идея смешивается с бухгалтерской книгой «сделай сам», поэтому не так ясно, что происходит.

Answer 22

Вот практический пример из мира файловых систем. Эта утилита рекурсивно подсчитывает файлы в указанной директории. (Я не помню почему, но я на самом деле было необходимости что-то вроде этого давно ...)

public static int countFiles(File f) { 
    if (f.isFile()){ 
     return 1; 
    } 

    // Count children & recurse into subdirs: 
    int count = 0; 
    File[] files = f.listFiles(); 
    for (File fileOrDir : files) { 
     count += countFiles(fileOrDir); 
    } 
    return count; 
} 

(Обратите внимание, что в Java File экземпляр может представлять либо обычный файл или каталог. Это полезность исключает каталоги из подсчета.)

Обычный пример в реальном мире был бы, например, FileUtils.deleteDirectory() из библиотеки Commons IO; см. API doc & source.

Answer 23

Правило большого пальца для рекурсии: «Используйте рекурсию, если и только если на каждой итерации ваша задача разбивается на двух или более подобных задач».

Так что Фибоначчи не является хорошим примером применения рекурсии, в то время как Ханой - хороший.

Таким образом, большинство хороших примеров рекурсии - обход дерева в разных случаях.

Например: график обхода - требование, посетившая узел никогда не будут посещать снова эффективно делает график дерево (дерево представляет собой связный граф без простых циклов)

разделяй и властвуй алгоритмы (быструю сортировку, слияние sort) - части после «деления» составляют дочерние узлы, «победить» формирует ребра от родительского узла до дочерних узлов.