當(dāng)人們提到“遞歸”一詞，不知道如何理解它，也有人會問遞歸和迭代有什么區(qū)別？首先可以從定義上入手來分析，遞歸是自身調(diào)用自身的函數(shù)進(jìn)行循環(huán)、遇到滿足終止條件的情況時(shí)逐層返回來結(jié)束。迭代則是函數(shù)內(nèi)某段代碼實(shí)現(xiàn)循環(huán)，循環(huán)代碼中參與運(yùn)算的變量同時(shí)是保存結(jié)果的變量，當(dāng)前保存的結(jié)果作為下一次循環(huán)計(jì)算的初始值。?

如何實(shí)現(xiàn)遞歸算法的設(shè)計(jì)方法？

遞歸算法即是一種有效的算法設(shè)計(jì)方法，也是一種有效的分析問題的方法，遞歸算法求解問題的基本思想是：對于較為復(fù)雜的問題，把原問題分解成諾干個(gè)相對簡單且類同的子問題，這樣，原問題就可遞推得到求解。 適宜用遞歸算法求解的問題的充分必要條件是：

其一，問題具有某種可借用的類同自身的子問題描述的性質(zhì)：

其二，某一有限步的子問題（也稱做本原問題）有直接的解存在。

如何去理解遞歸算法？

從小老師就教我們?nèi)绾胃咝У膹?加到100，如果我們在沒有了解過高斯計(jì)數(shù)的情況下，我想大部分人，都會一個(gè)一個(gè)進(jìn)行累加的方式。這樣是不是得不償失呢？那么如何描述他的代碼結(jié)構(gòu)呢？

從上述算法中可以看出，都可以得出結(jié)果是5050。那么不僅有小伙伴會問？這兩個(gè)都可以得出相應(yīng)的結(jié)果，那我在工作中，如何使用那種方案呢？ 關(guān)于這一點(diǎn)就要去分析他們的時(shí)間復(fù)雜度和空間復(fù)雜度了。 先去計(jì)算他的時(shí)間復(fù)雜度假設(shè)時(shí)間復(fù)雜度為f(n)=2n+1, 那么f(n）的計(jì)算方法第一行執(zhí)行了一個(gè)時(shí)間單位，第二行執(zhí)行了n個(gè)時(shí)間單位，第三行執(zhí)行了n個(gè)時(shí)間單位，可以得出f(n)=2n+1。因?yàn)闀r(shí)間復(fù)雜度表示的是算法隨n變化的一種趨勢，而f(n)=2n+1表示的就是一種線性增長關(guān)系，為了統(tǒng)一表達(dá)忽略常數(shù)項(xiàng)和系數(shù)，可得時(shí)間復(fù)雜度為O(n)！ 空間復(fù)雜度是隨n的變化而變化，因此空間復(fù)雜度為O(n)。?

?遞歸的算法最典型的是遞歸求斐波那契數(shù)列的算法

這個(gè)求斐波那契的遞歸算法的時(shí)間復(fù)雜度是多少呢？ 在講解遞歸時(shí)間復(fù)雜度的時(shí)候，我們提到了遞歸算法的時(shí)間復(fù)雜度本質(zhì)上是要看: 遞歸的次數(shù) * 每次遞歸的時(shí)間復(fù)雜度。 可以看出上面的代碼每次遞歸都是O(1)的操作。再來看遞歸了多少次，這里將i為5作為輸入的遞歸過程 抽象成一顆遞歸樹，如圖：?

?從圖中，可以看出f(5)是由f(4)和f(3)相加而來，那么f(4)是由f(3)和f(2)相加而來 以此類推。 在這顆二叉樹中每一個(gè)節(jié)點(diǎn)都是一次遞歸，那么這棵樹有多少個(gè)節(jié)點(diǎn)呢？ 我們之前也有說到，一棵深度（按根節(jié)點(diǎn)深度為1）為k的二叉樹最多可以有 2^k - 1 個(gè)節(jié)點(diǎn)。 所以該遞歸算法的時(shí)間復(fù)雜度為 O(2^n) ，這個(gè)復(fù)雜度是非常大的，隨著n的增大，耗時(shí)是指數(shù)上升的。

如何去理解遞歸算法的數(shù)據(jù)推導(dǎo)？

數(shù)學(xué)中經(jīng)常有這樣的函數(shù)，它自己定義自己。例如：n的階乘函數(shù)f(n)=n!，n為整數(shù)： f(n)=1 n<=1 f(n)=nf(n-1) n>1

當(dāng)n小于或等于1時(shí)，f(n)的值為1，例如f(-3)=f(0)=f(1)=1。當(dāng)n大于1時(shí)，f(n)是遞歸定義的，因?yàn)橛覀?cè)也有f。但這不會導(dǎo)致循環(huán)完義，因?yàn)橛覀?cè)f的參數(shù)小于左側(cè)f的參數(shù)。例如，f(2)=2f(1)，因?yàn)閒(1)=1，所以f(2)=2*1=2,以此類推，f(3)=3f(2)=3*2=6。 假定f(n)是直接遞歸的。要使函數(shù)f(n)的遞歸定義有一個(gè)完全的形式，需要滿足如下條件：

• 有一個(gè)基礎(chǔ)部分（base component)，它包含n的一個(gè)或多個(gè)值，對這些值，f(n)是直 接定義的（即不用遞歸就能求解）。為簡單起見，我們假定f的定義域是非負(fù)整數(shù)，基 礎(chǔ)部分包含0<=n<=k，其中k為作負(fù)常數(shù)。（n>=k的情形也是可能的，但很少見。）

• 在遞歸部分（recursive component），右側(cè)f有一個(gè)參數(shù)小于n，因此重復(fù)應(yīng)用遞歸部分可以把右側(cè)f的表達(dá)式轉(zhuǎn)變?yōu)榛A(chǔ)部分。

總之，遞歸算法是程序設(shè)計(jì)中一種重要的方法，在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中，使用遞歸的思想能解決很多運(yùn)算量較大的問題，節(jié)省大量的人力資源和時(shí)間，但對于遞歸的概念，初學(xué)者往往感到不容易理解，那么為什么還要引入遞歸的概念呢？

其一，有很多數(shù)學(xué)函數(shù)本身就是遞歸定義的，如階乘函數(shù)當(dāng) n = 1 時(shí)，n!=1時(shí)，n!=1,當(dāng) n>1時(shí)，n!=nx(n-1)!;

其二，有些數(shù)據(jù)結(jié)構(gòu)，如二叉樹、廣義表等，由于結(jié)構(gòu)本身固有的遞歸特性，有關(guān)它們的操作，就可以采用遞歸函數(shù)來實(shí)現(xiàn)；

其三，還有一類問題，雖問題本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸法求解，則更簡潔明了，如快速排序問題、圖的深度優(yōu)先搜索問題等。