Рекурсия: за кулисами

Question

Хотя известно, что рекурсия - это «метод, который вызывает себя», я склонен задаваться вопросом, что на самом деле происходит. Возьмем классический факториальный пример:

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

факт (5);

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

http://postimg.org/image/4yjalakcb/

Почему функция рекурсии, как это? Какой аспект компьютера заставляет его работать через себя назад так? Что происходит за кулисами?

Будучи студентом, я чувствую, что рекурсия, которую мы учим, является мелкой и общей. Я хочу, чтобы отличное сообщество помогло мне понять это на уровне самой машины. Спасибо!

Answer 1

Вот это краткий обзор того, что происходит, когда вы вызываете метод:

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

Здесь вы можете узнать больше о фреймах - JVM Spec - Frames.

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

fact(5) 
    5 * fact(4) 
    4 * fact(3) 
     3 * fact(2) 
     2 * fact(1) 
      1 * fact(0) // Base case reached. Stack starts unwinding. 
     2 * 1 * 1 
     3 * 2 * 1 * 1 
    4 * 3 * 2 * 1 * 1 
    5 * 4 * 3 * 2 * 1 * 1 == Final result 

Answer 2

Если вы отслеживаете вызовы функций, вы увидите, как это работает.

E.g.

fact(3) вернет 3 * fact(2). Поэтому java вызовет fact(2).

fact(2) вернет 2 * fact(1). Поэтому java вызовет fact(1).

fact(1) вернет 1 * fact(0). Поэтому java вызовет fact(0).

fact(0) вернет 1.

Затем fact(1) вернет 1 * 1 = 1.

Затем fact(2) вернет 2 * 1 = 2.

Затем fact(3) вернет 3 * 2 = 6.

Java вызывает рекурсивный метод, как и любой другой метод.

Answer 3

Вы, наверное, слышали что-то под названием «Стек» Это то, что используется для метода хранения состояний.

Я считаю, что это также сохраняет вызывающую строку, так что функция может вернуться к нему это звонящему

Так что у вас есть свой вызов рекурсивной функции

- int $input = 5 
- stack.Push L 
- GOTO FOO 
- Label L 

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

- Label FOO 
- int in = $input 
- input = in - 1 
- stack.Push in 
- stack.Push L2 
- goto FOO 
- Label L2 
- in = stack.Pop in 
- output *= in 
- goto stack.POP 

Answer 4

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

1. Определение: факториал 0 равен 1
2. Определение: факториал числа п больше 0 является продуктом этого числа и факториал его предшественника.

Следовательно

5! = 5*4! = 5*4*3! = 5*4*3*2! = 5*4*3*2*1! = 5*4*3*2*1*0! = 5*4*3*2*1*1 = 120 

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

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

Пример: Доказательство по индукции, что квадрат четного числа является кратным 4!

1. Квадрат 0 равен 0, и это кратно 4.
2. Пусть п четное число, квадрат которого N² кратно 4. Тогда (2+n)*(2+n) = 4+2n+2n+n². Это мультипликатор из 4, так как n² по нашему предположению, 4 равно 1 и 2n+2n = 4n также кратно 4, а сумма кратных 4 кратно 4 по закону распределения: 4a + 4b = 4(a+b)
3. Q.E.D. Свойство имеет место для 0 (наш базовый случай) и для (2 + n), если оно выполнено для n. Следовательно, оно выполняется для 2, 4, 6, 8 .... и всех других четных чисел.

(Более легкое доказательство того, что (2a)² = 4*a*a, что кратно 4.)

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

1. Записает вычисление для базового случая.
2. Для не базового случая, мы знаем, как мы можем вычислить результат (например, мы знаем, что n! = n * (n-1)!, поэтому мы написать это только вниз, так как функция Нам нужна одна, мы просто писать!
3. Мы можем заключить, что наша программа будет вычислять правильное значение для базового случая и любого преемника базового случая. Если 678! все же не вычисляет правильный ответ, то это связано с тем, что мы использовали тип данных, такой как int что не подходит для больших чисел (или, если сказать, по-другому, вычисляет все moulo 2^32) и, кроме того, с программным обеспечением, которое настаивает на интерпретации половины доступных чисел как отрицательных.

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

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