Возможные дубликаты:
Примеры рекурсии реального мира
Примеры рекурсивных функций
Я вижу, что в большинстве учебников по языку программирования учат рекурсию, используя простой пример, который заключается в том, как сгенерировать последовательность фибоначчи, мой вопрос в том, есть ли еще один хороший пример, отличный от генерации последовательности фибоначчи, чтобы объяснить, как работает рекурсия?
Классическим является поиск двоичного дерева:
def findval (node,val):
if node == null:
return null
if node.val = val:
return node
if node.val > val:
return findval (node.left,val)
return findval (node.right,val)
findval (root,thing_to_find)
Это может быть немного более сложным, чем простая формула, но это использование "хлеба и масла" рекурсии, и оно иллюстрирует лучшие места для его использования, когда уровни рекурсии сводятся к минимуму.
Под этим я подразумеваю: вы могли бы добавить два неотрицательных числа с:
def add (a,b):
if b == 0:
return a
return add (a+1,b-1)
но вы, скорее всего, быстро исчерпаете пространство стека для больших чисел (если, конечно, компилятор не оптимизировал верные рекурсии, но вы, вероятно, должны игнорировать это для уровня обучения, о котором вы беспокоитесь).
В других ответах упоминаются различные алгоритмы, которые полностью прекрасны, но если вы хотите немного более "конкретный" пример, вы можете перечислить все файлы в какой-то каталог и его подкаталоги. Иерархическая файловая система является хорошо известным примером рекурсивной (древовидной) структуры, и вы можете показывать поиск по глубине и по ширине с использованием этого конкретного примера.
Моим любимым примером для рекурсии является Towers of Hanoi: Чтобы переместить стопку предметов с полюса A на полюс B, вы перемещаете все выше самый низкий кусок к полюсу, который не является A или B, затем переместите нижнюю часть на B, а затем вы переместите стек, который вы положили на "вспомогательный столб", поверх верхней части. Для первого и третьего шагов вы следуете этой инструкции рекурсивно. См. Ссылку для более подробного объяснения:)
Проверьте palyndrome:
bool recursivePalindrome(std::string str, unsigned int index = 0) {
if (index > str.length()/2) return true;
else if (str[index] == str[str.length()-index-1])
return recursivePalindrome(str, ++index);
else return false;
}
Или на менее серьезной ноте:)
void StackOverflow()
{
StackOverflow();
}
Как насчет поиска факториала.
int GetFactorial(int n )
{
if ( n==0) return 1;
return n*GetFactorial(n-1);
}
Идея состоит в том, что факториал определяется рекурсивно как произведение n и факториала (n-1). И из рекурсивного определения вы получаете свою рекурсию.
Перемещение иерархии папок дерева каталогов как части файловой системы является хорошим примером реального мира. Посмотрите на это сообщение SO для примера С++:
Почему у меня возникают проблемы с рекурсивным удалением каталогов?
Сортировка слияния - довольно хороший пример алгоритма, который легче читать и понимать при реализации рекурсивно.
Здесь немного высокоуровневой псевдокодной версии Merge Sort:
def merge_sort(List sortlist)
if sortlist.length <= 1 return sortlist
split sortlist into leftlist and rightlist
return merge(merge_sort(leftlist), merge_sort(rightlist))
def merge(List leftlist, List rightlist)
while(leftlist and rightlist not empty)
compare leftlist.first to rightlist.first
pop lowest value off its list and append to resultlist
append any remains of leftlist onto resultlist
append any remains of rightlist onto resultlist
return resultlist
Итеративная версия этого будет намного сложнее писать и визуализировать.
================
Пример, который я использую для демонстрации простой мощности рекурсии, - это рекурсивная обработка файлов в дереве каталогов.
Вот пример С#
void ProcessFiles( string sFolder )
{
foreach( string f in Directory.GetFiles( sFolder ) )
{
DoSomethingTo( f );
}
foreach( string d in Directory.GetDirectories( sFolder ))
{
ProcessFiles( d );
}
}
Существует несколько примеров:
T(n) = Sum(T(i)*T(n-i)) for all 1 <= i < n
A(x,y) = y+1 (if x = 0)
A(x,y) = A(x-1,1) (if y=0)
A(x,y) = A(x-1, A(x,y-1)) otherwise.
Поиск проблемы гамильтонового пути
факториала.
и вы можете увидеть wiki страницу для других ссылок.
Хорошие примеры рекурсии часто связаны с случаями, когда базовая структура данных или сама проблема рекурсивно: деревья, графики, алгоритмы, использующие подход "разделять" и "побеждать" (как и многие виды), парсер рекурсивных грамматик (например, общие арифметические выражения) найти стратегию для шахматных игр двух игроков (для простого примера Nim), комбинаторных проблем и т.д.
Попробуйте рекурсивный двоичный поиск: http://www.fredosaurus.com/notes-cpp/algorithms/searching/rbinarysearch.html
Или рекурсивный быстрый сортировка: http://www.dreamincode.net/forums/topic/72311-recursive-quicksort-algorithm/
Это всего лишь два небольших примера в огромном мире рекурсивных функций.
Оценка арифметических выражений может быть выполнена рекурсивно или итеративно с использованием стека. Может быть весьма поучительно сравнить два подхода.
Моя свекровь сделала вводный курс на C. У нее была проблема с домашним заданием, что-то вроде:
У вас есть металлический брусок (длина len), а число (n), чтобы разрезать металл на различный длина. Вы хотите максимизировать количество используемого металла, но не может превышать общую длину.
Инструктор предложил повторить от 1 до 2 ** n в двоичном формате, исключая порядок, если его соответствующий бит равен 0, и включает в себя порядок, если его бит равен 1, при этом отслеживая максимальную сумму. Его предложение будет выполняться в полиномиальное время.
Другое решение существует с использованием рекурсивного алгоритма ранца. Вы можете выполнить итерацию от len до 1 и выполнить поиск в глубину для рекурсивного поиска суммы длин.
Другая область, в которой я использовал рекурсию, была кодировка Хаффмана (для сжатия строки), но это не имеет интуитивного чувства проблемы с рюкзаком.
Рекурсия - замечательная концепция, которая радикально отличается. С наилучшими пожеланиями в обучении или обучении.
Функция Аккермана:
/* undefined if m and n are negative */
uint32 ackermann( uint32 m, uint32 n )
{
if( m < 0 && n < 0 ) { exit(1); /* invalid m and n */ }
if( m == 0 ){ return n + 1; }
if( m > 0 && n == 0 ){ return ackermann( m - 1, 1 ); }
if( m > 0 && n > 0 ){ return ackermann( m - 1, ackermann(m, n - 1) ); }
}
Многочисленные сравнения m > 0 являются избыточными (и могут быть упрощены). Однако оставить их как есть, показывает стандартное определение функции Аккермана.
Но не нужно заходить так далеко от математического края, чтобы найти интересные рекурсивные функции, отличные от чисел Фибонаци.
У вас есть функция наибольшего общего знаменателя (GDC), быстрая сортировка и всегда типичный алгоритм бинарного поиска.
Все, что имеет иерархию. Например, список всех сотрудников ниже вашего босса.
Рекурсия находит свои основы в математической индукции и должна преподаваться как таковая.
Определение функций по индукции может быть ясно раскрыто при обработке списка. Есть много вещей, которые можно сказать о fold, например.
Затем перейдите к деревьям.
Это не С++, очевидно, но понятие звучит:
PHP рекурсивно перемещает вложенные многомерные массивы:
public function recurse_me($collection) {
foreach ($collection as $value) {
if (is_array($value)) {
$this->recurse_me($value);
} else {
// process value.
}
}
}
Я помню, что я понял рекурсию, написав программу, которая ищет word ladders. В данном словаре.
Академический пример - факториал
!
calculum. В реальной жизни вы получаете математические библиотеки.
Существуют алгоритмы сортировки, которые полагаются на рекурсию.
И тогда есть двоичный поиск, который реализуется с рекурсией.
Сортировка кучи также является хорошим примером. Вы можете прочитать об этом в "Введение в алгоритмы" Кормена, Ривеста и других. Отличная книга, надеюсь, вы найдете там много интересного.
Множество операций с структурами типа связанных типов node может быть рекурсивным. Другие упомянули BST, но если вы не хотите объяснять, что это такое, рассмотрите поиск наивысшего значения в линейном, несортированном списке:
int MaxValue(Node node)
{
if (node == null)
return 0;
if (node.Next == null)
return node.Value;
int maxNext = MaxValue(node.Next);
return node.Value > maxNext ? node.Value : maxNext;
}
Списки (в данном случае связанные списки) очень легко объясняются в реальных условиях; ваша аудитория даже не нуждается в программировании. Вы можете просто описать его как группу несортированных ящиков или список чисел.