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

Question

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

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

1. Что такое рекурсия?
2. Когда я буду использовать рекурсию?
3. Почему люди не используют рекурсию?

Answer 1

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

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

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

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

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

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

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

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

Answer 2

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

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.

Answer 3

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

struct Node {
    Node* next;
};

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

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

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

Answer 4

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

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

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

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

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

Заключение

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

Answer 5

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

Канонический пример - это процедура для генерации факториала 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))));

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

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

Answer 6

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

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

    return n * Factorial(n - 1);
}

Answer 7

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

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

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

Answer 8

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

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

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

  return a*fact(a-1);
}

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

Answer 9

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

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

Answer 10

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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

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

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

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

Answer 11

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

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

• GNU означает GNU, а не Unix
• PHP расшифровывается как PHP: гипертекстовый препроцессор
• YAML расшифровывается как YAML, а не язык разметки
• Вино означает Вино не эмулятор
• VISA выступает за Международную Сервисную Ассоциацию Visa

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

Answer 12

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

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

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

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

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

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

Answer 13

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

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

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

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

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

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

Answer 14

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

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

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

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

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

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

Answer 15

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

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

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)

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

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

Answer 16

1.) Метод является рекурсивным, если он может вызывать сам себя; либо напрямую:

void f() {
   ... f() ... 
}

или косвенно:

void f() {
    ... g() ...
}

void g() {
   ... f() ...
}

2.) Когда использовать рекурсию

Q: Does using recursion usually make your code faster? 
A: No.
Q: Does using recursion usually use less memory? 
A: No.
Q: Then why use recursion? 
A: It sometimes makes your code much simpler!

3.) Люди используют рекурсию только тогда, когда писать итеративный код очень сложно. Например, методы обхода дерева, такие как предварительный заказ, почтовый заказ, могут быть как итеративными, так и рекурсивными. Но обычно мы используем рекурсивный из-за его простоты.

Answer 17

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

Answer 18

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

Answer 19

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

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

Answer 20

Простым английским: предположим, что вы можете сделать 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

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

Я надеюсь, что это "простой английский" ответ, который вы ищете!

Answer 21

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

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

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

Answer 22

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

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

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

Answer 23

Самым простым определением рекурсии является "самоссылка". Функция, которая ссылается на себя, то есть вызывает сама себя, является рекурсивной. Самая важная вещь, которую нужно иметь в виду, состоит в том, что рекурсивная функция должна иметь "базовый случай", то есть условие, которое, если true, заставляет ее не вызывать себя и, таким образом, завершать рекурсию. В противном случае у вас будет бесконечная рекурсия:

http://cart.kolix.de/wp-content/uploads/2009/12/infinite-recursion.jpg

Answer 24

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

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

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

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

Answer 25

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

Answer 26

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

Допустим, вы хотите найти слово в словаре. У вас есть операция под названием "поиск".

Твой друг говорит: "Я мог бы прямо сейчас выпить немного пудинга!" Вы не знаете, что он имеет в виду, поэтому вы ищите "словарь" в словаре, и он звучит примерно так:

Ложка: существительное - посуда с круглым совком на конце. Ложка: глагол - использовать ложку на чем-нибудь Ложка: глагол - плотно обниматься сзади

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

Обниматься: глагол - прижиматься Посуда: существительное - инструмент, часто пищевая посуда

Привет! Вы знаете, что такое прижимание, и это не имеет ничего общего с пудингом. Вы также знаете, что пудинг - это то, что вы едите, так что теперь это имеет смысл. Твой друг должен хотеть съесть пудинг с ложкой.

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

Традиционный пример, который приводится, это факториал, где 5 факториал равен 1*2*3*4*5 (что равно 120). Базовый случай будет 0 (или 1, в зависимости). Итак, для любого целого числа n вы делаете следующее

n равно 0? в противном случае верните 1, верните n * (факториал n-1)

давайте сделаем это с примером 4 (который мы знаем заранее: 1*2*3*4 = 24).

факториал 4 ... это 0? нет, так что это должно быть 4 * факториал из 3, но что такое факториал из 3? это 3 * факториал 2 факториала 2, 2 * факториал 1 факториала 1, 1 * факториал 0, и мы ЗНАЕМ факториал 0!:-D это 1, то есть факториал определения 1 равен 1 * факториал 0, который был 1... поэтому 1*1 = 1 факториал 2 равен 2 * факториал 1, который был 1... так 2*1 = 2 факториал из 3 равен 3 * факториал из 2, который был 2... так что 3*2 = 6 факториал из 4 (наконец-то!!) равен 4 * факториал из 3, который был 6... 4*6 24

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

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

Answer 27

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

Answer 28

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

Answer 29

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

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

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

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

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

Answer 30

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

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

В качестве примера, вот функция для выполнения алгоритма быстрой сортировки в Scala ( скопировано из записи в Википедии для Scala)

def qsort: List[Int] => List[Int] = {
  case Nil => Nil
  case pivot :: tail =>
    val (smaller, rest) = tail.partition(_ < pivot)
    qsort(smaller) ::: pivot :: qsort(rest)
}

В этом случае условие выхода - пустой список.