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




пальцах программирование (25)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  return a*fact(a-1);
}

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


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

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

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


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


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

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

    return n * Factorial(n - 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)

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

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

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

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


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

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

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


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

function cmdCheckAllClick {
    checkRecursively(TreeView1.RootNode);
}

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

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

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

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

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


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

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

пример

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

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

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


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

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

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

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

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


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


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

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

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

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

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

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

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

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

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

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


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

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


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


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

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

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


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

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

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

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


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

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

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

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

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

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


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


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

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


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

struct Node {
    Node* next;
};

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

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

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


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


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

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

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

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


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

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

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 и y и возвращает их произведение:

(lambda (x y) (* x y)) 

Он может быть применен как в строке ( 50 ):

((lambda (x y) (* x y)) 5 10)




recursion computer-science