遞歸算法就是通過(guò)自身不斷反復(fù)調(diào)用自身以解決問(wèn)題，其中最經(jīng)典的也就是漢諾達(dá)和斐波納契數(shù)列的問(wèn)題了休吠。
1.漢諾塔問(wèn)題
在印度，有這么一個(gè)古老的傳說(shuō)：在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候训裆，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔蜀铲。不論白天黑夜边琉，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片，一次只移動(dòng)一片记劝，不管在哪根針上变姨，小片必在大片上面。當(dāng)所有的金片都從梵天穿好的那根針上移到另外一概針上時(shí)厌丑，世界就將在一聲霹靂中消滅定欧，梵塔、廟宇和眾生都將同歸于盡怒竿。

image.png

分析：挪到C的金片也是從下到上由大到小的順序排列砍鸠，那么A之剩下最下面的金片移動(dòng)到C的時(shí)候，C上面是不可以有金片的愧口，這個(gè)時(shí)候A上面只有第n個(gè)金片睦番，B上面有n-1個(gè)金片，C上面沒(méi)有金片，然后這個(gè)情況就和剛開(kāi)始情況相同了托嚣，只不過(guò)A和B顛倒了位置而已巩检。
（1）n-1個(gè)金片從A通過(guò)C移動(dòng)到B，n-1個(gè)金片從A通過(guò)C移動(dòng)到B也是不斷調(diào)用自身逐步縮小范圍示启。通過(guò)遞歸調(diào)用后兢哭，就完成了A上面僅剩下最大的金片，C上面沒(méi)有金片夫嗓，B上面有n-1個(gè)金片迟螺。
（2）最大的那個(gè)金片從A移動(dòng)到C
（3）調(diào)用自身重復(fù)剛開(kāi)始的情況，只不過(guò)現(xiàn)在有金片的是B，即B通過(guò)A把金片移動(dòng)到C。

image.png

2.斐波納契數(shù)列
2.1生兔子問(wèn)題
古典問(wèn)題：3個(gè)月起每個(gè)月都生一對(duì)兔子奢赂，小兔子長(zhǎng)到第三個(gè)月后每個(gè)月又生一對(duì)兔子，假如兔子都不死窍株，問(wèn)每個(gè)月的兔子總數(shù)為多少？下面先從小到大分析下這個(gè)情況
分析：假設(shè)將兔子分為小中大三種攻柠，兔子從出生后從第三個(gè)月開(kāi)始每個(gè)月就會(huì)生出一對(duì)兔子球订，也就是一旦兔子變?yōu)榇笸米幽敲此蜕艘粚?duì)兔子
分析情況圖如下

image.png

很明顯這個(gè)是一個(gè)為斐波那契數(shù)列，即如果用f(n)表示第n個(gè)月的兔子的對(duì)數(shù)瑰钮，那么f(n)=f(n-1)+f(n-2)

image.png

image.png

2.2走臺(tái)階問(wèn)題
一個(gè)臺(tái)階總共有n級(jí)开睡，如果一次可以跳1級(jí)，也可以跳2級(jí)苟耻。求總共有多少總跳法士八，并分析算法的時(shí)間復(fù)雜度。
分析：假設(shè)我們現(xiàn)在還有最后一步要走梁呈，可能的情況有哪些？
（1）我們站在第9級(jí)上蘸秘，一步1級(jí)后到達(dá)頂端官卡；
（2）我們站在第8級(jí)上，一步2級(jí)后到達(dá)頂端醋虏；
所以寻咒，最后一步可以走1級(jí)或者2級(jí)，不外乎兩種情況颈嚼。
再假設(shè)毛秘，已知從0級(jí)到9級(jí)的走法有M種，從0級(jí)到8級(jí)的走法有N種，那么從0到10級(jí)的走法和M叫挟、N有什么關(guān)系呢艰匙？從0到10級(jí)的走法一共是多少種呢？答案是M+N抹恳。
所以逐步遞歸员凝，說(shuō)白了，這還是個(gè)Fibnacci數(shù)列奋献。即f(n)=f(n-1)+f(n-2)健霹，事件復(fù)雜度是2^n

臺(tái)階問(wèn)題的變種:
一個(gè)臺(tái)階總共有n級(jí)，如果一次可以跳1級(jí)瓶蚂，也可以跳2級(jí).....也可以跳n級(jí)糖埋。求總共有多少總跳法

分析：用Fib(n)表示跳上n階臺(tái)階的跳法數(shù)。如果按照定義窃这，F(xiàn)ib(0)肯定需要為0瞳别，否則沒(méi)有意義。但是我們?cè)O(shè)定Fib(0) = 1钦听；n = 0是特殊情況洒试，通過(guò)下面的分析就會(huì)知道，強(qiáng)制令Fib(0) = 1很有好處朴上。因?yàn)镕ib(0)等于幾都不影響我們解題垒棋，但是會(huì)影響我們下面的分析理解。

當(dāng)n = 1 時(shí)痪宰， 只有一種跳法叼架，即1階跳：Fib(1) = 1;

當(dāng)n = 2 時(shí)， 有兩種跳的方式衣撬，一階跳和二階跳：Fib(2) = 2;

到這里為止乖订，和普通跳臺(tái)階是一樣的。

當(dāng)n = 3 時(shí)具练，有三種跳的方式乍构，第一次跳出一階后，對(duì)應(yīng)Fib(3-1)種跳法扛点； 第一次跳出二階后哥遮，對(duì)應(yīng)Fib(3-2)種跳法；第一次跳出三階后陵究，只有這一種跳法眠饮。Fib(3) = Fib(2) + Fib(1)+ 1 = Fib(2) + Fib(1) + Fib(0) = 4;

當(dāng)n = 4時(shí)，有四種方式：第一次跳出一階铜邮，對(duì)應(yīng)Fib(4-1)種跳法仪召；第一次跳出二階寨蹋，對(duì)應(yīng)Fib(4-2)種跳法；第一次跳出三階扔茅，對(duì)應(yīng)Fib(4-3)種跳法已旧；第一次跳出四階，只有這一種跳法咖摹。所以评姨，F(xiàn)ib(4) = Fib(4-1) + Fib(4-2) + Fib(4-3) + 1 = Fib(4-1) + Fib(4-2) + Fib(4-3) + Fib(4-4) 種跳法。

當(dāng)n = n 時(shí)萤晴，共有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)文虏。

通過(guò)上述分析，我們就得到了通項(xiàng)公式：

             Fib(n) =  Fib(0)+Fib(1)+Fib(2)+.......+ Fib(n-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