相信很多初學的伙伴對遞歸是又愛又恨，遞歸能很輕松的解決一些復雜問題，但是理解起來太過抽象，對新手小白很不友好，今天這篇博客就讓我來為大家分享一下我學習遞歸的心得和在學習過程中的一些誤區，希望這篇博客能夠幫到你；

? ? ? ? ? ? ?因為自己淋過雨，所以也想為別人撐傘！

要理解遞歸首先要明白什么是遞歸？

遞歸，在計算機科學中是指一種通過重復將問題分解為同類的子問題而解決問題的方法。

這只是網上隨便都能搜到的官方解釋，對很多伙伴幫助并不大，該懵逼還是懵逼，那我們不妨從俗套的現實問題中理解遞歸微妙的過程：

? ?你想將心儀已久的女神拿下，女神很喜歡編程，這個時候你想將自己的女神追到手要會編程吧（有共同話題才能有機會嘛）但是會編程必須得學數據結構和算法，學數據結構和算法又必須得會一門語言，學習語言要了解它基本的語法，在語法之下我們應該去好好了解計算機的底層操作原理，一但掌握底層操作原理后我們就可以往回一步一步的去實現我們的目標，最后成為編程大牛拿下女神！

當然還有一種情況，女神可能對你并不會設置跳出條件，就算你是編程大牛了也不會做你女朋友，有些兄弟可能在這個過程中不斷的尋找讓她回心轉意的條件，這樣注定沒有結果的死循環就是死遞歸；

讓我們回到計算機中，正確的遞歸一定有兩個條件，有這兩個條件不一定對，但沒有這兩個條件一定是錯誤的遞歸：

1.遞歸一定有一個跳出的條件，當達到這個條件的時候將不會遞下去了，而是歸來；

2.每次遞歸一定是逐漸接近這個跳出條件的；

我們來看編程中遞歸的例子：

輸入一個整數n如何打印它的每一位數字？

我們想要得到n的每個數字可以用這樣的方法

n = 1234 ，那么 n%10=4，我們就得到了n的個位數4

n/10=123，n%10=3，給n除10我們就得到了123，123再模10我們就得到了n的十位數3

以此類推我們分別就能得到n的所有位數了

如何用遞歸實現？

首先我們寫一個函數reverse來實現這個問題：

