遞歸樹斐波納契-Python-

Question

我瞭解遞歸我寫這個（低效率）的第n個Fibonacci數計算器：

def fibonacci(n): 
    if n == 0: 
     return 0 
    elif n == 1: 
     return 1 
    else: 
     return fibonacci(n-1) + fibonacci(n-2) 

我知道，在遞歸，可以繪製所謂的「遞歸樹。當我做這個簡單的二進制生成：

def binary(length, outstr=""): 
    if len(outstr) == length: 
     print(outstr) 
    else: 
     for i in ["0", "1"]: 
      binary(length, outstr + i) 

我能想出這是什麼樹的樣子：

但我想不通的斐波那契數函數的樹！那棵樹會是什麼樣子？

由於提前，

Answer 1

例如斐波納契（4）給出以下遞歸樹，因爲需要兩個函數調用：斐波納契（3）和斐波納契（2），所以每次調用該函數調用其他兩個函數，直到達到退出條件。

  4 
     /\ 
     / \ 
     / \ 
     3  2 
    /\ /\ 
    / \ / \ 
    2  1 1  0 
    /\ 
/ \ 
    1  0