Что такое рекурсия и когда я должен использовать ее?

Существует много хороших объяснений рекурсия в этом потоке, этот ответ о том, почему Вы не должны использовать его на большинстве языков.* В большинстве основных реализаций императивного языка (т.е. каждой основной реализации C, C++, Основного, Python, Ruby, Java и C#) , повторение весьма предпочтительно для рекурсии.

Для наблюдения, почему идите через шаги что вышеупомянутое использование языков для вызывания функции:

1. пространство вырезано на стек для аргументов функции и локальных переменных
2. , аргументы функции копируются в это новое пространство
3. переходы управления к функции
4. выполнения кода функции
5. , результат функции копируется в возвращаемое значение
6. , стек перематывается к его предыдущим переходам управления положением
7. назад туда, где функция была вызвана

, Выполнение всех этих шагов занимает время, обычно немного больше, чем это берет для итерации через цикл. Однако настоящая проблема находится на шаге № 1. Когда много программ запускаются, они выделяют единственный блок памяти для их стека, и когда у них заканчивается та память (часто, но не всегда из-за рекурсии), программа отказывает из-за переполнение стека .

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

существует техника, которую реализаторы языка могут использовать названный оптимизация последнего вызова , который может устранить некоторые классы переполнения стека. Помещать кратко: если выражение возврата функции является просто результатом вызова функции, то Вы не должны добавлять новый уровень на стек, можно снова использовать текущий для вызванной функции. К сожалению, немногим реализациям императивного языка встроили оптимизацию последнего вызова.

* я люблю рекурсию. Мой любимый статический язык не использует циклы вообще, рекурсия является единственным способом неоднократно делать что-то. Я просто не думаю, что рекурсия обычно является хорошей идеей на языках, которые не настраиваются для нее.

** путем Mario, типичное название Вашей функции ArrangeString является "соединением", и я был бы удивлен, не имеет ли Ваш предпочтительный язык уже реализации его.

Простой пример рекурсии на английском языке.

A child couldn't sleep, so her mother told her a story about a little frog,
    who couldn't sleep, so the frog's mother told her a story about a little bear,
         who couldn't sleep, so the bear's mother told her 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.

Вы хотите использовать его каждый раз, когда у Вас есть древовидная структура. Это очень полезно в чтении XML.

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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

function checkRecursively(Node n) {
    n.Checked = True;
    foreach ( n.Children as child ) {
        checkRecursively(child);
    }
}

, Таким образом, Вы видите, что checkRecursively сначала проверяет узел, который он передается, затем называет себя для каждого из детей того узла.

действительно необходимо быть немного осторожными с рекурсией. При вхождении в бесконечный рекурсивный цикл Вы получите Исключение из-за переполнения стека :)

я не могу думать о причине, почему люди не должны использовать его, в надлежащих случаях. Это полезно при некоторых обстоятельствах, а не при других.

я думаю, что, потому что это - интересная техника, некоторые кодеры, возможно, заканчивают тем, что использовали его чаще, чем они должны без реального выравнивания. Это дало рекурсии дурную славу в некоторых кругах.

1. функция А, которая называет себя
2. , Когда функция может быть (легко) разложена на простую операцию плюс та же функция на некоторой меньшей части проблемы. Я должен сказать, скорее что это делает это хорошим кандидатом на рекурсию.
3. Они делают!

каноническим примером является факториал, который похож:

int fact(int a) 
{
  if(a==1)
    return 1;

  return a*fact(a-1);
}

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

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

каноническим примером является стандартная программа для генерации Факториала n. Факториал n вычисляется путем умножения всех чисел между 1 и n. Повторяющееся решение в C# похоже на это:

public int Fact(int n)
{
  int fact = 1;

  for( int i = 2; i <= n; i++)
  {
    fact = fact * i;
  }

  return fact;
}

нет ничего удивляющего о повторяющемся решении, и оно должно иметь смысл любому знакомому с C#.

рекурсивное решение найдено путем распознавания, что энный Факториал является n * Факт (n-1). Или, другими словами, если Вы знаете то, что конкретное Факториальное число - Вы, может вычислить следующий. Вот рекурсивное решение в C#:

public int FactRec(int n)
{
  if( n < 2 )
  {
    return 1;
  }

  return n * FactRec( n - 1 );
}

