目錄

遞歸

什么是遞歸？

遞歸的兩個(gè)必要條件?

遞歸的優(yōu)缺點(diǎn)

遞歸求階乘

遞歸求斐波那契數(shù)

優(yōu)化求階乘和斐波那契數(shù)

總結(jié)

---

遞歸

什么是遞歸？

所謂遞歸，我認(rèn)為就是存在傳遞也存在歸還功能的一種算法，簡(jiǎn)單點(diǎn)來說，就是一個(gè)函數(shù)直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問題層層轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來求解。特點(diǎn)：函數(shù)自己調(diào)用自己

遞歸的兩個(gè)必要條件?

• 存在限制條件，當(dāng)滿足這個(gè)限制條件的時(shí)候，遞歸便不再繼續(xù)。?
• 每次遞歸調(diào)用之后越來越接近這個(gè)限制條件

遞歸的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

簡(jiǎn)潔。只需要幾行代碼就能實(shí)現(xiàn)遞歸。

在樹的前序，中序，后序遍歷算法中，遞歸的實(shí)現(xiàn)明顯要比循環(huán)簡(jiǎn)單得多。

缺點(diǎn)：

遞歸由于是函數(shù)調(diào)用自身，而函數(shù)調(diào)用是有時(shí)間和空間的消耗的：每一次函數(shù)調(diào)用，都需要在內(nèi)存棧中分配空間以保存參數(shù)、返回地址以及臨時(shí)變量，而往棧中壓入數(shù)據(jù)和彈出數(shù)據(jù)都需要時(shí)間。->效率

遞歸中很多計(jì)算都是重復(fù)的，由于其本質(zhì)是把一個(gè)問題分解成兩個(gè)或者多個(gè)小問題，多個(gè)小問題存在相互重疊的部分，則存在重復(fù)計(jì)算，如Fibonacci斐波那契數(shù)列的遞歸實(shí)現(xiàn)。->效率

調(diào)用棧可能會(huì)溢出，其實(shí)每一次函數(shù)調(diào)用會(huì)在內(nèi)存棧中分配空間，而每個(gè)進(jìn)程的棧的容量是有限的，當(dāng)調(diào)用的層次太多時(shí)，就會(huì)超出棧的容量，從而導(dǎo)致棧溢出。->性能

---

下面從幾個(gè)遞歸的例題讓大家更清楚的理解遞歸算法！

遞歸求階乘

• 函數(shù)功能：設(shè)計(jì)factorial函數(shù)求第n階的階乘數(shù)。（不考慮溢出）
• 遞歸部分：階乘的原公式是：n!=n*(n-1)*(n-2)...3*2*1，根據(jù)將大問題分解成小問題，我們把它轉(zhuǎn)換成這樣：n!=n*(n-1)!
• 核心代碼：

int factorial（int n） {if（n <= 1）// 0! = 1return 1;elsereturn n* factorial(n-1) }

當(dāng)n=5時(shí) Factorial函數(shù)遞歸過程配圖如下：

---

遞歸求斐波那契數(shù)

普及一下，斐波那契數(shù)列（Fibonacci Sequence）又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardoda Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、34、……

• 函數(shù)功能：設(shè)計(jì)Fibonacci函數(shù)求第n個(gè)斐波那契數(shù)的值。（不考慮溢出）
• 遞歸部分：F（n）=F（n-1）+F（n-2）（n>2,n∈N*，F[1]=1,F[2]=1），也就是一個(gè)數(shù)會(huì)等于前兩個(gè)數(shù)相加的結(jié)果。
• 核心代碼：

int fib（int n） {if（n <= 2）return 1;elsereturn fib(n - 1) + fib(n - 2) }

當(dāng)n=6時(shí)，Fibonacci函數(shù)遞歸過程配圖如下：

---

從以上兩個(gè)例題我們不難看出有些問題：

• Factorial函數(shù)遞歸會(huì)隨著n的增加而使棧的空間變小，以至于棧溢出，程序崩潰。
• Fibonacci函數(shù)遞歸會(huì)存在很多重復(fù)的計(jì)算，使得計(jì)算起來特別耗費(fèi)時(shí)間。

遞歸與棧的關(guān)系

遞歸的過程就是出入棧的過程，在調(diào)試factorial函數(shù)的時(shí)候，如果你給的參數(shù)比較大，那就會(huì)報(bào)錯(cuò)：Stack Overflow（棧溢出）這樣的信息。系統(tǒng)分配給程序的棧空間是有限的，但是如果出現(xiàn)了死循環(huán)，或者（死遞歸），這樣有可能導(dǎo)致一直開辟棧空間，最終產(chǎn)生棧空間耗盡的情況，這樣的現(xiàn)象我們稱為棧溢出。

那如何優(yōu)化解決上述的問題呢？

將遞歸改寫成非遞歸。

使用static對(duì)象替代nonstatic局部對(duì)象。在遞歸函數(shù)設(shè)計(jì)中，可以使用static對(duì)象替代nonstatic局部對(duì)象（即棧對(duì)象），這不僅可以減少每次遞歸調(diào)用和返回時(shí)產(chǎn)生和釋放nonstatic對(duì)象的開銷，而且static對(duì)象還可以保存遞歸調(diào)用的中間狀態(tài)，并且可為各個(gè)調(diào)用層所訪問。

---

優(yōu)化求階乘和斐波那契數(shù)

• 非遞歸的核心代碼：

//求n的階乘（非遞歸） int factorial（int n） {int result = 1;while(n > 1){result *= n;n -= 1;}return result; } //求第n個(gè)斐波那契數(shù)（非遞歸） int fib(int n) {int result;int pre_result;int next_older_result;result = pre_result = 1;while(n > 2){n -= 1;next_older_result = pre_result;pre_result = result;result = pre_result + next_older_result;}return result; }

總結(jié)

解決遞歸問題的主要思想是分治思想，即我們?cè)谶f歸時(shí)要盡量將問題的規(guī)模縮小。

許多問題是以遞歸的形式進(jìn)行解釋的，這只是因?yàn)樗确沁f歸的形式更為清晰。

但是這些問題的迭代實(shí)現(xiàn)往往比遞歸實(shí)現(xiàn)的效率更高，雖然代碼的可讀性稍微差些。

當(dāng)一個(gè)問題相當(dāng)復(fù)雜，難以用迭代實(shí)現(xiàn)時(shí)，此時(shí)遞歸實(shí)現(xiàn)的簡(jiǎn)潔性便可以補(bǔ)償它所帶來的運(yùn)行時(shí)開銷

---

看到這里你應(yīng)該對(duì)于遞歸有了很深的理解吧！遞歸的學(xué)習(xí)是一個(gè)漫長的過程，畢竟大師 L. Peter Deutsch 說過：To Iterate is Human, to Recurse, Divine.中文譯為：人理解迭代，神理解遞歸。下篇我將會(huì)帶領(lǐng)大家研究幾個(gè)經(jīng)典的遞歸問題。

漢諾塔問題

青蛙跳臺(tái)階問題

如有補(bǔ)充或存在問題請(qǐng)?jiān)谠u(píng)論區(qū)留言喲~

總結(jié)

以上是生活随笔為你收集整理的C语言递归算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。