void reverse(int n) {//我們先打印n的個位數printf("%d",n%10);}

我們可以將這個問題拆解成打印（n/10）的每個位數加上打印n%10的結果，就像剝洋蔥一樣一層一層的把問題簡化，這就是遞歸的一大特點每次調用逐漸接近問題源頭

void reverse(int n) {//開始調用自己reverse( n/10);printf("%d",n%10);}

將n/10傳參給reverse函數就是將問題剝離一層重新提出一個如何將123分別打印的問題，在這樣不斷的調用下當n終于被除成0的時候說明n已經沒有位數可以截取下來的，這個就是我們的限制條件

void reverse(int n) {if (n != 0)//給上我們的限制條件{reverse( n/10);//n不斷接近我們的限制條件printf("%d ", n % 10);}}

當n等于0，函數就不會遞下去了，而是歸來，這是一個抽象的過程，除了我們的兩大基本條件外，其他條件就是決定我們要執行的結果??

void reverse(int n) {if (n != 0)//給上我們的限制條件{reverse( n/10);//n不斷接近我們的限制條件printf("%d ", n % 10);//決定我們要執行怎樣的代碼，如果這段代碼放在函數調用之前//會產生怎樣的代碼，我們一定要思考這個問題}}

?經過思考，我們知道調整printf的位置在調用函數之前我們的結果就會是倒著打印n，所以我們要掌握這種解題思路，根據問題能做出相應的調整才能更好的使用遞歸

經典漢諾塔遞歸問題：

漢諾塔是一個非常具有代表性的遞歸問題，遞歸在這里體現的非常精妙，看完后你一定會對遞歸有一個更深層次的理解

漢諾塔又稱河內塔，相傳在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。. 印度教的主神 梵天 在創造世界的時候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。. 不論白天黑夜，總有一個僧侶在按照下面的法則移動這些金片：一次只移動一片，不管在哪根針上，小片必須在大片上面。. 僧侶們預言，當所有的金片都從梵天穿好的那根針上移到另外一根針上時，世界就將在一聲霹靂中消滅，而 梵塔 、廟宇和眾生也都將同歸于盡。. 不管這個傳說的可信度有多大，如果考慮一下把64片金片，由一根針上移到另一根針上，并且始終保持上小下大的順序。.

問有三個柱子x y z，x上有n個由小到大的盤子，一次只能移動一個盤子，并且每次移動盤子小的必須在大盤子上面,怎么才能將x柱子上的所有盤子移動到z柱子上？

沒玩過漢諾塔游戲的可以進鏈接試玩一下：漢諾塔,漢諾塔游戲在線玩_7k7k益智游戲_7k7k小游戲

多玩幾遍我們發現它是有規律，這個規律我們抽象的分為以下三個步驟：

1.首先要將n-1個盤子借助z柱子將他們放到y柱子上；

?2.此時x柱子上面只剩下了第n個盤子，將第n個盤子直接移動到z柱子上面；

3.當最大的盤子移動到z柱子上了我們就不要管它了，現在我們重新復盤我們的問題，是不是在原問題上變成了如何將y柱子上的n-1個盤子經由x柱子移動到z柱子上面，和原問題一模一樣，只是盤子個數削減了還有柱子參數不一樣而已

?漢諾塔的思想就是這樣三步抽象的過程，那我們用代碼來實現它：

#define _CRT_SECURE_NO_WARNINGS #include<stdio.h> void move(char pa1, char pa2) {printf("%c -> %c \n",pa1,pa2); } void Hanoi(int n, char x, char y, char z) {if (n == 1)//當盤子為一個直接從x移動到z{move(x, z);//寫一個打印函數}else{Hanoi(n - 1, x, z, y);//將n-1個盤子從x經由z移動到ymove(x, z);// 將x上的最后一個盤子直接移動到zHanoi(n - 1, y, x, z);//將n-1個盤子從y經由x移動到z} } int main() {char x = 'x';char y = 'y';char z = 'z';int n = 0;scanf("%d", &n);Hanoi(n, x, y, z);return 0; }

核心代碼就是這一小段代碼：

? ? ? ? Hanoi(n - 1, x, z, y);? ? ? ?----->? ? ? ? ? ?//將n-1個盤子從x經由z移動到y
?? ??? ?move(x, z);? ? ? ? ? ? ? ? ? ? ??----->? ? ? ? ? ?// 將x上的最后一個盤子直接移動到z
?? ??? ?Hanoi(n - 1, y, x, z);? ? ? ? ?----->?? ? ? ? ?//將n-1個盤子從y經由x移動到z

這三個代碼就代表漢諾塔的三個抽象步驟,其實我當時到這里還是非常的懵逼，它怎么就會知道盤子該如何如何移動，就憑這幾段代碼，太不可思議了！? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 下面我就給大家分享一個知乎上叫Fireman A用戶的評論

作者：Fireman A
鏈接：https://www.zhihu.com/question/24385418/answer/257751077
來源：知乎
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。
?

對遞歸的理解的要點主要在于放棄!

放棄你對于理解和跟蹤遞歸全程的企圖，只理解遞歸兩層之間的交接，以及遞歸終結的條件。

想象你來到某個熱帶叢林，意外發現了十層之高的漢諾塔。正當你苦苦思索如何搬動它時，林中出來一個土著，毛遂自薦要幫你搬塔。他名叫二傻，戴著一個草帽，草帽上有一個2字，號稱會把一到二號盤搬到任意柱。

你靈機一動，問道：“你該不會有個兄弟叫三傻吧？”
“對對，老爺你咋知道的？他會搬一到三號盤。“
”那你去把他叫來，我不需要你了。“
于是三傻來了，他也帶著個草帽，上面有個3字。

你說：”三傻，你幫我把頭三個盤子移到c柱吧。“
三傻沉吟了一會，走進樹林，你聽見他大叫：”二傻，出來幫我把頭兩個盤子搬到C!“

由于天氣炎熱你開始打瞌睡。朦朧中你沒看見二傻是怎么工作的，二傻干完以后，走入林中大叫一聲：“老三，我干完了!”

三傻出來，把三號盤從A搬到B，然后又去叫二傻：“老二，幫我把頭兩個盤子搬回A!”

余下的我就不多說了，總之三傻其實只搬三號盤，其他叫二傻出來干。最后一步是三傻把三號盤搬到C，然后呼叫二傻來把頭兩個盤子搬回C

事情完了之后你把三傻叫來，對他說：“其實你不知道怎么具體一步一步把三個盤子搬到C，是吧？”

三傻不解地說：“我不是把任務干完了？”

你說：“可你其實叫你兄弟二傻干了大部分工作呀？”

三傻說：“我外包給他和你屁相干？”

你問到：“二傻是不是也外包給了誰？“

三傻笑了：“這跟我有屁相干？”

你苦苦思索了一夜，第二天，你走入林中大叫：“十傻，你在哪？”

一個頭上帶著10號草帽的人，十傻，應聲而出：“老爺，你有什么事？”

“我要你幫把1到10號盤子搬到C柱“

“好的，老爺。“十傻轉身就向林內走。

“慢著，你該不是回去叫你兄弟九傻吧“

“老爺你怎么知道的？“

“所以你使喚他把頭九個盤子搬過來搬過去，你只要搬幾次十號盤就好了，對嗎？“

“對呀！“

“你知不知道他是怎么干的？“

“這和我有屁相干？“

你嘆了一口氣，決定放棄。十傻開始干活。樹林里充滿了此起彼伏的叫聲：“九傻，來一下！“ “老八，到你了！““五傻！。。。“”三傻！。。。“”大傻！“

你注意到大傻從不叫人，但是大傻的工作也最簡單，他只是把一號盤搬來搬去。

若干年后，工作結束了。十傻來到你面前。你問十傻：“是誰教給你們這么干活的？“

十傻說：“我爸爸。他給我留了這張紙條。”

他從口袋里掏出一張小紙條，上面寫著：“照你帽子的號碼搬盤子到目標柱。如果有盤子壓住你，叫你上面一位哥哥把他搬走。如果有盤子占住你要去的柱子，叫你哥哥把它搬到不礙事的地方。等你的盤子搬到了目標，叫你哥哥把該壓在你上面的盤子搬回到你上頭。“

你不解地問：“那大傻沒有哥哥怎么辦？“

十傻笑了：“他只管一號盤，所以永遠不會碰到那兩個‘如果’，也沒有盤子該壓在一號上啊。”

但這時他忽然變了顏色，好像泄漏了巨大的機密。他驚慌地看了你一眼，飛快地逃入樹林。

第二天，你到樹林里去搜尋這十兄弟。他們已經不知去向。你找到了一個小屋，只容一個人居住，但是屋里有十頂草帽，寫著一到十號的號碼。

我看完后受到不少幫助，確實我們的思維有時候很執拗，非要跟蹤全局，越是這樣遞歸越是能把你繞暈，相反按照這個老哥的思路揭下遞歸的面具，面具之下也是一張普通的臉，當然遞歸的熟練不是幾篇博客能夠解決的，知識的熟練沒有捷徑可走，大家下來一定還是要多看多練。

接下來我們來看一個遞歸和非遞歸解決第n個斐波那契數列的問題：

每個斐波那契數列都是前兩個斐波那契數之和，1? ?1? ?2? ??3? ? 5? ? ?8? ? ?13?? ? 21? ?? 34 ...........? ? ? ??

int Fibonacci(int n) //非遞歸 {if (n < 3) //當n小于3時，前兩個數列一定是1{return 1;}int tmp1 = 1;//定義第一個數列int tmp2 = 1;//定義第二個數列int snm = 0; //定義一個數將第一.二個數列相加while (n > 2){snm = tmp1 + tmp2;tmp1 = tmp2;tmp2 = snm;n--;}return snm; }

int Fibonacci(n) //遞歸 {if (n < 3){return 1;}return Fibonacci(n - 1) + Fibonacci(n - 2); }

看上去遞歸的代碼好像很簡短，其實在遞歸內它進行了大量的重復計算，效率遠遠不及非遞歸的寫法，遞歸將一個主問題不斷的分成兩個遞歸子問題，子問題又不斷的將分成兩個更小的問題，這樣反復下去，問題就變復雜很多了

有沒有發現，圖片中有很多重復計算的過程，如果我是求第50個斐波那契數列呢？重復的過程可以超過千萬，就算是計算機也要不少時間才能計算完，這樣的效率我們是不能認可的，所以并不是所有的問題都要去用遞歸解決，要切合實際開發，靈活的運用遞歸；

另外肌肉是鍛煉出來的，運動指南永遠只是輔助而已，你不行動起來肌肉如何憑空長出來！

總結

以上是生活随笔為你收集整理的递归思想如何理解？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。