0 回顧
之前的筆記（0）和筆記（1），我們介紹了算法的基本含義，并且舉了一些實例，同時理解了，算法就是人類在教計算機做事情！
我們知道，算法就是解決問題的方案，我們將自然語言描述的問題，轉換為符號語言，再解決問題，使用計算機思維，構建解決問題的算法，最后轉換為計算機可以識別的語言，教會計算機，讓它幫助我們解決問題。
在算法設計的時候，我們需要關注其時間和空間的復雜度，這與實際問題有關，可能關注事件，也可能關注空間，也可能二者兼有。
下面，我們來看看遞歸思想，并且使用實例來理解抽象的思想。
1 遞歸思想
遞歸是可能計算機與人類最大的不同，人類是遞推思維，能夠發散，計算機是遞歸思維，能夠做重復且簡單的固定事情。
因此，我們教計算機做事的時候，要盡可能簡單且固定，也就是，我們需要將一個復雜的問題，拆解成若干小問題，這些小問題最好還是已知的，已經被解決的，這樣，我們就很容易能夠設計出一個算法，并且教會計算機做事。
1.1 遞歸的含義
所謂的遞歸，看起來就像：同樣的一件事情，做了很多遍，雖然每一次的代碼一樣，但是每一次的數據不一樣，導致行為不一樣，并且，會有一個盡頭，一旦走到盡頭了，就得原路返回來。
我們看一個例子
#include <iostream>
using namespace std;void story(int i) {if (i > 10)return;cout << "從前有個廟，廟里有個老和尚，老和尚給小和尚講故事" << endl;cout << "講的故事是什么呢？講的是：" << endl;story(i + 1);
}int main()
{story(1);return 0;
}
這就是生活中的一個遞歸的例子，還蠻有趣的！
注意，它并不是循環！與循環還是有差別的，最重要的就是，遞歸在條件終止之后，會返回來，而循環，條件終止就停了。
1.2 遞歸算法的重要結構
- 終止條件 & 終止處理辦法
- 遞歸處理方法
我們知道，遞歸不可能無限進行下去，因此需要終止條件，以及觸發該條件后對應的處理方案。
并且，更重要的是，我們需要知道遞歸如何處理。
對于遞歸程序，通常都是解決一個小問題。
我們將一個大問題分解成若干個小問題，然后，這些小問題的處理方式是相似的，我們用遞歸來分別解決每一個小問題，得到每個小問題的解，之后將這些解合并。
階乘問題
先列出遞歸方程，再轉換為程序即可。
// 階乘問題
int factorial(int n) {if (n <= 0)return 1;elsereturn n * factorial(n - 1);
}
如果不用遞歸呢？
使用遞推！ 從1到n.用循環搞定。
// 不用recursion的階乘，遞推
int factorial2(int n) {if (n == 0)return 1;int result = 1;for (int i = 1; i <= n; i++) {result *= i;}return result;
}
遞歸特點：有去有回！從n到1！從結果到起點，再返回來。
對于遞歸來說，最開始目標的n就是已知的，然后逐漸變化到臨界值，經過層層處理，再返回來。關鍵點：遞歸方程！
斐波那契數列
遞歸方程
- f(n) = 1，n = 1或n = 0
- f(n) = f(n-1) + f(n-2)，n > 1
// 斐波那契數列
int fib(int n) {if (n == 1 || n == 0)return 1;return fib(n - 1) + fib(n - 2);
}
迭代：就是重復執行一些指令，指令是一定的，但是相關的數據是變化的。
遞歸調用的過程，終點參數在不斷變化，一直在逼近終點，最終停下來，依次返回。
小結
我們先將一個問題，使用符號語言描述，拆解問題，將其轉換成遞歸方程，使用數學語言描述，然后將其轉換為算法和實際的程序。
所謂的遞歸，就是先給出終點參數，它是復雜的，然后隨著參數的減小，會逐漸簡單，然后得到最簡單的結果，之后再往回走，就能獲得復雜問題的結果。
這與人類思維不一樣，人類通常是遞推，先解決簡單問題，再逐漸復雜化，最終解決復雜問題。
因此，求解問題的時候，可以簡單問題找規律，最終獲得復雜抽象的方程，從而獲得最終結果。
