遞歸深度（Python）的

檢查下面的代碼：遞歸深度（Python）的

>>> def fib(x): 
... if x == 0 or x == 1: 
...  return 1 
... else: 
...  return fib(x-1) + fib(x-2) 
>>> print(fib(4))

根據在SoloLearn Python的教程（遞歸）的意見，代碼是這樣的：

1. fib(4) = fib(3) + fib(2) 
2. = (fib(2) + fib(1)) + (fib(1) + fib(0)) 
3. = fib(1) + fib(0) + fib(1) + fib(1) + fib(0) 
4. = 1+ 1 + 1 + 1 + 1 
5. = 5

線後2，只有fib(2)應該去掉fib()函數的else部分，對吧？這兩個fib(1)和單個fib(0)符合fib()函數的if部分的標準。所以返回1。我的問題是，爲什麼在第三行中，fib(1) + fib(0) + fib(1) + fib(1) + fib(0)全部被1代替，然後添加？

請原諒我問這樣一個noob問題。

來源

2016-10-11 Ahnaf

因爲所有這些電話的解析爲第一條。 –

@MorganThrapp是正確的。更具體地，遞歸函數fib的基本情況是：當fib(1)或fib(0)稱爲

if x==0 or x==1: 
    return 1

該子句被觸發。在編程說明中，功能評估到它的返回值，這裏是1。

在你的fib(4)例如，fib被稱爲五次無論是1或0輸入，這些結果都加在一起，那結果是從原來的通話回到fib(4)的5最終返回值並立即傳入print函數。

來源

2016-10-11 17:13:43

我相信代碼工作方式的描述是誤導性的，因爲它似乎表明，從一行到下一行都不是每個值都被評估。如果我們用所調用的函數替換所有函數（或返回的值），並在您的示例中加上圓括號，我們會得到以下內容，這可能會幫助您更好地理解該代碼的內部工作原理：

1. fib(4) 
2. = fib(3) + fib(2) 
3. = (fib(2) + fib(1)) + (fib(1) + fib(0)) 
4. = ((fib(1) + fib(0)) + 1) + (1 + 1) 
5. = 1 + 1 + 1 + 2 
6. = 5

來源

2016-10-11 17:20:44 Efferalgan

爲什麼第3行的fib（1）被第4行的1替換？ – Ahnaf

仍然不是這個描述的粉絲，因爲對我來說它意味着某種並行化。現實情況是，第二條線路中的一條電話先被探測到深處，然後再考慮下一條。 – pjs

@Ahnaf因爲如果遞歸中的if語句！請參閱Robert Columbia的回答，並注意當您調用'fib（1）'時，參數'x'的值爲1。 – pjs

這是一個雙遞歸函數，所以它的調用結果用FIB（1）和FIB的基本情況呼叫的樹狀結構（0）

fib(4) =     fib(3)   +  fib(2)  
         / \    / \ 
fib(4) =  ( fib(2) + fib(1)) + (fib(1) + fib(0))  
       / \   |    |  | 
fib(4) = ((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))  
       |  |   |   |  | 
fib(4) = (( 1 + 1 ) + 1 ) + ( 1 + 1 )  
        \ /   |    \ /
fib(4) = ((  2  ) + 1 ) + (  2  )  
         \  /     | 
fib(4) = (     3   ) + (  2  )  
            \   /
fib(4) =         5

你也可以可視化功能的工作通過在正確的地方添加一些印刷品和一個額外的輔助參數來幫助它和其他一些小的變化

>>> def fib(n, nivel=0): 
     if n==0 or n==1: 
      print(" "*nivel,"fib(",n,")=1") 
      return 1 
     else: 
      print(" "*nivel,"fib(",n,")") 
      result = fib(n-1,nivel+1) + fib(n-2,nivel+1) 
      print(" "*nivel,"fib(",n,")=",result) 
      return result 

>>> fib(4) 
fib(4) 
    fib(3) 
    fib(2) 
    fib(1)=1 
    fib(0)=1 
    fib(2)= 2 
    fib(1)=1 
    fib(3)= 3 
    fib(2) 
    fib(1)=1 
    fib(0)=1 
    fib(2)= 2 
fib(4)= 5 
5 
>>>

在這裏你可以看到呼叫按順序解決從左至右和自下而上

來源

2016-10-11 18:27:40 Copperfield

遞歸深度（Python）的

回答

相關問題