Блог

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

 def fib(x):
  print(x)
  if x == 0 or x == 1:
    return 1
  else: 
    return fib(x-1)  fib(x-2)

print(fib(4))
  

Я получаю эти выходные данные:

 4
3
2
1
0
1
2
1
0
5
  

Но это просто не имеет смысла для меня.

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

Последовательность Фибоначчи — это разностное уравнение

f (x) = f (x-1) f (x-2), f(0)=f (1) = 1

Оператор if запрашивает, является ли ваше значение одним из значений серии по умолчанию, если это не так, то оно должно быть вычислено рекурсией, что выполняется в операторе else.

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

В вашем примере это выглядит так

fib (4) выводит 4, затем вызывает fib (3) и fib (2), сначала он обращается к fib (3)

fib (3) выводит 3, затем вызывает fib (2) и fib (1), сначала он обращается к fib (2)

fib (2) выводит 2, затем вызывает fib (1) и fib (0), сначала он обращается к fib (1)

fib (1) выводит 1, затем возвращает 1

Теперь посещает fib (0), который выводит 0 и возвращает 1

Он поднимается на одну строку и посещает fib (1), который печатает 1 и возвращает 1

Затем он посещает fib (2), печатает 2 и вызывает fib (1) и fib (0), fib (1) печатает 1 и возвращает 1, fib (0) печатает 0 и возвращает 0

И вот ваш вывод. Последняя строка — это ответ

У него должна быть переменная ответа, равная номеру один номер два. Тогда номер один = номер два и номер два = ответ.

Возможно, добавление счетчика глубины помогло бы объяснить:

  def fib(x, depth=0):
     print('t' * depth   str(x))
     if x == 0 or x == 1:
             return 1
     else:
             return fib(x-1, depth 1)   fib(x-2, depth   1)
  

вывод для print(fib(4)) :

 4
        3
                2
                        1
                        0
                1
        2
                1
                0
5
  

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

 4  - Call to fib(4)
3  - fib(4)'s call to fib(4-1)
2  - fib(4-1)'s call to fib(4-1-1)
1  - fib(4-1-1)'s call to fib(4-1-1-1): this returns a value of 1 because x = 1
0  - fib(4-1-1)'s call to fib(4-1-1-2): this returns 1 because x = 0; fib(4-1-1) returns 2 because the two 1s are added together
1  - fib(4-1)'s call to fib(4-1-2): this returns a value of 1 because x = 1; the 1 from this is added to the 2 from fib(4-1-1) to make the result for fib(4-1)
2  - fib(4)'s call to fib(4-2)
1  - fib(4-2)'s call to fib(4-2-1): this returns 1 because x = 1
0  - fib(4-2)'s call to fib(4-2-2): this returns 1 because x = 0; fib(4-2) returns 1 1 = 2; fib(4) returns 5 because fib(4-1) returned 3 and fib(4-2) returned 2
5  - Final result
  

Глядя на операции, всякий раз, когда мы добираемся до return fib(x-1) fib(x-2) инструкции, каждый раз fib(x-1) выполняется первым, потому что порядок операций слева направо, как при чтении.

На компьютерном уровне это расширяет операции примерно так, при этом каждая строка итеративно углубляется:

 fib(4)
fib(4-1)   fib(4-2)
(fib(3-1)   fib(3-2))   fib(4-2)
((fib(2-1)   fib(2-2))   fib(3-2))   fib(4-2)
((fib(1)   fib(0))   fib(3-2))   fib(4-2)
((1 1)   fib(3-2))   fib(4-2)
(2   fib(1))   fib(4-2)
(2 1)   fib(4-2)
3   fib(2)
3   (fib(2-1)   fib(2-2))
3   (fib(1)   fib(0))
3   (1   1)
3   2
5
  

Я сжал несколько частей из соображений экономии места, но, надеюсь, это должно донести суть.