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

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

Итак, вопрос:

  1. Что такое рекурсия?
  2. Когда я буду использовать рекурсию?
  3. Почему люди не используют рекурсию?
6.08.2008 02:29:51
И, возможно, это поможет: stackoverflow.com/questions/126756/…
kennytm 4.05.2010 11:28:05
Это может помочь понять концепцию: перейдите по ссылке, приведенной во втором комментарии к вопросу на этой странице, и сделайте то, что говорят комментарии: stackoverflow.com/questions/3021/…
dtmland 21.12.2015 19:27:01
30 ОТВЕТОВ
  1. Функция, которая вызывает себя
  2. Когда функция может быть (легко) разложена на простую операцию плюс та же функция в некоторой меньшей части проблемы. Скорее я должен сказать, что это делает его хорошим кандидатом для рекурсии.
  3. Они делают!

Канонический пример - факториал, который выглядит следующим образом:

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

  return a*fact(a-1);
}

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

8
6.08.2008 02:39:08

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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

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

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

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

6
6.08.2008 02:44:53

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

Канонический пример - это процедура для генерации факториала 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 * Fact (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, нас снова не остановит выражение guard, и в результате мы получим:

// 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))));

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

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

27
7.02.2016 14:18:11
Хорошее объяснение, но я думаю, что важно отметить, что это просто хвостовая рекурсия и не дает преимущества перед итеративным решением. Это примерно столько же кода, и он будет работать медленнее из-за накладных расходов на вызов функции.
Steve Wortham 5.06.2011 13:41:24
@SteveWortham: это не хвостовая рекурсия. На рекурсивном шаге результат FactRec()должен быть умножен nдо возврата.
rvighne 19.07.2016 19:53:19

Я создал рекурсивную функцию для объединения списка строк с разделителем между ними. Я использую его в основном для создания выражений SQL, передавая список полей в качестве « элементов » и « запятая + пробел » в качестве разделителя. Вот функция (она использует некоторые собственные типы данных Borland Builder, но может быть адаптирована для любой другой среды):

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, ", ");

Представьте, что у вас есть массив с именем ' fields ' с этими данными внутри: ' albumName ', ' releaseDate ', ' labelId '. Затем вы вызываете функцию:

ArrangeString(fields, 0, ", ");

Когда функция начинает работать, переменная « result » получает значение позиции 0 массива, которая равна « albumName ».

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

ArrangeString(fields, 1, ", ");

Он продолжает повторяться, создавая стопку LIFO, пока не достигнет точки, где рассматриваемая позиция является последней, поэтому функция возвращает только элемент с этой позиции в списке, больше не конкатенируя. Затем куча соединяется в обратном направлении.

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

0
6.08.2008 03:00:16

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

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

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

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

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

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

4
6.08.2008 03:12:15

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

Во-первых, нам нужно два правила:

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

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

  1. набор [xxx] не является пустым, поэтому мы применяем правило 2. количество элементов равно одному плюс количество элементов в [xx] (т.е. мы удалили элемент).
  2. набор [xx], поэтому мы снова применяем правило 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) и получить количество элементов в [xxx], которое равно 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)

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

4
20.11.2016 00:23:09

Я использую рекурсию. Какое это имеет отношение к получению степени CS ... (кстати, я не знаю)

Общие использования я нашел:

  1. sitemaps - проходить через файловую систему, начиная с корня документа
  2. пауки - просматривают веб-сайт, чтобы найти адрес электронной почты, ссылки и т. д.
  3. ?
0
6.08.2008 03:13:35

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

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;
}

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

0
7.02.2016 14:19:38

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

2
6.08.2008 03:32:35

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

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

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

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

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

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

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

** Кстати, Марио, типичное имя для вашей функции ArrangeString - «join», и я был бы удивлен, если бы у вашего языка выбора его еще не было.

