Фибоначи рекурсии рубин объяснение

Question

Я знаю, как решить эту проблему без рекурсии, но с ним, у меня возникли некоторые трудности understanding..I нужно глубокое объяснение того, как эта линия работает по линии

Вот как проблема сделано:

def fibo(num) 
    if num < 2 
    num 
    else 
    #this is where I get lost on the line below.. 
    fibo(num-1) + fibo(num-2) 
    end 
end 

p fibo(6) 

Answer 1

В последовательности Фибоначчи каждое число в последовательности после первых 2 является суммой предыдущих 2-х номеров:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 

Когда вы пишете рекурсивную функцию, вы явно обрабатываете базовые футляры (в вашем случае fibo(0) и fibo(1)), а затем все что-либо вычисляется, вызывая функцию, которую вы пишете, создавая более поздние результаты operati ng на более ранних.

По определению, после первых двух чисел в последовательности число Фибоначчи представляет собой сумму из двух предыдущих чисел. Другими словами, fibo (n) = fibo (n-1) + fibo (n-2).Это то, что эта строка кода делает:

fibo(num-1) + fibo(num-2) 

Он возвращает значение фибо (NUM), называя себя (то есть «рекурсия») в течение предыдущих 2-х цифр и складывая их вместе.

Поскольку они являются базовыми случаи, мы знаем, фибо (0) будет 0, и фибо (1) будет 1. Давайте посмотрим, как это работает для Фибо (4):

fibo(4) = fibo(3) + fibo(2) 
fibo(4) = (fibo(2) + fibo(1)) + (fibo(1) + fibo(0)) 
     = (fibo(2) + 1 ) + ( 1 + 0 ) 
     = (fibo(2) + 2) 
     = ((fibo(1) + fibo(0)) + 2 
     =  1  + 0  + 2 
     = 3 

Итак, программа в конечном итоге вычисляет правильный результат, разбивая каждое вычисление на более простые проблемы, пока не достигнет базового случая, который определил ответ. Обратите внимание, что это не очень эффективно, так как fibo называется 9 раз для вычисления fibo(4).

Answer 2

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

Для этого конкретного примера взгляните на этот чертеж. Это показывает, что происходит шаг за шагом: http://natashatherobot.com/wp-content/uploads/fibonacci.png

Это сообщение будет полезно прочитать: http://natashatherobot.com/recursion-factorials-fibonacci-ruby/

Answer 3

Если вы знаете кадр стека, вы можете лучше понять рекурсию. Возьмем более простой x = Fib (3), чтобы показать изменение фрейма стека.

(1) При вызове Fib (3) стек Fib функции выглядит так: 3 в качестве параметра: | | | 3 |

(2) когда Fib (3) отправился на линию Fib (n-1) + Fib (n-2), стек выглядит следующим образом: | | | 2 | | 3 |

(3) тогда этот Fib (2) оценивается как Fib (1) + Fib (0), стек выглядит следующим образом: | 1 | | 2 | | 3 |

(4) fib (1) возвращает значение 1, теперь его очередь на поворот (0): | 0 | | 2 | | 3 |

(5) Fib (0) возвращает 0, теперь значение Fib (2) равно 1 и возвращается в Fib (3), | 1 | теперь Fib (3) нужна другая часть, Fib (1), стек выглядит вот так: | 3 |

(6) Fib (1) возвращает 1, теперь Fib (3) оценивается как 2 и возвращается, стек пуст.

Редактировать: почему StackOverflow не поддерживает формат? Altenatively, пожалуйста, обратитесь к этой ссылке: http://en.wikipedia.org/wiki/Recursion_(computer_science)

или этого YouTube видео: https://www.youtube.com/watch?v=k0bb7UYy0pY