Рекурсия в глубину (Python)

#python #recursion #return

#python #рекурсия #Возврат

Вопрос:

Проверьте следующий код:

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

Согласно комментариям в руководстве SoloLearn по Python (для рекурсии), код работает следующим образом:

 1. fib(4) = fib(3)   fib(2)
2. = (fib(2)   fib(1))   (fib(1)   fib(0))
3. = fib(1)   fib(0)   fib(1)   fib(1)   fib(0)
4. = 1  1   1   1   1
5. = 5

После строки 2 fib(2) должна идти только другая часть fib() функции, верно?
Два fib(1) и один fib(0) соответствуют критериям if части fib() функции. Таким образом, возвращается 1. Мой вопрос в том, почему в 3-й строке fib(1) fib(0) fib(1) fib(1) fib(0) все заменяются на 1, а затем добавляются?

Простите меня за то, что я задаю такой вопрос.

Ответ №1:

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

 fib(4) =                  fib(3)                   fib(2)    
                         /                       /     
fib(4) =        (  fib(2)        fib(1) )   ( fib(1)   fib(0) )    
                  /              |              |        |
fib(4) = ( ( fib(1)   fib(0) )   fib(1) )   ( fib(1)   fib(0) )    
               |        |          |            |        |
fib(4) = ( (   1        1    )     1    )   (   1        1    )    
                     /            |                   /
fib(4) = ( (        2        )     1    )   (        2        )    
                               /                    |
fib(4) = (                  3           )   (        2        )    
                                                /
fib(4) =                                  5

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

 >>> def fib(n, nivel=0):
        if n==0 or n==1:
            print(" "*nivel,"fib(",n,")=1")
            return 1
        else:
            print(" "*nivel,"fib(",n,")")
            result = fib(n-1,nivel 1)   fib(n-2,nivel 1)
            print(" "*nivel,"fib(",n,")=",result)
            return result

>>> fib(4)
 fib( 4 )
  fib( 3 )
   fib( 2 )
    fib( 1 )=1
    fib( 0 )=1
   fib( 2 )= 2
   fib( 1 )=1
  fib( 3 )= 3
  fib( 2 )
   fib( 1 )=1
   fib( 0 )=1
  fib( 2 )= 2
 fib( 4 )= 5
5
>>>

здесь вы можете заметить, что вызовы разрешаются последовательно слева направо и снизу вверх

Ответ №2:

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

 1. fib(4) 
2. = fib(3)   fib(2)
3. = (fib(2)   fib(1))   (fib(1)   fib(0))
4. = ((fib(1)   fib(0))   1)   (1   1)
5. = 1   1   1   2
6. = 5

1. Почему fib(1) из строки 3 заменяется на 1 в строке 4?

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

3. @Ahnaf Потому что, если if предложение в вашей рекурсии! Смотрите Ответ Роберта Колумбии и обратите внимание, что при вызове fib(1) значение аргумента x равно 1.

Ответ №3:

@MorganThrapp правильно. Более конкретно, базовый вариант рекурсивной функции fib :

 if x==0 or x==1:
    return 1

Это предложение запускается при fib(1) fib(0) вызове or . На языке программирования функция вычисляет возвращаемое значение, которое здесь 1 .

В вашем примере fib(4) , fib вызывается пять раз с 1 вводом a или a 0 , и все эти результаты суммируются, и это приводит к вашему окончательному возвращаемому значению 5 , которое возвращается из вашего первоначального вызова fib(4) и немедленно передается в print функцию.