86
26.12.2016 01:59:29
Приятно видеть объяснение накладных расходов на рекурсию. Я затронул и это в своем ответе. Но для меня большая сила рекурсии - это то, что вы можете сделать со стеком вызовов. Вы можете написать сжатый алгоритм с рекурсией, который будет многократно ветвиться, что позволит вам с легкостью выполнять такие операции, как обход иерархий (отношения родитель / потомок). Смотрите мой ответ для примера.
Steve Wortham 5.06.2011 13:49:49
Очень разочарован, когда нашел лучший ответ на вопрос «Что такое рекурсия и когда я должен ее использовать?» на самом деле не отвечайте ни на один из них, не берите в голову чрезвычайно предвзятое предупреждение против рекурсии, несмотря на его широкое использование в большинстве языков, которые вы упомянули (нет ничего особенно неправильного в том, что вы сказали, но вы, кажется, преувеличиваете проблему и недооцениваете полезность).
Dukeling 25.06.2015 16:42:42
Вы, вероятно, правы @Dukeling. Для контекста, когда я писал этот ответ, было уже много хороших объяснений рекурсии, и я написал это, намереваясь быть дополнением к этой информации, а не верхним ответом. На практике, когда мне нужно пройтись по дереву или обработать любую другую вложенную структуру данных, я обычно обращаюсь к рекурсии, и мне еще предстоит столкнуться с переполнением стека моего собственного создания в дикой природе.
Peter Burns 25.06.2015 17:01:42

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

1
21.08.2008 13:18:19

На самом деле лучшее рекурсивное решение для факториала должно быть:

int factorial_accumulate(int n, int accum) {
    return (n < 2 ? accum : factorial_accumulate(n - 1, n * accum));
}

int factorial(int n) {
    return factorial_accumulate(n, 1);
}

Потому что эта версия Tail Recursive

0
7.02.2016 14:20:49

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

struct Node {
    Node* next;
};

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

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

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

49
16.07.2010 09:07:46
@Christopher: Это хороший, простой пример рекурсии. В частности, это пример хвостовой рекурсии. Однако, как заявил Андреас, его можно легко переписать (более эффективно) с помощью цикла for. Как я объясняю в своем ответе, есть реальное использование для рекурсии.
Steve Wortham 4.05.2010 22:13:11
вам действительно нужно еще заявление здесь?
Adrien Be 28.11.2012 18:15:30
Нет, это только для ясности.
Andreas Brinck 28.11.2012 20:41:19
@ SteveWortham: это не хвостовая рекурсия, как написано; length(list->next)все еще нужно вернуться, чтобы length(list)последний мог добавить 1 к результату. Если бы он был написан так, чтобы передать всю длину, только тогда мы могли бы забыть, что звонящий существовал. Как int length(const Node* list, int count=0) { return (!list) ? count : length(list->next, count + 1); }.
cHao 2.12.2013 17:43:36

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

1
4.05.2010 11:25:53

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

Например, чтобы вычислить факториал для числа X, можно представить его как X times the factorial of X-1. Таким образом, метод «рекурсивно» находит факториал X-1, а затем умножает все, что получил, Xчтобы дать окончательный ответ. Конечно, чтобы найти факториал X-1, сначала нужно вычислить факториал X-2и так далее. Базовый случай будет, когда X0 или 1, и в этом случае он знает, что возвращать 1с тех пор 0! = 1! = 1.

9
4.05.2010 11:26:02
Я думаю, что вы ссылаетесь не на рекурсию, а на принцип разработки алгоритма <a href=" en.wikipedia.org/wiki/… и Conquer</a>. Посмотрите, например, на <a href = " en.wikipedia. org / wiki / Ackermann_function "> функция Аккермана </a>.
Gabriel Ščerbák 4.05.2010 11:35:11
Нет, я не имею в виду D & C. D & C подразумевает, что существует 2 или более подзадач, рекурсия сама по себе не существует (например, приведенный здесь факторный пример не D & C - он полностью линейный). D & C - это, по сути, подмножество рекурсии.
Amber 4.05.2010 11:41:11
Цитируется из той статьи, которую вы связали: «Алгоритм« разделяй и властвуй »работает путем рекурсивного разбиения задачи на две или более подзадачи одного и того же (или связанного) типа»,
Amber 4.05.2010 11:50:22
Я не думаю, что это хорошее объяснение, так как, строго говоря, рекурсия вообще не должна решать проблему. Вы можете просто позвонить себе (и переполниться).
UK-AL 4.05.2010 16:27:38
Я использую ваше объяснение в статье, которую я пишу для PHP Master, хотя я не могу приписать это вам. Надеюсь, ты не возражаешь.
frostymarvelous 30.05.2013 12:31:27

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

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

3
4.05.2010 11:27:09

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

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

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

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

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

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

