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


14 Answers

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

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.
Question

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

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

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



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

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

  • GNU означает GNU's Un Unix
  • PHP означает PHP: препроцессор гипертекста
  • YAML означает YAML - это не язык разметки
  • Вина означает, что Wine не является эмулятором
  • VISA означает Visa International Service Association

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




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




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

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

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

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



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

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

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

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

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

Вы можете сделать один из них очень просто с рекурсией, где стек вызовов ветвится в 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);
    }
}

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

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

Вывод

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




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

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




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




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

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

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




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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

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

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

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




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




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

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

    return n * Factorial(n - 1);
}



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

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

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




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

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

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 )

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

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




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

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




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.) Люди используют рекурсию только тогда, когда очень сложно писать итеративный код. Например, методы обхода дерева, такие как preorder, postorder, могут быть сделаны итеративными и рекурсивными. Но обычно мы используем рекурсивную из-за своей простоты.




Related