Попытка понять функции рекурсии

Question

Я пытаюсь понять концепцию рекурсии, и я просто не могу ее понять. Может кто-нибудь объяснить мне, почему он работает так, как он делает?

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

def Fib(n): 
    if n == 1 or n == 2: 
     return 1 
    return Fib(n-1) + Fib(n-2) 


print Fib(10) 

Я также стараюсь делать это, и ожидаем, что печать 1, но только получить None

def foo(n): 
    if n == 1: 
     return n 
    else: 
     foo(n-1) 
print foo(10) 

EDIT: Я ценю помощь, которая была предоставлена. Я все еще просто не вижу связи, которой нужен мой мозг для AH-HA! Это, скорее всего, связано с ограничением моего опыта, а не с способностью сообщества объяснить мою проблему. Надеюсь, предоставленная информация сможет помочь мне в будущем, когда я вернусь к этому, а также к другим. Спасибо! Я бы отказался от голосов, но у меня нет необходимой репутации, извините!

Answer 1

Вы забыли вернуть значение foo (n-1), которое не будет функцией рекурсии, по умолчанию оно будет возвращать None. Попробуйте так:

def foo(n): 
    if n == 1: 
     return 1 
    else: 
     return foo(n-1) 
print foo(10) 

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

Прежде всего, если n == 1, он возвращает 1, иначе если n = 5, он возвращает foo (4) и foo (4) возвращает foo (3), foo (3) возвращает foo (2), foo (1) return 1. Итак, если вы напечатаете foo (100) или foo (200), это будет 1 навсегда.

Помните, что п должно быть положительным числом, или вы получите это:

RuntimeError: maximum recursion depth exceeded 

Просто распечатайте процесс:

def Fib(n): 
    print "Call number", n 
    if n == 1 or n == 2: 
     return 1 
    print '\n now is', Fib(n-1) + Fib(n-2) 
    return Fib(n-1) + Fib(n-2) 

print Fib(10) 

Может помочь понять PO.

Answer 2

class noisyOne(): 
    def __init__(self, val=1): 
     self.val = val 

    def __add__(self, other): 
     print("**Adding {0} with {1}**".format(self.val, other.val)) 
     return noisyOne(self.val + other.val) 

    def __str__(self): 
     return str(self.val) 



def Fib(n, side): 
    if n == 1 or n == 2: 
     print ("return 1 : called from {0}".format(side)) 
     return noisyOne(1) 
    print("return Fib({0}) + Fib({1}) : called from {2}".format(n-1, n-2, side)) 
    return Fib(n-1, 'Fib({0})'.format(n-1)) + Fib(n-2, 'Fib({0})'.format(n-2)) 


print (Fib(5, 'Fib(5)')) 

# return Fib(4) + Fib(3) : called from Fib(5) :        Fib(5) = Fib(4) + Fib(3) 
# return Fib(3) + Fib(2) : called from Fib(4) : Fib(4) = Fib(3) + Fib(2) -> Fib(5) = Fib(3) + Fib(2) + Fib(3) 
# return Fib(2) + Fib(1) : called from Fib(3) : Fib(3) = Fib(2) + Fib(1) -> Fib(5) = Fib(2) + Fib(1) + Fib(2) + Fib(3) 
# return 1 : called from Fib(2)     : Fib(2) = 1    -> Fib(5) = 1  + Fib(1) + Fib(2) + Fib(3) 
# return 1 : called from Fib(1)     : Fib(1) = 1    -> Fib(5) = 1  + 1  + Fib(2) + Fib(3) 
# **Adding 1 with 1**       : 1 + 1 = 2    -> Fib(5) = 2    + Fib(2) + Fib(3) 
# return 1 : called from Fib(2)     : Fib(2) = 1    -> Fib(5) = 2    + 1  + Fib(3) 
# **Adding 2 with 1**       : 2 + 1 = 3    -> Fib(5) = 3      + Fib(3) 
# return Fib(2) + Fib(1) : called from Fib(3) : Fib(3) = Fib(2) + Fib(1) -> Fib(5) = 3      + Fib(2) + Fib(1) 
# return 1 : called from Fib(2)     : Fib(2) = 1    -> Fib(5) = 3      + 1 + Fib(1) 
# return 1 : called from Fib(1)     : Fib(1) = 1    -> Fib(5) = 3      + 1 + 1 
# **Adding 1 with 1**       : 1 + 1 = 2    -> Fib(5) = 3      + 2 
# **Adding 3 with 2**       : 3 + 2 = 5    -> Fib(5) = 5 
# 5 

