フィボナッチシーケンスの再帰

Question

私はここで起こる処理を理解するための助けが必要です。fib(5)私はフィボナッチ5が8であることを望んでいます。しかし、アルゴリズムを理解しようとする私の脳はそれを言いますない。

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

は今、xは1 fib(1)、最後に再帰を引き起こしif x == 0 or x == 1:条件文です原因：これは私（誤って）はどのように考えるかです。私の論理によれば3 + 1 + 4 + 3になるでしょう。私の間違った論理を修正してください。ここで

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

は何が起こるかを完全に拡張したものです：

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 

あなたがものをカウントした場合、あなたは答えとして8を得ます。 1より大きいすべてのxについては

Answer 2

、fib関数は二回自身を呼び出します。

1. fib(5)がfib(4) + fib(3)
2. なり、(fib(3) + fib(2)) + (fib(2) + fib(1))
3. に展開し、((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + 1)
4. に展開(((fib(1) + fib(0)) + 1) + (1 + 1)) + ((1 + 1) + 1)
に展開
5. は、8までの合計で(((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1)

に拡張されます。