目錄

• 【算法基礎(chǔ)】經(jīng)典例題說遞歸
• • 遞歸簡介
  • • 遞歸的適用范圍
    • 遞歸的基本思路
  • 經(jīng)典例題解析
  • • 移梵塔
    • • 題目描述
      • 題目分析
      • 題解
    • 九連環(huán)
    • • 題目描述
      • 題目分析
      • 題解
  • 更新日志

【算法基礎(chǔ)】經(jīng)典例題說遞歸

遞歸簡介

遞歸是一種編程技巧，一種解決問題的思維方式。通過函數(shù)的自我調(diào)用寫出簡潔漂亮、可解釋性強的代碼。

遞歸：參見遞歸。

遞歸的適用范圍

遞歸的思維方式適用于解決層層嵌套、層層相似的問題。要解決本層問題就需要先把上一層問題解決掉，而且每一層的解決方法與上一層的解決方法相似。（就像套娃一樣，一層套一層，每層都長得差不多）

生活中許多問題都滿足層層嵌套的特性。如漢諾塔、九連環(huán)的解法，謝爾賓斯基三角形的繪制，二進制數(shù)的進位…

拓展閱讀：
漢諾塔，二進制和謝爾賓斯基三角形（上）
漢諾塔，二進制和謝爾賓斯基三角形（下）

遞歸的基本思路

遞歸最重要的就是找到實現(xiàn)需求的過程中反反復(fù)復(fù)一直在執(zhí)行的核心操作是什么，并且找到和核心操作不太一樣的邊界操作，從而確定觸底條件。
（這個在觸底條件上，和核心操作不太一樣的操作，就像套娃里面最小的那個套娃，和別的大套娃不一樣，它肚子不開口。邊界操作不再自我調(diào)用。）

層層深入->觸底->層層返回

層層深入（核心操作的自我調(diào)用，增加遞歸深度）
觸底（不再自我調(diào)用，開始返回的分界點）
層層返回（return）

經(jīng)典例題解析

移梵塔

時間限制: 1 Sec 內(nèi)存限制: 64 MB

題目描述

有三根柱A、B、C，在A柱上有n塊盤片，所有盤片都是大片在下面，小片放在大片上面。并依次編好序號。現(xiàn)要將A上的n塊盤片移到C柱上，每次只能移動一片，而且在同一根柱子上必須保持上面的盤片比下面的盤片小，請輸出移動方法。

輸入
僅一個整數(shù)n(n≤20)，表示A柱上的盤片數(shù)。

輸出
輸出盤片的移動步驟。

樣例輸入
3

樣例輸出
A-1-C
A-2-B
C-1-B
A-3-C
B-1-A
B-2-C
A-1-C

題目分析

讀題可知漢諾塔的解法符合層層嵌套、層層相似的特性，故采用遞歸算法。
任意盤片堆都是由一個更小的小盤片堆加一片大盤片構(gòu)成的。想要讓這個盤片堆移動，就必須三步走：①先把小盤片堆移動到暫存柱上，②這樣大盤片才能移動到目標(biāo)柱，③最后小盤片堆移動到大盤片上。
因為在同一根柱子上必須保持上面的盤片比下面的盤片小，所以移動小盤片堆使小盤片堆離開初始柱的操作可以等價于移動小盤片堆中最大的盤片。
在這里比較特殊的是第一片盤片，它上面沒有其他盤片，可以自由移動。

核心操作：把小盤片堆從A柱移動到C柱

邊界操作：移動第一片盤片

觸底條件：正在移動的盤片是第一片盤片

題解

先放完整代碼（C語言）對整體算法有個宏觀理解：

#include <stdio.h>void hanoi(int num,char a,char b,char c){if(num==1){printf("%c-%d-%c\n",a,num,c);}else{hanoi(num-1,a,c,b);printf("%c-%d-%c\n",a,num,c);hanoi(num-1,b,a,c);} }int main() {int num;scanf("%d",&num);hanoi(num,'A','B','C');return 0; }

接著是注釋版本，可以對照理解：

#include <stdio.h>//hanoi()：第num片盤片從起始柱a移動到目標(biāo)柱c //b為盤片移動三步走中會用到的暫存柱 void hanoi(int num,char a,char b,char c){if(num==1){//當(dāng)前移動盤片為第一片盤片的時候直接移動就好啦printf("%c-%d-%c\n",a,num,c);/*↑【注意】↑只有一步所以直接打印了*/}else{//盤片移動三步走hanoi(num-1,a,c,b);//小盤片堆從起始柱移動到暫存柱（a->b）printf("%c-%d-%c\n",a,num,c);//大盤片從起始柱移動到目標(biāo)柱（a->c）/*↑【注意】↑只有一步所以直接打印了*/hanoi(num-1,b,a,c);//小盤片堆從暫存柱移動到目標(biāo)柱（b->c）} }int main() {int num;scanf("%d",&num);//讀入盤片總數(shù)numhanoi(num,'A','B','C');return 0; }

九連環(huán)

時間限制: 1 Sec 內(nèi)存限制: 64 MB

題目描述

