怎麼樣可以很好地理解編程中的遞歸呢？

01-04

大家都說遞歸很好理解，但是就我個人而言，可能是習慣了過程編程，對遞歸這樣的函數式編程，雖然它確實比較易讀，但是自己寫的話，總是會出現各種問題，總歸還是對遞歸的理解不好。求知乎神人指教，怎麼樣可以去更好地理解遞歸呢
-------------------------------------------------------補充問題------------------------------------------------------------------------

最近在編寫一個實現背包問題最簡單形式的小程序。
給定一個數組，我這裡假設它是 array = [11,10,9,8,7,6,5]，然後從裡面選擇若干元素，把它裝入容量為20的背包中，並使背包剛好裝滿。我打算用遞歸實現。遞歸函數的形式是：
public static void knapsack(int start,int target)
{
........
}
參數start表示掃描數組的開始下標，比如對於上面的array數組，先從下標0開始，即array[0]開始掃描數組，然後利用遞歸一次從1，2,3……逐個開始掃描。參數target表示背包容量。每次掃描，如果掃描到的數值小於target（假設這個數是num），則假定這個數是滿足某一組合中的一個數。相應target -= num；以此類推。。。。這樣就可以進行遞歸了。
終止條件：

如果按照我這樣寫的話，遞歸的終止條件應該是 array[start] == targrt || start&>array.lenght-1;
我寫的程序是：
private static int[] choice = [11,10,9,8,7,6,5];
public static void knapsack(int start,int tar)
{
if(choice[start] == tar || start&>choice.length-1)

{
System.out.print(choice[start]+" ");
System.out.println();
return;
}
else if(choice[start] &< tar)
{
System.out.print(choice[start]+" ");
tar -= choice[start];

}
for(int i=start+1;i& {
knapsack(i,tar);
}
}

public static void main(String[] args)
{
int target = 20;
knapsack(0,target);
}
自然這個程序就是各種問題跑不下來了。

PS：我發現自己在寫遞歸程序的時候，總是喜歡腦部遞歸程序的運行，然後又對遞歸程序的理解不夠，於是腦補著腦補著，就會覺得很亂了。。O(∩_∩)O 。謝謝廣大的知友。
關於數學歸納法的思想，根據我自己的理解，數學歸納法一般都是先證 x = 1，然後假設x=k時某公式成立，繼而通過x=k 證明 x=k+1時公式也成立。所以我覺得數學歸納法是k從小→大，推理起來比較順其自然。而遞歸，我的理解大概是大→小→大，其實也比較好理解，但是寫起程序來，就會出現各種問題。

從遞歸的（過程式）實現而非數學原理來理解，會更加容易。

首先說個有趣的事實，早期的編程語言實現（如FORTRAN 77）不支持定義遞歸函數。原因很簡單，因為函數是這麼實現的：內部變數存放的位置固定好，而調用函數就是跳轉到指定位置、執行代碼、再跳轉回去。這樣實現函數，問題就出來了：遞歸地調用自己時，數據以及執行流無法與上一次調用分隔開，遞歸的邏輯自然實現不了（不論是直接還是間接遞歸）

之後計算機科學家E.W.Dijkstra發表文章《Recursive Programming》（網上能找到原文），提出了用棧這一數據結構實現遞歸的演算法。所有的函數調用通過一個執行棧來實現：棧內存放的對象為棧幀，每一次調用函數，壓入一個棧幀，這個棧幀包括了這次調用的參數、函數變數以及執行的上下文。函數執行完畢時，彈出棧幀，返回值交給之前執行被掛起的棧幀，繼續計算。這樣一來，遞歸的語義就實現了：同一個函數，可以有不同實例在運行，而一個實例的執行流程又依賴於另一個實例的返回值。這種依賴關係，體現在棧的先入後出性，而棧幀的實現，隔離開不同實例的數據，避免新一輪調用對之前調用的破壞。

這一設計甚至影響到CPU設計，現代CPU都有硬體棧對這一機制提供支持，許多語言（如C/C++）的編譯器能夠生成高效利用硬體棧的機器碼。而一些實現得不咋樣的語言（如Python），它們支持遞歸，也是用棧來實現的（軟體實現的棧）

稍微延伸一下：

剛才提到同一函數之間不同實例的依賴來自返回值。實際上還有自由變數（函數體引用的非參數的變數）。在C的情形下，就是全局變數（因為沒有嵌套函數定義），而如果是允許嵌套函數定義（或至少像C++11一樣加了個lambda），自由變數還可以是函數變數，情形就複雜多了，需要引入詞法作用域與閉包。另外在多線程下執行有副作用的遞歸函數，執行流和結果都是非確定性的。
函數式編程里還有尾遞歸優化這一概念。之前的棧式實現遞歸，n次調用的空間複雜度為O(n)，但如果函數體滿足尾遞歸的形式（返回前最後一件事就是調用自己），那就可以不用壓棧，直接goto，空間複雜度為O(1)。像Scheme，就要求所有實現都自動做尾遞歸優化。
遞歸的概念不僅停留在遞歸函數，還有遞歸數據類型。比如上下文無關文法就可以非常方便地表示為遞歸的數據類型。

要理解遞歸必先理解遞歸！

遞歸本身是十分容易理解的，從數學角度來看只是很簡單的函數的自我調用，比如Fibonacci數列：

f(0) = 0

f(1) = 1

f(k) = f(k - 1) + f(k - 2)

其實遞歸的概念在高中階段就已經介紹了，就是經常用來證明數列題的」數學構造法「，特點很明顯：結構簡單、證明粗暴，只要你架構好了框架就能證明出結論。

那麼什麼是遞歸的」結構簡單「的框架？

初始條件： f(0) = 0, f(1) = 1
遞歸的表達式: f(k) = f(k - 1) + f(k - 2)

而其實關於Fibonacci，每個人從f(0)開始往後計算都會，而且很自然。哪怕讓你算f(1000)，你需要的不過是紙、筆、時間，所以，遞歸本身的難度不大。

那麼又為什麼遞歸會給人難以理解的印象？那是因為"遞歸的實現"難以理解，尤其是利用計算機語言實現遞歸。因為，實現是反過來的，不是讓你從初始條件推，而是反過來一直推到初始條件，初始條件反而變成了退出條件。

為了能夠反推，計算機必須利用棧來存儲整個遞歸過程中產生的數據，所以寫遞歸會遇到棧溢出的問題。為了能實現遞歸，人腦也要去模擬整個的遞歸過程，可惜的是，人腦的存儲有限，雙參數三層遞歸基本就能讓你溢出。

所以，最直接的方法就是用紙把腦子中的棧記錄下來。十分機械痛苦，且耗費耐心，但是往往在過程中還是能發現問題。

或者，回到遞歸本身的定義上，自己首先寫上架構，然後填充。定義好退出條件，定義好表達式。之後再嚴格按照架構實現代碼。遞歸的代碼一般都是足夠簡單的，所以實現上不容易出錯。一旦程序結果有問題，首先不應該是去檢查代碼，而是應該去檢查自己的定義。死循環？初始條件錯了、漏了；錯誤結果？遞歸式有問題。找出問題了，再依照新的架構改動代碼。沒有把問題定義清楚前不要去實現。當然，實在不行，只能最後一招：紙和筆。

-----------------------以上都是廢話的分割線-----------------------

好了，我們講重點吧：

The Little Schemer 看完這本」兒童讀物「，從此遞歸是路人，我是認真的。

關於SICP這本書，你就為了掌握遞歸，有必要去看好幾百頁的書實現個解釋器么。看完兒童讀物再看這個SICP么。

「我五分鐘後到，如果沒有，請再看一遍此簡訊"

谷歌教你遞歸

其實我們學的前序後序中序的混合就是遞歸的控制流，舉個例子：

f(){//1

f();

//2

f();

//3

}

遞歸程序跑的時候形成了一棵樹，樹中的每個節點就是一個函數了，在每個節點，控制流都會經過三次，分別執行了1，2，3處的代碼，我們學的前中後序遍歷剛好分別是那三處。

我覺得搞懂分治對這個幫助很大。

定義上的說的什麼函數調用自己只是表現形式，我不覺得有什麼指導意義。

一個問題的規模是N，你給出一個演算法，使他每次的規模都減少同時解決這個小規模問題的演算法和大規模演算法是一樣的，這樣不斷的分解，直至你能簡單的完成它。

調用自己玩自己

感覺你出現的問題應該在結束條件上

以一個初學者的體會，理解遞歸最重要的是要有【整體思想】。