一切都應該儘可能地簡單，但不要太簡單 ——阿爾伯特·愛因斯坦
將複雜的問題簡單化，抓到本質，能夠讓我們的編程更愉快。分治策略、動態規劃都是如此，將複雜的問題分解成規模小的簡單問題。本文介紹的遞歸，是很多算法都使用的一種方法，讓複雜問題簡單化，同時能讓你的代碼更加優雅。
調用棧
講遞歸之前，不得不提到調用棧(Call Stack)，因為調用棧:
- 使得遞歸成為可能
- 同時有助於理解遞歸的執行細節。
自定義函數，使得代碼可以複用。從某種程度上說，一個程序的執行過程，就是無數個的函數相互調用，達到實現最終目標的旅程。而這些函數之間的調用關係，就用調用棧來描述，這也是“函數調用棧”前四個字的由來，最後一個字對應LIFO的數據結構棧。
函數需要區分定義(defined)和執行(executed, called)兩種情形，以python為例：
- def語句定義一個函數，本質上和賦值語句沒有區別，只是bind了一個name到一個value (使得定義遞歸函數成為可能)
- 函數真正執行時(called), 會創建一個Local Frame, 這個Local Frame維護著該函數內部的局部變量。
函數每執行一次，創建的一個Local Frame，所有的Local Frame使用函數調用棧(Call Stack, LIFO)維護，每個Local Frame對應該棧中的一個元素，裡面記錄著某個函數在某次執行時的一些局部變量(Local Variable, 函數的入參及函數內部定義的變量)。調用棧，讓不同執行函數間的局部變量互相不干擾，使得程序能夠正確執行。
函數調用棧在每個編程語言內部實現，使用起來很方便，但每次的函數調用，都會佔用一定的內存。如果函數調用次數很多(一直push入棧)，並一直不返回結果(沒有pop出棧)，即Call Stack很大，會佔用大量的內存，可能會導致棧溢出，也就是著名的stack overflow。
很多編程比賽中，為追求速度的極致，很多選手採用C、C++語言，很多有經驗的選手，通常都將大的數組放在main函數，用全局變量表示。如果放在某個函數內部做為局部變量，即使遞歸調用次數少，但也可能因為局部變量太大，產生棧溢出。
何為遞歸
遞歸，簡單說就是一個函數，自己調用自己。
調用棧，使得遞歸成為可能。遞歸和其他函數調用並沒有本質不同，都是執行到某行，建立新的棧幀，執行完後彈出返回原點繼續執行。
遞歸函數實現中的一個常見模式，以基本情況開始（base case），後面跟著的是遞歸情況（recursive case）。
- 基本情況：定義了在輸入是最簡單輸入數據下的求解，此時函數不調用自身，避免形成死循環。
- 遞歸情況：此時函數調用自身，將規模大的原問題（複雜）分解為規模小的子問題（簡單）。
理解了調用棧，再理解遞歸就相當簡單。舉一個計算階乘的例子:
可以這麼理解:
- CEO說(main函數對應的棧幀)：總監, 給我算下f(3)
- 總監(f(3)函數對應的棧幀)： 經理，給我算下f(2)
- 經理(f(2)函數對應的棧幀)： 組長，給我算下f(1)
- 組長(f(1)函數對應的棧幀)： 程序員，給我算下f(0)
- 程序員（f(0)函數對應的棧幀）：報告組長，f(0) = 1；（f(0)執行完畢，銷燬f(0)棧幀）
- 組長：報告經理，f(1) = 1*f(0) = 1，f(1)執行完畢，銷燬f(1)棧幀
- 經理： 報告總監, f(2) = 2*f(1) = 2，f(2)執行完畢，銷燬f(2)棧幀
- 總監：報告老大, f(3) = 3*f(2) = 6，f(3)執行完畢，銷燬f(3)棧幀
- CEO總結： 幹得漂亮，main()執行完畢，銷燬main()棧幀，退出。
注意上述步驟的粗體部分: f(3) -> f(2) -> f(1) -> f(0) -> f(0) -> f(1) -> f(2) -> f(3), 明顯的LIFO的棧結構。
尾遞歸: 不只要優雅，也要性能
遞歸讓人又愛又恨。愛他的人說：遞歸讓我的代碼更優雅；恨他的人說，遞歸讓性能更差。
也有人說，使用遞歸，代碼更加優雅；但使用循環，性能更優。
如果說非遞歸是普通人，遞歸是優雅的天使，那麼尾遞歸就是戰鬥天使，好看又能打。尾遞歸，是遞歸的一種特殊形式，需滿足下面兩個條件:
- 遞歸調用是整個函數體中最後執行的語句(即遞歸調用完成後，不需要再執行其他運算)
- 它的返回值不屬於表達式的一部分
編譯器可以利用尾遞歸的特性，生成優化的代碼，猜測內部用循環的形式實現，而不是建立一個又一個的棧幀。（注：之所以能夠優化，是因為調用在尾部，沒有必要保存任何局部變量，可以通過循環實現）。
以1+2+3+…+n求累積和為例（不用階乘，是因為書太大，即使long long也會溢出）。
源碼如下:
Makefile如下:
測試結果如下:
usng optimimized cumsum
tco_cumsum(999000)=499000999500
cumsum(999000)=499000999500
usng default cumsum
Segmentation fault
- 默認編譯選項: 即"g++ cumsum.cpp -o cumsum", 會產生Segmentation fault
- 用"-O2"編譯選項，不再報錯，輸出結果。不過g++的編譯器好像足夠聰明，即使不是嚴格意義上的尾遞歸，它也能夠優化。
python和尾遞歸
cython不支持尾遞歸，python設計者為了方便調試，有意不官方支持的。如果支持，棧跟蹤(tracebacks)信息會亂掉。
python中如果用遞歸，最好確保遞歸的深度不要太大，否則會很慢。最好建議手動優化成循環實現。為了快，只能犧牲部分優雅。
"make factorial_test"執行結果如下:
遞歸@Python
python factorial.py
f(10)=3628800
Traceback (most recent call last):
File "factorial.py", line 59, in <module>
print("f({})={}".format(1000, factorial(1000)))
File "factorial.py", line 32, in factorial
return n * factorial(n - 1)
File "factorial.py", line 32, in factorial
return n * factorial(n - 1)
File "factorial.py", line 32, in factorial
return n * factorial(n - 1)
[Previous line repeated 995 more times]
File "factorial.py", line 29, in factorial
if n == 0:
RecursionError: maximum recursion depth exceeded in comparison
計算f(1000)時，最大遞歸深度超出範圍，報錯
小結
尾遞歸可以讓代碼不僅優雅，也保證性能（通過讓編譯器優化支持）。不過PYTHON官方不支持尾遞歸優化。
實戰: 給定一個序列，其長度為n, 從中取出k個元素的所有組合
方案1: 最簡單暴力的方式是用for循環實現，但是for循環的層數為k，k為動態變化。這種方案比較醜陋，k變化，代碼就得跟變化。
方案2: 用遞歸，先取其中一個元素，在從剩下的可選元素中取k-1個元素（長度為k的問題，簡化為長度k-1的簡單問題），相對方案1，算是優雅的方案。
方案3: 用python自帶的itertools模塊
執行結果:
遞歸: [['周杰倫', '李健'], ['周杰倫', '王菲'], ['李健', '王菲']]
循環: [['周杰倫', '李健'], ['周杰倫', '王菲'], ['李健', '王菲']]
itertools: [('周杰倫', '李健'), ('周杰倫', '王菲'), ('李健', '王菲')]
總結
本文介紹了調用棧、遞歸：通過CEO下達指令的過程，類比遞歸的執行過程。
結合C++/Python給出了階乘、累積和、組合的例子。
遞歸使得代碼優雅，尾遞歸使得性能得到保證。