первая часть этой функции известна как Основной Случай (или иногда Пункт охраны) и - то, что препятствует тому, чтобы алгоритм работал навсегда. Это просто возвращает значение 1 каждый раз, когда функция вызвана со значением 1 или меньше. Вторая часть более интересна и известна как Рекурсивный Шаг . Здесь мы называем тот же метод с немного измененным параметром (мы постепенно уменьшаем его 1), и затем умножьте результат с нашей копией n.

, Когда сначала встреченный это может довольно сбивать с толку, таким образом, это поучительно, чтобы исследовать, как это работает, когда выполнено. Предположите, что мы называем FactRec (5). Мы вводим стандартную программу, не взяты основным случаем и таким образом, мы заканчиваем как это:

// In FactRec(5)
return 5 * FactRec( 5 - 1 );

// which is
return 5 * FactRec(4);

, Если мы повторно вводим метод с параметром 4, в нас снова не заходят защитный пункт и таким образом, мы заканчиваем в:

// In FactRec(4)
return 4 * FactRec(3);

, Если мы заменяем этим возвращаемым значением в возвращаемое значение выше, мы добираемся

// In FactRec(5)
return 5 * (4 * FactRec(3));

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

return 5 * (4 * FactRec(3));
return 5 * (4 * (3 * FactRec(2)));
return 5 * (4 * (3 * (2 * FactRec(1))));
return 5 * (4 * (3 * (2 * (1))));

, Что заключительная замена происходит, когда основной случай инициирован. В этой точке у нас есть простая algrebraic формула для решения, который приравнивается непосредственно к определению Факториалов во-первых.

Это поучительно, чтобы отметить, что каждый вызов в метод приводит или к основному инициированному случаю или к вызову к тому же методу, где параметры ближе к основному случаю (часто названный рекурсивным вызовом). Если дело обстоит не так затем метод будет работать навсегда.

Рекурсия работает лучше всего с тем, что мне нравится называть "фрактальными проблемами", где Вы имеете дело с большой вещью, это сделано из уменьшенных вариантов той большой вещи, каждый из которых является ровным уменьшенным вариантом большой вещи и так далее. Если Вы когда-нибудь должны пересекать или перерывать что-то как дерево или вложили идентичные структуры, у Вас есть проблема, которая могла бы быть хорошим кандидатом на рекурсию.

Люди избегают рекурсии по ряду причин:

1. Большинство людей (самостоятельно включенный) сокращает зубы программирования на процедурном или объектно-ориентированном программировании в противоположность функциональному программированию. Таким людям итерационный подход (обычно использующий циклы) чувствует себя более естественным.

2. Тем из нас, кто сократил наши зубы программирования на процедурном или объектно-ориентированном программировании, часто говорили избежать рекурсии, потому что это подвержено ошибкам.

3. Нам часто говорят, что рекурсия является медленной. Вызов и возврат из стандартной программы неоднократно включают большое продвижение стека и сование, которое медленнее, чем цикличное выполнение. Я думаю, что некоторые языки обрабатывают это лучше, чем другие, и те языки наиболее вероятны не они, где доминирующая парадигма является процедурной или объектно-ориентированной.

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

Рекурсивно вызывать решенную проблему: ничего не сделайте, Вы сделаны.
Для рекурсивного вызова открытую проблему: сделайте следующий шаг, затем рекурсивно вызовите остальных.

Вот простой пример: сколько элементов в наборе. (существуют лучшие способы считать вещи, но это - хороший простой рекурсивный пример.)

Первый, нам нужны два правила:

1. , если множество пусто, количество объектов в наборе является нулем (понятное дело!).
2. , если множество не пусто, количество один плюс количество объектов в наборе после того, как один объект удален.

предположим у Вас есть набор как это: [x x x]. давайте рассчитаем сколько объектов, там.

1. набор [x x x], который не пуст, таким образом, мы применяем правило 2. количество объектов один плюс количество объектов в [x x] (т.е. мы удалили объект).
2. набор [x x], таким образом, мы применяем правило 2 снова: один + количество объектов в [x].
3. набор [x], который все еще соответствует правилу 2: один + количество объектов в [].
4. Теперь набор [], который соответствует правилу 1: количество является нулем!
5. Теперь, когда мы знаем ответ на шаге 4 (0), мы можем решить шаг 3 (1 + 0)
6. Аналогично, теперь, когда мы знаем ответ на шаге 3 (1), мы можем решить шаг 2 (1 + 1)
7. И наконец теперь, когда мы знаем ответ на шаге 2 (2), мы можем решить шаг 1 (1 + 2) и вложить количество объектов [x x x], который равняется 3. Ура!