4
4.05.2010 14:53:29
Большая часть причин, по которым факториалы или последовательности Фибоначчи используются в качестве примеров, заключается в том, что они являются общими элементами, которые определены рекурсивно, и, таким образом, они естественным образом поддаются примерам рекурсии для их вычисления - даже если это не самый лучший метод. с точки зрения CS.
Amber 4.05.2010 11:32:00
Я согласен - я только что обнаружил, когда читал книгу, что было интересно поднять этот вопрос в середине раздела о рекурсии
Robben_Ford_Fan_boy 4.05.2010 11:36:09

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

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

    return n * Factorial(n - 1);
}
12
4.05.2010 12:46:51

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

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

пример

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

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

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

1
4.05.2010 11:54:34
Вы описываете разделяй и властвуй. Хотя это пример рекурсии, он ни в коем случае не единственный.
Konrad Rudolph 4.05.2010 12:02:53
Это нормально. Я не пытаюсь описать [мир рекурсии] [1] в предложении здесь. Я хочу интуитивное объяснение. [1]: facebook.com/pages/Recursion-Fairy/269711978049
Andres Jaan Tack 4.05.2010 17:45:53

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

Рассмотрим рекурсивные сокращения как простой пример:

  • GNU означает GNU, а не Unix
  • PHP расшифровывается как PHP: Hypertext Preprocessor
  • YAML расшифровывается как YAML, а не язык разметки
  • WINE означает вино не эмулятор
  • VISA выступает за международную ассоциацию обслуживания Visa

Больше примеров в Википедии

5
5.05.2010 03:35:09

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

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

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

в C # у вас будет что-то вроде этого:

private void findlinks(string URL, int reccursiveCycleNumb)    {
   if (reccursiveCycleNumb == 0)
        {
            return;
        }

        //recursive action here
        foreach (LinkItem i in LinkFinder.Find(URL))
        {
            //see what links are being caught...
            lblResults.Text += i.Href + "<BR>";

            findlinks(i.Href, reccursiveCycleNumb - 1);
        }

        reccursiveCycleNumb -= reccursiveCycleNumb;
}
1
7.02.2016 14:19:59

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

1
4.05.2010 12:42:48

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

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

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

public int fact(int n)
{
    if (n==0) return 1;
    else return n*fact(n-1)
}
1
4.05.2010 12:56:27
На простом английском языке повторение чего-либо снова и снова называется итерацией.
toon81 26.02.2012 18:17:24

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

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

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

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

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

1
4.05.2010 12:50:05

Простым английским: предположим, что вы можете сделать 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
4.05.2010 13:09:33
Подожди, у меня на столе много меток, и теперь я хочу знать, сколько есть меток. Могу ли я как-то использовать яблоки для этого?
Christoffer Hammarström 4.05.2010 14:18:55
Если вы возьмете яблоко с земли (когда вы положите его туда во время процесса) и положите его на стол каждый раз, когда вы царапаете одну метку в списке, пока не останется меток, я уверен, что вы в конечном итоге количество яблок на столе будет равно количеству подсчитанных вами отметок. Теперь просто посчитайте эти яблоки для мгновенного успеха! (примечание: этот процесс уже не рекурсия, а бесконечный цикл)
Bastiaan Linders 4.05.2010 15:10:52

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

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

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

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

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

Так в общем:

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

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

В этом примере мы просто создаем особый случай, определяя factorial (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)

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

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

4
4.05.2010 13:30:28

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

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

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

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

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

введите описание изображения здесь

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

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);
    }
}

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

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

Заключение

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

46
9.03.2013 00:31:37

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

3
4.05.2010 13:34:56

Любой алгоритм демонстрирует структурную рекурсию для типа данных, если в основном состоит из оператора 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

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

1
4.05.2010 13:53:14

Рассмотрим старую, хорошо известную проблему :

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

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

определение gcd

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

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

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

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

  1. жк (10, 8)
  2. жк (10, 10 мод 8)
  3. жк (8, 2)
  4. жк (8, 8 мод 2)
  5. жк (2, 0)
  6. 2

На первом этапе 8 не равно нулю, поэтому применяется вторая часть определения. 10 mod 8 = 2, потому что 8 входит в 10 один раз с остатком 2. На шаге 3 вторая часть применяется снова, но на этот раз 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))

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

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

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. Рекурсивные случаи сводят на нет проблему, чтобы перейти к простым ответам.

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

9
10.05.2010 14:23:06