關於python遞歸的邏輯困惑？

01-04

是這樣的，我今天在讀《Learning Python (5th Edition)》的第19章(Advanced Function Topics)，涉及到了遞歸的概念（recursive function)
一開始看到示例代碼之後，我的第一感覺是這不太符合思維習慣，甚至不太符合之前所學的syntax：在定義一個function的時候，調用了這個function本身。
為了清晰表述，付上一段代碼（出自L.P. p558）：

def sumtree(L): tot = 0 for x in L: if not isinstance(x, list): tot += x else: tot += sumtree(x) return tot
我的疑問是：在def下的這塊代碼應該都算是在定義sumtree這個函數，那麼我的理解是在函數內調用函數的時候，這個函數不是按照人類思維來說，還未定義完成嗎？這麼想是從程序的語法上進行考慮的。
另外為了避免誤會，在數學上的遞歸式我是理解的，最典型的斐波那契遞歸式等等。
請問，我的想法在哪裡開始不對？或者說，python實現遞歸的機制是怎樣的呢？（暫時看不懂源碼，我主要糾結的地方在於，函數內部調用函數，感覺這個函數還沒定義完）
希望可以解答我的問題，謝謝！

你可以在後面幾行代碼

sumtree2 = sumtree sumtree = None

再運行一下看看會發生什麼

這實際上是一個作用域的問題。數學上的遞歸其實你一樣也不理解。不然你告訴我數學公式里作用域規則是怎麼樣的？答不出來吧。我也答不出來，沒事，很多號稱專業研究數學的也不能立即答上來 (逃

命令式語言中遞歸的理論基礎? - eldereal 的回答

函數名本質上是一個地址，遞歸調用從彙編層面看就是跳轉回了函數段首地址，從底層來說是沒什麼問題的。

至於你說的函數未定義是從抽象角度想的，但只要底層沒問題，編譯器就能實現這樣的功能。

如果你真的理解高中數學上的遞歸，應該不會有這種問題。

在函數中調用函數本身時，相當於你讓程序回到函數的第一行重新走一遍而已。

1.1 演算法與程序框圖 - 高中年級必修三高中數學填空題第26頁 - 題庫巴巴上面這個演算法寫成代碼就是：

def foo(S, T): S = T * T - S if S &>= 10: W = S + T * T return W else: foo(S, T * 2)

你就把最後一行代碼看作圖中的 N 分支唄。

就理解上，你可以把函數定義分為介面與實現兩個部分。在你寫完def這一行後，函數的介面(或者叫簽名)，已經定義好了。下面的代碼是在定義其實現細節。

當你在實現中調用函數(任何函數)時，其實是在調用其介面，由編譯器或運行環境來決定實際要使用的實現。

而在未定義完成的函數實現中調用已完全定義的函數介面並沒有任何違和。

遞歸就是你說的「在定義一個function的時候，調用了這個function本身」，那麼調用自身的時候，當然就是你說的「定義未完成」么。你既然能理解肥波納妾的f(n) = f(n - 1) + f(n - 2)，它不也是「定義未完成」么，你怎麼就理解了呢？

至於實現遞歸的機制什麼的，我覺得你現在不用想這麼多。

這和python有啥關係？

遞歸函數的調用和普通函數沒有區別，都是將參數入棧，修改ESP EBP等，執行運算之後恢復之前的棧幀。

理解它的話，你就直接模擬計算機計算一下就好了。

比如到了遞歸函數的那個地方，你把新的參數帶入進去自己算一下就知道那是能算的。

如何將子問題結果綜合起來呢？那就需要保存的是外層的運演算法則，這樣遞歸結果返回後可以逐步回溯到最終的結果。

數學遞歸好理解是因為你大腦遞歸和回溯都是比較自然的，而你對計算機函數調用的機制並不了解所以產生了疑惑。

實在想搞清楚的話，去讀CSAPP第三章和函數調用有關的部分。

當然是先定義完成(Static syntax checking) 再來run time啊。。。你要是用java就更明白了。在運行之前，沒有人知道你的程序運行順序是什麼，遞歸啊，順序啊，都不重要。函數是否定義完成，是在compile的時候會檢查的。不僅僅函數是否定義完整，就連type是否匹配，是否初始化，if, else是否合法，for 是否合法，while是否合法，函數有無return，type是否可以轉換，等等等等，都要檢查完。檢查完了，編譯器已經讀完你這個函數的定義了，然後在運行時run time，才出現你這個，運行到一半就跳出去又遞歸運行自己的狀態。這個運行時當然是函數沒走完就跳出去了，但是，人家編譯之間就檢查過得好不好……

當你真正調用他的時候，它已經完成了。

def sumtree(L):

tot = 0 #初始化tot

for x in L: #對於L中的所有x

if not isinstance(x, list):#若x不屬於list

tot += x #tot累加x

else:#否則

tot += sumtree(x)

#tot累加sumtree(x)

return tot #返回tot的值

估計題主不明白的是最後一個sumtree(x)吧，此時，以x為參數傳入sumtree函數。

就好比你開了個工廠，專門做sumtree業務。一天接到原料L，你把任務發到流水線上，負責檢查的工人跑到你辦公室報告說L列表有一個元素也是列表，應該怎麼辦，你說好辦，把這個元素拆了拿出來再重頭過一遍流水線。工人問以後碰到這種事情咋辦，你說就按我剛才說的反覆做，直到最後能把所有的list都拆了。最後成品就是L內所有元素拆分後的和。

而且說道遞歸，上面的代碼其實能夠更簡潔一點。