九連環(huán)是由九個彼此套接的圓環(huán)和一根橫桿組成，九個環(huán)從左到右依次為l～9，每個環(huán)有兩種狀 態(tài)：1和0，1表示環(huán)在桿上，0表示環(huán)不在桿上。初始狀態(tài)是九個環(huán)都在桿上，即：111111111，目標(biāo)狀態(tài)是九個環(huán)都不在桿上，即：000000000，由初始狀態(tài)到目標(biāo)狀態(tài)的變化規(guī)則是：
(1)第一環(huán)為無論何時均可自由上下橫行；
(2)第二只環(huán)只有在第一環(huán)為1時，才能自由上下；
(3)想要改變第n(n>2)個環(huán)的狀態(tài)，需要先使第一到第(n-2)環(huán)均為下桿，且第n-1個環(huán)為上桿，而與第n+l個到第九環(huán)狀態(tài)無關(guān)；
(4)每改變一個環(huán)，記為一步。
現(xiàn)在九連環(huán)由111111111變到000000000，求中間第i步的狀態(tài)。

輸入
僅包含一個整數(shù)i。

輸出
僅包含中間第i步的狀態(tài)。如果輸入的步數(shù)大于實際變換所需的步數(shù)，則輸出-1。

樣例輸入
【樣例1】
2
【樣例2】
500

樣例輸出
【樣例1】
010111111
【樣例2】
-1

題目分析

讀題可知九連環(huán)的解法符合層層嵌套、層層相似的特性，故采用遞歸算法。

核心操作：解環(huán)

想要改變第n(n>2)個環(huán)的狀態(tài)，需要先使第一到第(n-2)環(huán)均為下桿，且第n-1個環(huán)為上桿，而與第n+l個到第九環(huán)狀態(tài)無關(guān)；

邊界操作：解第一個環(huán)

(1)第一環(huán)為無論何時均可自由上下橫行；

觸底條件：當(dāng)前在解的環(huán)是第一個環(huán)

分析解環(huán)過程，解環(huán)會對前面的環(huán)的狀態(tài)產(chǎn)生影響，但是不會對后面的環(huán)產(chǎn)生影響。所以從后往前解環(huán)才能把九連環(huán)解開。

題解

先放完整代碼（C語言）對整體算法有個宏觀理解：

#include <stdio.h>int step; int pos[10]={1,1,1,1,1,1,1,1,1,1};void turn(int num){if(step==0) return;if(pos[num-1]==0) turn(num-1);for(int i=num-2;i>=1;i--){if(pos[i]==1) turn(i);}if(step==0) return;pos[num]=(pos[num]+1)%2;step--; }int main() {scanf("%d",&step);for(int i=9;i>=1;i--){turn(i);}if(step==0){for(int i=1;i<=9;i++){printf("%d",pos[i]);}putchar('\n');}else if(step>0){puts("-1");}return 0; }

然后這里是非常非常詳細的注釋，看不懂可以對照著看：

#include <stdio.h>//step：操作步數(shù)，在turn()函數(shù)中倒數(shù)計數(shù) int step;//pos數(shù)組：記錄環(huán)的情況 /*【注意】只有九個環(huán)但是我開了10個位置 的數(shù)組，1~9才是記錄環(huán)的情況的，其中pos[0] 記錄的1是為了減少代碼量，避免第一個環(huán)的情況 需要單獨列出。*/ int pos[10]={1,1,1,1,1,1,1,1,1,1};//turn()函數(shù)：改變第num個環(huán)的狀態(tài)，套上或卸下 /*這個函數(shù)采用了遞歸的方法，但是它的觸底條件比較隱蔽， 仔細觀察可以發(fā)現(xiàn)當(dāng)num=1時函數(shù)就不再自我調(diào)用了， 它就是邊界操作。所以，num=1是觸底條件。*/ void turn(int num){/*當(dāng)步數(shù)走完就需要讓函數(shù)返回，不讓它再做其他什么操作使得結(jié)果改變*/if(step==0) return;//解環(huán)的預(yù)先操作，先讓當(dāng)前環(huán)前面的環(huán)滿足解環(huán)的條件if(pos[num-1]==0) turn(num-1);/*↑【注意】↑看這里！如果pos數(shù)組0~9存狀態(tài)，當(dāng)num=0就要單獨列出操作了，因為數(shù)組會溢出*/for(int i=num-2;i>=1;i--){if(pos[i]==1) turn(i);}/*預(yù)先操作過程中最后一步如果step已經(jīng)到達0，返回到上一層就會一直往下執(zhí)行，這樣step就會變成負數(shù)了。這樣可不行！趕緊把它return掉！>A<*/if(step==0) return;//解開當(dāng)前環(huán)，并記錄步數(shù)pos[num]=(pos[num]+1)%2;step--; }int main() {//讀入題目給出的步數(shù)scanf("%d",&step);//從后往前解環(huán)for(int i=9;i>=1;i--){turn(i);}//輸出答案/*(step==0) 步數(shù)走完了(step>0) 步數(shù)沒走完*/if(step==0){for(int i=1;i<=9;i++){printf("%d",pos[i]);}putchar('\n');}else if(step>0){puts("-1");}return 0; }

更新日志

2020-2-6
第一版完成！o(￣▽￣)ブ
只寫了兩題是因為我刷題刷得少orz
遞歸好難啊好難啊，想破腦殼殼QAQ
但是遞歸好神奇，本小白對它充滿喜歡，我一定要把遞歸這只小妖精抱緊緊！！！

總結(jié)

以上是生活随笔為你收集整理的【算法基础】经典例题说递归的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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