Rekursja na sekwencji Fibonacciego

Question

Potrzebuję pomocy w zrozumieniu przetwarzania, które ma miejsce tutaj, więc załóżmy, że dzwonię pod numer fib(5) Chcę, aby fibonacci 5, który jest 8. Ale mój mózg, próbując zrozumieć algorytm mówi, że to jest nie. Jest to, jak i (niesłusznie) pomyśleć:

return fib(4) + fib(3) // Stack frame 1 
return fib(3) + fib(1) // Stack frame 2 

teraz powodować x oznacza 1 fib(1), instrukcja warunkowa if x == 0 or x == 1: powoduje rekursji do końca. Który według mojej logiki stałby się 3 + 1 + 4 + 3. Popraw moją wadliwą logikę.

def fib(x): 
    """assumes x an int >= 0 
     returns Fibonacci of x""" 
    assert type(x) == int and x >= 0 
    if x == 0 or x == 1: 
     return 1 
    else: 
     return fib(x-1) + fib(x-2) 

Answer 1

Oto pełna ekspansja, co się dzieje:

fib(5) expands to fib(4)+fib(3) 
    fib(4) expands to fib(3)+fib(2) 
    fib(3) expands to fib(2)+fib(1) 
     fib(2) expands to fib(1)+fib(0) 
     fib(1) evaluates to 1 
     fib(0) evaluates to 1 
     fib(1) evaluates to 1 
    fib(2) expands to fib(1)+fib(0) 
     fib(1) evaluates to 1 
     fib(0) evaluates to 1 
    fib(3) expands to fib(2)+fib(1) 
    fib(2) expands to fib(1)+fib(0) 
     fib(1) evaluates to 1 
     fib(0) evaluates to 1 
    fib(1) evaluates to 1 

Jeśli zliczane są te, masz 8 jako odpowiedź.

Answer 2

Dla wszystkich x większa niż 1, funkcja fib nazywa się dwukrotnie:

1. fib(5) staje fib(4) + fib(3)
2. i rozszerza się (fib(3) + fib(2)) + (fib(2) + fib(1))
3. i rozszerza się ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
4. rozszerza się (((fib(1) + fib(0)) + 1) + (1 + 1)) + ((1 + 1) + 1)
5. rozwija się do (((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1)

która sumuje się do 8.