Мы можем представить это как:

count of [x x x] = 1 + count of [x x]
                 = 1 + (1 + count of [x])
                 = 1 + (1 + (1 + count of []))
                 = 1 + (1 + (1 + 0)))
                 = 1 + (1 + (1))
                 = 1 + (2)
                 = 3

При применении рекурсивного решения, у Вас обычно есть по крайней мере 2 правила:

• основание, простой случай, который указывает, что происходит, когда Вы "израсходовали" все свои данные. Это обычно - некоторое изменение, "если Вы вне данных для обработки, ответ X"
• рекурсивное правило, которое указывает, что происходит, если у Вас все еще есть данные. Это обычно - некоторое правило, в котором говорится, "делают что-то, чтобы сделать Ваш набор данных меньшим, и повторно применить Ваши правила к меньшему набору данных".

, Если мы переводим вышеупомянутое для псевдокодирования, мы добираемся:

numberOfItems(set)
    if set is empty
        return 0
    else
        remove 1 item from set
        return 1 + numberOfItems(set)

существуют намного более полезные примеры (пересекающий дерево, например), который я уверен, что другие люди покроют.

На простом английском языке рекурсия означает повторение чего-то снова и снова.

Одним из примеров программирования является вызов функции внутри себя.

Посмотрите на следующий пример вычисления факториала числа:

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}

Рекурсия применительно к программированию - это, по сути, вызов функции изнутри ее собственного определения (внутри себя) с другими параметрами для выполнения задачи.

эй, извините, если мое мнение с кем-то согласуется, я просто пытаюсь объяснить рекурсию простым английским языком.

предположим, что у вас есть три менеджера - Джек, Джон и Морган. Джек управляет 2 программистами, Джон - 3, а Морган - 5. вы собираетесь дать каждому менеджеру по 300 долларов и хотите чтобы узнать, сколько это будет стоить. Ответ очевиден - но что, если двое сотрудников Моргана также являются менеджерами?

ЗДЕСЬ идет рекурсия. вы начинаете с начала иерархия. летняя стоимость 0 $. вы начинаете с Джека, затем проверьте, есть ли у него менеджеры в качестве сотрудников. если вы обнаружите, что кто-то из них есть, проверьте, есть ли у них менеджеры в качестве сотрудников и так далее. Добавляйте 300 долларов к летним расходам каждый раз, когда найдете менеджера. Когда вы закончите с Джеком, идите к Джону, его сотрудникам, а затем к Моргану.

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

Рекурсия - это дерево с ветвями и листьями, называемыми родителями и потомками соответственно. Когда вы используете алгоритм рекурсии, вы более или менее сознательно строите дерево из данных.

Любой алгоритм демонстрирует структурную рекурсию для типа данных, если в основном состоит из оператора switch с регистром для каждого случая типа данных.

например, когда вы работаете с типом

  tree = null 
       | leaf(value:integer) 
       | node(left: tree, right:tree)

, структурный рекурсивный алгоритм будет иметь форму

 function computeSomething(x : tree) =
   if x is null: base case
   if x is leaf: do something with x.value
   if x is node: do something with x.left,
                 do something with x.right,
                 combine the results

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

Теперь, когда вы смотрите на целые числа (ну, натуральные числа), как они определены с использованием аксиом Пеано

 integer = 0 | succ(integer)

, вы видите, что структурный рекурсивный алгоритм для целых чисел выглядит так

 function computeSomething(x : integer) =
   if x is 0 : base case
   if x is succ(prev) : do something with prev

: слишком хорошо известная факториальная функция является наиболее тривиальным примером этой формы.

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

Например, чтобы вычислить факториал для числа X , можно представить его как X раз больше факториала X-1 . Таким образом, метод "выполняет рекурсию", чтобы найти факториал X-1 , а затем умножает полученное значение на X , чтобы дать окончательный ответ. Конечно, чтобы найти факториал X-1 , он сначала вычислит факториал X-2 и так далее. Базовый случай - когда X равен 0 или 1, и в этом случае он знает, что нужно вернуть 1 , поскольку 0! = 1! = 1 .

