① 常見演算法1——遞歸演算法
遞歸演算法就是通過自身不斷反復調用自身以解決問題，其中最經典的也就是漢諾達和斐波納契數列的問題了。
1.漢諾塔問題
在印度，有這么一個古老的傳說：在世界中心貝拿勒斯（在印度北部）的聖廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片，一次只移動一片，不管在哪根針上，小片必在大片上面。當所有的金片都從梵天穿好的那根針上移到另外一概針上時，世界就將在一聲霹靂中消滅，梵塔、廟宇和眾生都將同歸於盡。
分析：挪到C的金片也是從下到上由大到小的順序排列，那麼A之剩下最下面的金片移動到C的時候，C上面是不可以有金片的，這個時候A上面只有第n個金片，B上面有n-1個金片，C上面沒有金片，然後這個情況就和剛開始情況相同了，只不過A和B顛倒了位置而已。
（1）n-1個金片從A通過C移動到B，n-1個金片從A通過C移動到B也是不斷調用自身逐步縮小范圍。通過遞歸調用後，就完成了A上面僅剩下最大的金片，C上面沒有金片，B上面有n-1個金片。
（2）最大的那個金片從A移動到C
（3）調用自身重復剛開始的情況，只不過現在有金片的是B，即B通過A把金片移動到C。
2.斐波納契數列
2.1生兔子問題
古典問題：3個月起每個月都生一對兔子，小兔子長到第三個月後每個月又生一對兔子，假如兔子都不死，問每個月的兔子總數為多少？下面先從小到大分析下這個情況
分析：假設將兔子分為小中大三種，兔子從出生後從第三個月開始每個月就會生出一對兔子，也就是一旦兔子變為大兔子那麼他就生了一對兔子
分析情況圖如下
很明顯這個是一個為斐波那契數列，即如果用f(n)表示第n個月的兔子的對數，那麼f(n)=f(n-1)+f(n-2)
2.2走台階問題
一個台階總共有n級，如果一次可以跳1級，也可以跳2級。求總共有多少總跳法，並分析演算法的時間復雜度。
分析：假設我們現在還有最後一步要走，可能的情況有哪些？
（1）我們站在第9級上，一步1級後到達頂端；
（2）我們站在第8級上，一步2級後到達頂端；
所以，最後一步可以走1級或者2級，不外乎兩種情況。
再假設，已知從0級到9級的走法有M種，從0級到8級的走法有N種，那麼從0到10級的走法和M、N有什麼關系呢？從0到10級的走法一共是多少種呢？答案是M+N。
所以逐步遞歸，說白了，這還是個Fibnacci數列。即f(n)=f(n-1)+f(n-2)，事件復雜度是2^n
台階問題的變種:
一個台階總共有n級，如果一次可以跳1級，也可以跳2級.....也可以跳n級。求總共有多少總跳法
分析：用Fib(n)表示跳上n階台階的跳法數。如果按照定義，Fib(0)肯定需要為0，否則沒有意義。但是我們設定Fib(0) = 1；n = 0是特殊情況，通過下面的分析就會知道，強制令Fib(0) = 1很有好處。因為Fib(0)等於幾都不影響我們解題，但是會影響我們下面的分析理解。
當n = 1 時， 只有一種跳法，即1階跳：Fib(1) = 1;
當n = 2 時， 有兩種跳的方式，一階跳和二階跳：Fib(2) = 2;
到這里為止，和普通跳台階是一樣的。
當n = 3 時，有三種跳的方式，第一次跳出一階後，對應Fib(3-1)種跳法； 第一次跳出二階後，對應Fib(3-2)種跳法；第一次跳出三階後，只有這一種跳法。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;
當n = 4時，有四種方式：第一次跳出一階，對應Fib(4-1)種跳法；第一次跳出二階，對應Fib(4-2)種跳法；第一次跳出三階，對應Fib(4-3)種跳法；第一次跳出四階，只有這一種跳法。所以，Fib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 種跳法。
當n = n 時，共有n種跳的方式，第一次跳出一階後，後面還有Fib(n-1)中跳法； 第一次跳出二階後，後面還有Fib(n-2)中跳法..........................第一次跳出n階後，後面還有 Fib(n-n)中跳法。Fib(n) = Fib(n-1)+Fib(n-2)+Fib(n-3)+..........+Fib(n-n) = Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-1)。
通過上述分析，我們就得到了通項公式：
因此，有 Fib(n-1)=Fib(0)+Fib(1)+Fib(2)+.......+Fib(n-2)
兩式相減得：Fib(n)-Fib(n-1) = Fib(n-1) =====》 Fib(n) = 2*Fib(n-1) n >= 3
這就是我們需要的遞推公式：Fib(n) = 2*Fib(n-1) n >= 3