需要計算對以下函式的遞回呼叫量：
def fb(n, d):
if n in d:
return d[n]
else:
ans = fb(n-1, d) fb(n-2, d)
d[n] = ans
return ans
d = {1:1, 2:2}
print(fb(8, d))
print(d)
現在我理解了這個函式，以及本質上發生了什么，我只是不能用我的大腦來手動（手動）計算遞回的數量。我可以通過查看'd'來計算代碼或jsut的遞回，但我無法理解為什么最后只有13個遞回呼叫。
在我的腦海中發生了以下情況：ans 進行了 2 次遞回呼叫（n = 7 和 n = 6），這兩個呼叫中的每一個都再進行兩次呼叫，等等，直到所有這些呼叫以 2 或 1 的 n 結束。
但是，如果我查看代碼，并且每次運行函式時都列印 n，我會得到以下輸出：
def fb(n, d):
if n in d:
return d[n]
else:
print(n)
ans = fb(n-1, d) fb(n-2, d)
d[n] = ans
return ans
d = {1:1, 2:2}
print(fb(8, d))
輸出：
8
7
6
5
4
3
32
現在我知道答案是 13，每個數字上對函式 (2 * 6) 的 2 次呼叫 最后一次回傳 ans 的呼叫。但我的問題是，這在內部是如何運作的，我怎樣才能在我的腦海中復制這個思維程序。
感謝您的時間。
uj5u.com熱心網友回復：
這可能有助于您理解它：
def fb(n, d, indent):
if n in d:
print(indent, n, "old")
return d[n]
else:
print(indent, n, "new")
indent2 = indent " "
ans = fb(n-1, d, indent2) fb(n-2, d, indent2)
d[n] = ans
return ans
d = {1:1, 2:2}
print(fb(8, d, ""))
我以兩種不同的方式擴充了該函式：（1）我顯示所有呼叫，無論值是舊的還是新的，以及（2）我根據呼叫深度縮進。結果是：
8 new
7 new
6 new
5 new
4 new
3 new
2 old
1 old
2 old
3 old
4 old
5 old
6 old
34
正如你所看到的，它從一個遞回呼叫鏈開始n-1，獲取新值，直到它達到 2。此時，它是一個舊值，所以它立即回傳。
然后呼叫者使用n-2(ie 1) 進行遞回呼叫。這是第一次n-2執行呼叫。當然，它也是一個舊值，所以它會立即回傳。然后呼叫者將兩者相加，存盤結果（對于 3），然后回傳。這是第一次有新病例回傳。
然后它只是重復，但現在所有的n-2電話都是舊電話。當它到達頂層時，將 7 和 6 的結果相加得到 8 的值，然后回傳給頂層呼叫者，結果為 34。
uj5u.com熱心網友回復：
在我的腦海中發生了以下情況：ans 進行了 2 次遞回呼叫（n = 7 和 n = 6），這兩個呼叫中的每一個都再進行兩次呼叫，等等，直到所有這些呼叫以 2 或 1 的 n 結束。
您需要對這里的邏輯更加嚴格。首先ans是一個變數。所以說“ans進行2次遞回呼叫”是無稽之談。此外，遞回呼叫所在的行位于陳述句else塊內if，因此您需要評估 的條件if以確定遞回呼叫是否發生。
所以讓我們更徹底地分析一下fib(7)。由于7不是字典中的鍵，我們遞回呼叫fib(6). 這又會呼叫fib(5)等等，直到我們到達fib(2). 讓我們用縮進來表示每個遞回呼叫：
fib(7)
fib(6)
fib(5)
fib(4)
fib(3)
fib(2)
現在我們到達了一個if條件是True因為字典有2一個鍵。所以并fib(2)回傳2。讓我們注意，與->
fib(7)
fib(6)
fib(5)
fib(4)
fib(3)
fib(2) -> 2
現在fib(3)呼叫fib(n - 2)which is fib(1)。并fib(1)回傳1。我們只需添加適當的縮進級別：
fib(7)
fib(6)
fib(5)
fib(4)
fib(3)
fib(2) -> 2
fib(1) -> 1
現在fib(3)將結果添加2 1到字典并回傳：
fib(7)
fib(6)
fib(5)
fib(4)
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
現在我們處于fib(4)呼叫fib(2)和回傳的級別2：
fib(7)
fib(6)
fib(5)
fib(4)
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
fib(2) -> 2
現在fib(4)回傳3 2：
fib(7)
fib(6)
fib(5)
fib(4) -> 5
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
fib(2) -> 2
現在我們回到fib(5)呼叫fib(n - 2)or的呼叫fib(3)：
fib(7)
fib(6)
fib(5)
fib(4) -> 5
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
fib(2) -> 2
fib(3)
但是我們已經呼叫fib(3)了它的值并將其存盤在字典中。所以這會立即回傳，無需任何額外的遞回呼叫：
fib(7)
fib(6)
fib(5)
fib(4) -> 5
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
fib(2) -> 2
fib(3) -> 3
現在fib(5)回傳5 3：
fib(7)
fib(6)
fib(5) -> 8
fib(4) -> 5
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
fib(2) -> 2
fib(3) -> 3
現在我們回到fib(6)which calls fib(4)。同樣，我們已經計算過了，它的結果會立即回傳：
fib(7)
fib(6)
fib(5) -> 8
fib(4) -> 5
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
fib(2) -> 2
fib(3) -> 3
fib(4) -> 5
現在fib(6)回傳5 8：
fib(7)
fib(6) -> 13
fib(5) -> 8
fib(4) -> 5
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
fib(2) -> 2
fib(3) -> 3
fib(4) -> 5
我們又回到了下一個fib(7)電話fib(5)。同樣，我們已經計算并存盤了這個值，所以我們立即回傳：
fib(7)
fib(6) -> 13
fib(5) -> 8
fib(4) -> 5
fib(3) -> 3
fib(2) -> 2
fib(1) -> 1
fib(2) -> 2
fib(3) -> 3
fib(4) -> 5
fib(5) -> 8
最后fib(7)回傳13 8or 21。
如您所見，有11遞回呼叫fib(7). 我讓你做剩下的分析fib(8)。
uj5u.com熱心網友回復：
以下是樹形呼叫（僅顯示 n 的值，其中 n 已經在括號中的 d 中的呼叫）：
8
/ \
7 (6)
/ \
6 (5)
/ \
5 (4)
/ \
4 (3)
/ \
3 (2)
/ \
(2) (1)
如果經過的話，首先是樹的左側，然后你會從右側爬上去。希望它可以幫助您更清楚地看到它（我知道它對我有用！）。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/520635.html
標籤：Python递归