Что ж, у вас есть довольно приличное определение. И в Википедии тоже есть хорошее определение. Так что я добавлю вам еще одно (возможно, худшее) определение.

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

Рекурсия - это выражение, прямо или косвенно ссылающееся на себя.

Рассмотрим рекурсивные акронимы в качестве простого примера:

• GNU означает GNU не Unix
• PHP означает PHP: Препроцессор гипертекста
• YAML означает для YAML Ain't Markup Language
• WINE означает Wine Is Not an Emulator
• VISA означает Visa International Service Association

Дополнительные примеры в Википедии

функция вызывает сама себя или использует собственное определение.

На простом английском: Предположим, что вы можете сделать 3 вещи:

1. Взять одно яблоко
2. Записать счетные метки
3. Посчитать счетные метки

Перед вами на столе много яблок, и вы хотите узнать, сколько их всего.

start
  Is the table empty?
  yes: Count the tally marks and cheer like it's your birthday!
  no:  Take 1 apple and put it aside
       Write down a tally mark
       goto start

Процесс повторения одного и того же действия до тех пор, пока вы не закончите, называется рекурсией.

Надеюсь, это тот ответ "простым английским языком", который вы искали!

Рекурсивная функция - это функция, которая содержит вызов самой себя. Рекурсивная структура - это структура, которая содержит экземпляр самой себя. Вы можете объединить два как рекурсивный класс. Ключевой частью рекурсивного элемента является то, что он содержит экземпляр / вызов самого себя.

Рассмотрим два зеркала, обращенных друг к другу. Мы видели аккуратный эффект бесконечности, который они производят. Каждое отражение является экземпляром зеркала, которое содержится в другом экземпляре зеркала и т. Д. Зеркало, содержащее собственное отражение, является рекурсией.

двоичное дерево поиска является хорошим примером программирования рекурсии. Структура рекурсивна, и каждый узел содержит 2 экземпляра узла. Функции для работы с двоичным деревом поиска также рекурсивны.

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

Самый простой пример - хвостовая рекурсия, когда последняя строка функции является вызовом самой себя:

int FloorByTen(int num)
{
    if (num % 10 == 0)
        return num;
    else
        return FloorByTen(num-1);
}

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

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

Вы можете нарисовать один из них очень просто с помощью рекурсии, где стек вызовов ветвится в трех направлениях:

private void BuildVertices(double x, double y, double len)
{
    if (len > 0.002)
    {
        mesh.Positions.Add(new Point3D(x, y + len, -len));
        mesh.Positions.Add(new Point3D(x - len, y - len, -len));
        mesh.Positions.Add(new Point3D(x + len, y - len, -len));
        len *= 0.5;
        BuildVertices(x, y + len, len);
        BuildVertices(x - len, y - len, len);
        BuildVertices(x + len, y - len, len);
    }
}

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

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

Заключение

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

Рекурсия - это решение проблемы с помощью функции, которая вызывает сама себя. Хорошим примером этого является функция факториала. Факториал - это математическая задача, в которой факториал 5, например, равен 5 * 4 * 3 * 2 * 1. Эта функция решает ее в C# для положительных целых чисел (не тестировалось - может быть ошибка).

public int Factorial(int n)
{
    if (n <= 1)
        return 1;

    return n * Factorial(n - 1);
}

Рассмотрим старую, хорошо известную задачу:

В математике наибольший общий делитель (gcd) ... двух или более ненулевых целых чисел - это наибольшее положительное целое число, которое делит эти числа без остатка.

Определение gcd удивительно просто:

где mod - оператор modulo (то есть остаток после деления целого числа).

В английском языке это определение означает, что наибольший общий делитель любого числа и нуля является этим числом, а наибольший общий делитель двух чисел m и n - это наибольший общий делитель n и остаток после деления m на n.

Если вы хотите узнать, почему это работает, смотрите статью Википедии о евклидовом алгоритме.

В качестве примера вычислим gcd(10, 8). Каждый шаг равен предыдущему:

1. gcd(10, 8)
2. gcd(10, 10 mod 8)
3. gcd(8, 2)
4. gcd(8, 8 mod 2)
5. gcd(2, 0)
6. 2

На первом шаге 8 не равно нулю, поэтому применима вторая часть определения. 10 mod 8 = 2, потому что 8 входит в 10 один раз с остатком 2. На третьем шаге снова применяется вторая часть, но на этот раз 8 mod 2 = 0, потому что 2 делит 8 без остатка. На шаге 5 второй аргумент равен 0, поэтому ответ - 2.

Вы заметили, что gcd появляется как слева, так и справа от знака равенства? Математик сказал бы, что это определение рекурсивно, потому что выражение, которое вы определяете, повторяется внутри своего определения.

Рекурсивные определения, как правило, элегантны. Например, рекурсивное определение суммы списка имеет вид

sum l =
    if empty(l)
        return 0
    else
        return head(l) + sum(tail(l))

где head - первый элемент списка, а tail - остальная часть списка. Обратите внимание, что sum повторяется внутри своего определения в конце.

Возможно, вместо этого вы предпочтете максимальное значение в списке:

max l =
    if empty(l)
        error
    elsif length(l) = 1
        return head(l)
    else
        tailmax = max(tail(l))
        if head(l) > tailmax
            return head(l)
        else
            return tailmax

Вы можете определить умножение неотрицательных целых чисел рекурсивно, чтобы превратить его в серию сложений:

a * b =
    if b = 0
        return 0
    else
        return a + (a * (b - 1))

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

Merge sort имеет прекрасное рекурсивное определение:

sort(l) =
    if empty(l) or length(l) = 1
        return l
    else
        (left,right) = split l
        return merge(sort(left), sort(right))

Рекурсивные определения встречаются повсюду, если знать, что искать. Обратите внимание, что все эти определения имеют очень простые базовые случаи, например, , gcd(m, 0) = m. Рекурсивные случаи разрушают проблему, чтобы добраться до простых ответов.

Теперь, понимая это, вы можете оценить другие алгоритмы в статье Википедии о рекурсии!

Пример: рекурсивное определение лестницы: Лестница состоит из: - одной ступени и лестницы (рекурсия) - или только одной ступени (завершение)

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

Мне также нравится обсуждение Стивом МакКоннеллом рекурсии в Code Complete, где он критикует примеры, используемые в книгах по информатике по рекурсии.

Не используйте рекурсию для факториалов или чисел Фибоначчи

Одна проблема с учебниками по информатике состоит в том, что они представляют глупые примеры рекурсии. Типичными примерами являются вычисление факториала или вычисление последовательности Фибоначчи. Рекурсия - это мощный инструмент, и очень глупо использовать его в любом из этих случаев. Если бы программист, который работал у меня, использовал рекурсию для вычисления факториала, я бы нанял кого-нибудь другого.

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

РЕДАКТИРОВАТЬ: Это не было копом ответа Дава - я не видел этого ответа, когда размещал это

Рекурсия - это процесс, когда метод вызывает сам себя для выполнения определенной задачи. Это уменьшает избыточность кода. Большинство рекурсивных функций или методов должны иметь условие для прерывания рекурсивного вызова, т.е. прекращения вызова самого себя при выполнении условия - это предотвращает создание бесконечного цикла. Не все функции подходят для рекурсивного использования.

«Если у меня есть молоток, сделай все похожим на гвоздь».

Рекурсия - это стратегия решения огромных проблем, где на каждом шаге просто «превращайте две мелочи в одна большая вещь "каждый раз одним и тем же молотком.

Пример

Предположим, ваш стол завален беспорядочным беспорядком из 1024 листов. Как с помощью рекурсии сделать одну аккуратную чистую стопку бумаг из беспорядка?

1. Divide: Разложите все листы так, чтобы у вас был только один лист в каждой «стопке».
2. Завоевание:
   2. Обойдите, кладя каждый лист поверх другого листа. Теперь у вас есть стопки по 2.
   3. Обойдите, кладя каждую 2 стопки поверх другой 2 стопки. Теперь у вас есть стеки по 4.
   4. Обойдите, кладя каждую 4 стека поверх другой 4 стека. Теперь у вас есть стопки по 8.
   5. ... снова и снова ...
   6. Теперь у вас есть одна огромная стопка из 1024 листов!