Answer 3

Код не будет печатать 1, потому что единственный способ, чтобы функция возвращает 1, когда параметр n либо 1 или 2. Таким образом, когда вы говорите print Fib(10), результат не будет 1.

Вместо этого, управление переходит к следующей строке после инструкции if (return Fib(n-1) + Fib(n-2)), которая снова вызывает Fib, на этот раз с 9 и 8. Результат этих двух вызовов функций будет добавлен и возвращен.

Так что теперь Fib работает с параметром n набора до 9. Так как 9 не равно 1 или 2, опять-таки последняя строка функции Fib будет работать, и Fib будет называться снова для значений 8 и 7.

Это продолжается, пока Fib вызываются с n=1 или n=2, в этом случае Fib возвратит 1. она возвращает 1 в вызывающем, который был экземпляр функции Fib, когда она была вызвана с n=3.Итак, вот что происходит, когда вы звоните Fib с n=3:

3 не 1 или 2, так что опять же, управление переходит к последней строке Fib, return Fib(n-1) + Fib(n-2). На этот раз эта строка вызывает Fib на n-1, которая равна 2, и n-2, что равно 1. Оба этих вызова функций оцениваются в 1, поэтому функция здесь возвращает 1 + 1 своему вызывающему.

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

Answer 4

Я думаю, что ключ, который вам не хватает, это вызов метода, создающий стек . Поэтому подумайте о последовательности вызовов.

Первый звонок с аргументом 10. Итак, вот наш стек вызовов:

__main__ 
Fib(10) 

где наша текущая подпрограмма (метод) находится внизу.

Затем Fib(10) вызывает подпрограмму с аргументом 9, поэтому наш стек вызовов выглядит следующим образом:

__main__ 
Fib(10) 
Fib(9) 

Всю дорогу до Fib(2):

__main__ 
Fib(10) 
Fib(9) 
Fib(8) 
Fib(7) 
Fib(6) 
Fib(5) 
Fib(4) 
Fib(3) 
Fib(2) 

На данный момент, Fib(2) переходит в блок if, и мы нанесли удар по return 1. Теперь вот ключ: return только выталкивает один элемент со стека. Поэтому, когда Fib(2) возвращается, мы вернемся к Fib(3):

__main__ 
Fib(10) 
Fib(9) 
Fib(8) 
Fib(7) 
Fib(6) 
Fib(5) 
Fib(4) 
Fib(3) 

Теперь, когда первый элемент в сумме вычисляется, Fib(3) может перейти на второй элемент в сумме. Это делает его называют Fib(1):

__main__ 
Fib(10) 
Fib(9) 
Fib(8) 
Fib(7) 
Fib(6) 
Fib(5) 
Fib(4) 
Fib(3) 
Fib(1) 

который также немедленно возвращает:

__main__ 
Fib(10) 
Fib(9) 
Fib(8) 
Fib(7) 
Fib(6) 
Fib(5) 
Fib(4) 
Fib(3) 

After Fib(1) возвращается, Fib(3) может, наконец, вернуться:

__main__ 
Fib(10) 
Fib(9) 
Fib(8) 
Fib(7) 
Fib(6) 
Fib(5) 
Fib(4) 

А потом Fib(4) звонки Fib(2), так же, как Fib(3)Fib(1) до:

__main__ 
Fib(10) 
Fib(9) 
Fib(8) 
Fib(7) 
Fib(6) 
Fib(5) 
Fib(4) 
Fib(2) 

и т. Д. И т. Д. Если конечный return вас сбивает с толку, имейте в виду, что return заканчивает текущую подпрограмму и возвращает вас в предыдущий.

На этом втором методе, который вы представляете, вы получаете None, потому что это должно быть return foo(n-1), а не только foo(n-1).