5

ここで行われる処理を理解するのに助けが必要なので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)
4

2 に答える 2

6

これが何が起こるかの完全な拡張です：

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を得る。

于 2012-12-01T10:36:56.153 に答える
5

x1より大きいすべての場合、fib関数はそれ自体を2回呼び出します。

  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. に拡大(((1 + 1) + 1) + (1 + 1)) + ((1 + 1) + 1)

合計すると8。

于 2012-12-01T10:37:00.607 に答える