Обратите внимание, что это довольно интуитивно понятно, не считая подсчета всего (что не является строго необходимым). На самом деле вы не можете полностью опуститься до стопки по 1 листу, но вы можете, и это все равно будет работать. Важной частью является молоток: руками вы всегда можете положить одну стопку на другую, чтобы получилась большая стопка, и не имеет значения (в пределах разумного), насколько велика каждая стопка.

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

Например, возьмите факториал:

factorial(6) = 6*5*4*3*2*1

Но легко увидеть факториал (6) также:

6 * factorial(5) = 6*(5*4*3*2*1).

Итак, в общем:

factorial(n) = n*factorial(n-1)

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

В этом примере мы просто создаем особый случай, определяя факториал (1) = 1.

Теперь мы видим его снизу вверх:

factorial(6) = 6*factorial(5)
                   = 6*5*factorial(4)
                   = 6*5*4*factorial(3) = 6*5*4*3*factorial(2) = 6*5*4*3*2*factorial(1) = 6*5*4*3*2*1

Поскольку мы определили факториал (1) = 1, мы достигаем "Нижний".

Вообще говоря, рекурсивные процедуры состоят из двух частей:

1) Рекурсивная часть, которая определяет некоторую процедуру в терминах новых входных данных в сочетании с тем, что вы «уже сделали» с помощью той же процедуры. (например, factorial (n) = n * factorial (n-1) )

2) Базовая часть, которая гарантирует, что процесс не повторяется вечно, давая ему место для начала ( т.е. factorial (1) = 1 )

Поначалу может быть немного запутанно, но просто посмотрите на кучу примеров, и все должно получиться. Если вы хотите глубже понять эту концепцию, изучите математическую индукцию. Также имейте в виду, что некоторые языки оптимизированы для рекурсивных вызовов, а другие - нет. Довольно легко сделать безумно медленные рекурсивные функции, если вы не будете осторожны, но есть также методы, чтобы сделать их работоспособными в большинстве случаев.

Надеюсь, это поможет ...

В самом общем смысле информатики , рекурсия - это функция, которая вызывает сама себя. Предположим, у вас есть структура связанного списка:

struct Node {
    Node* next;
};

И вы хотите узнать, какова длина связанного списка, вы можете сделать это с помощью рекурсии:

int length(const Node* list) {
    if (!list->next) {
        return 1;
    } else {
        return 1 + length(list->next);
    }
}

(Это, конечно, можно сделать и с помощью цикла for, но это полезно в качестве иллюстрации концепции)

Я создал рекурсивную функцию для конкатенации списка строк с разделителем между ними. Я использую его главным образом для создания SQL-выражений путем передачи списка полей как' объекты ' и' comma+space' как разделитель. Вот функция (Она использует некоторого Разработчика Borland собственные типы данных, но может быть адаптирована для установки любой другой среде):

String ArrangeString(TStringList* items, int position, String separator)
{
  String result;

  result = items->Strings[position];

  if (position <= items->Count)
    result += separator + ArrangeString(items, position + 1, separator);

  return result;
}

я называю это этим путем:

String columnsList;
columnsList = ArrangeString(columns, 0, ", ");

Предполагают, что у Вас есть массив, названный' поля ' с этими данными в нем: ' albumName', ' releaseDate', ' маркировал '. Затем Вы вызываете функцию:

ArrangeString(fields, 0, ", ");

, Поскольку функция начинает работать, переменная' , результат ' получает значение положения 0 массива, который является' albumName'.

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

ArrangeString(fields, 1, ", ");

Это продолжает повторяться, создавая груду LIFO, пока это не достигает точки, где положение, имеющий дело с, ЯВЛЯЕТСЯ последним, таким образом, функция возвращает только объект на той позиции по списку, не конкатенируя больше. Затем груда связывается назад.

Получил его? Если Вы не делаете, у меня есть другой способ объяснить это.: o)

Mario, я не понимаю, почему Вы использовали рекурсию для того примера.. Почему не просто цикл посредством каждой записи? Что-то вроде этого:

String ArrangeString(TStringList* items, String separator)
{
    String result = items->Strings[0];

    for (int position=1; position < items->count; position++) {
        result += separator + items->Strings[position];
    }

    return result;
}

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