一、遞歸算法介紹
????????這篇文章講的是一個(gè)古老而又經(jīng)典的漢諾塔問題,他是遞歸算法的一個(gè)很好的應(yīng)用實(shí)例寻行。有關(guān)遞歸函數(shù)的介紹,在使用遞歸函數(shù)求解字符串的逆置問題文章中介紹過匾荆。遞歸思想是來解決可計(jì)算問題的拌蜘,他的根本特征在于逐步的計(jì)算和分解這一計(jì)算,通過將某一大問題不斷的分解成邏輯上相同的小問題牙丽,然后對小問題的求解進(jìn)而獲得最終的答案简卧。使用遞歸算法的程序在形式上往往都比較簡潔明了,這也正是他的價(jià)值所在烤芦。(更好地閱讀體驗(yàn)举娩,請?jiān)L問程序員在旅途)
計(jì)算機(jī)使用棧內(nèi)存結(jié)構(gòu)來從物理上實(shí)現(xiàn)遞歸算法,每一次的遞歸調(diào)用拍棕,系統(tǒng)都要將本次調(diào)用的返回地址晓铆、局部變量、形式參數(shù)等值壓入到棧中绰播,調(diào)用結(jié)束之后骄噪,再從棧頂取出保存的信息返回給相應(yīng)的變量并退出棧,再繼續(xù)執(zhí)行遞歸的上一層函數(shù)蠢箩。由于計(jì)算機(jī)系統(tǒng)給每一個(gè)程序分配的椓慈铮空間有限,因此谬泌,在使用遞歸求解問題的時(shí)候滔韵,一定要注意遞歸的深度,如果遞歸的次數(shù)太多掌实,很可能會出現(xiàn)棧溢出的情況陪蜻,導(dǎo)致問題求解失敗。
二贱鼻、漢諾塔問題
2.1 問題由來
相傳在古印度圣廟中宴卖,有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上邻悬,有三根桿(編號A症昏、B、C)父丰,在A桿自下而上肝谭、由大到小按順序放置64個(gè)金盤。游戲的目標(biāo):把A桿上的金盤全部移到C桿上,并仍保持原有順序疊好攘烛。操作規(guī)則:每次只能移動(dòng)一個(gè)盤子魏滚,并且在移動(dòng)過程中三根桿上都始終保持大盤在下,小盤在上坟漱,操作過程中盤子可以置于A栏赴、B、C任一桿上.
漢諾塔柱子.png
2.2 問題分析
????????漢諾塔問題是一種多分支的遞歸解法靖秩,相對于單分支的遞歸解法(如:階乘的遞歸解法)來說,不太容易理解竖瘾,但是只要把握住遞歸的思想核心就能夠理解這個(gè)程序的邏輯沟突。漢諾塔解法總結(jié)起來有三步驟:
1) 把 N-1個(gè)盤子 移到中轉(zhuǎn)柱
2)把第N個(gè)盤子移動(dòng)到 目標(biāo)柱
3)把中轉(zhuǎn)柱上面的N-1個(gè)盤子借助目前空閑的柱子 移動(dòng)到 目標(biāo)柱。
????????注意捕传,上面的中轉(zhuǎn)柱惠拭,起始柱,是會變化的庸论。每一層遞歸的邏輯都是职辅,借助"目標(biāo)柱子",將n-1個(gè) 盤子移動(dòng)到 "中轉(zhuǎn)柱"聂示,然后再將最后一個(gè)盤子移動(dòng)到"目標(biāo)柱子"域携,再將中轉(zhuǎn)柱上的盤子按照同樣的規(guī)律移動(dòng)到"目標(biāo)柱子"。
無論有多少盤子鱼喉,在移動(dòng)的過程中秀鞭,都是遵循上面的三個(gè)步驟。在移動(dòng)第N個(gè)盤子的時(shí)候扛禽,我們總得要想辦法把前面N-1個(gè)盤子移到中轉(zhuǎn)柱锋边,然后才能將第N個(gè)盤子移到目標(biāo)柱。在移動(dòng)第N-1個(gè)盤子的時(shí)候编曼,也是得要把前面N-2個(gè)盤子移到中轉(zhuǎn)柱豆巨,然后才能把第N-1個(gè)盤子移到目標(biāo)柱。所以掐场,你可以看到往扔,移動(dòng)N、N-1刻肄、N-2···號盤子到目標(biāo)柱的思路是一樣的瓤球,因此,我們可以用遞歸的思想解決這個(gè)問題敏弃。
2.3 程序?qū)崿F(xiàn)
#include<stdio.h>
void hnt(int n, char a, char b, char c){
if(n == 1){ // 遞歸出界條件
printf("%c -- > %c \n", a,c);
}else{
/*
每一層遞歸的邏輯都是卦羡,借助"目標(biāo)柱子",將n-1個(gè) 盤子移動(dòng)到 "中轉(zhuǎn)柱",然后再將最后一個(gè)盤子移動(dòng)到"目標(biāo)柱子".
注意绿饵,這里的中轉(zhuǎn)柱是會變化的欠肾。
*/
hnt(n-1,a,c,b); // ① 借助 c 柱子將a柱子上的n-1個(gè)盤子 移動(dòng)到 b 柱子上
printf("%c -- > %c \n", a,c); // ② 將 a柱子上的第n個(gè)盤子 移動(dòng)到 c柱子上
hnt(n-1, b,a,c); // ③ 將在b柱子上的n-1個(gè)盤子,借助 a 柱子(此時(shí)a空閑) 移動(dòng)到 c 柱子上
}
}
int main(){
int n;
scanf("%d", &n);
hnt(n,'a','b','c');
return 0;
}
2.4 程序分析
????????通過對漢諾塔問題的分析拟赊,你或許會明白刺桃,上面的程序是可以求解出問題的答案,但是你可能會有一些疑惑吸祟,為什么上面的程序瑟慈,可以記錄下每一步的移動(dòng)過程?對于這種多分支的遞歸算法來說屋匕,如果像理解單分支遞歸那樣葛碧,在腦海中盡可能的窮舉出每一步的移動(dòng)過程,有時(shí)候是很困難的过吻,這樣也不符合用遞歸解決問題的原則进泼。但是如果我們實(shí)在是想搞明白這每一步具體的過程,怎么辦呢纤虽?下面用歸納總結(jié)的方式乳绕,來列出N∈[1,4]的移動(dòng)過程,分析他的移動(dòng)規(guī)律逼纸。
當(dāng)N =1時(shí):
當(dāng)N =2時(shí):
當(dāng)N =3時(shí):
通過N=1洋措,N=2的求解,我們可以推斷出樊展,N =3的時(shí)候呻纹,會有 3 + 1 + 3 = 7次移動(dòng)。3個(gè)盤子的話专缠,我們得要先把前兩個(gè)盤子移到B雷酪,然后把第三個(gè)盤子移到C,最后再把B上面的兩個(gè)盤子涝婉,借助A移動(dòng)到C哥力。上面的兩個(gè)盤子,先是移動(dòng)到B墩弯,然后又移動(dòng)到C吩跋,這兩個(gè)過程,需要的移動(dòng)次數(shù)是一樣的渔工,移動(dòng)邏輯也是一樣的锌钮。
當(dāng)N =4時(shí):
還是前面的邏輯,N=4的時(shí)候引矩,會有 7 + 1 + 7 = 15次移動(dòng)梁丘。思路和前面一樣侵浸, 把前3個(gè)盤子,借助C移到B氛谜,再把第四個(gè)盤子移到C掏觉。
????????通過前面的幾個(gè)演示能看得出來,求解 N 和求解 N-1 的思路完全一致值漫,這是保證可以使用遞歸算法的核心所在澳腹。
A、B杨何、C只是形式上的標(biāo)注酱塔,本質(zhì)上面的意義是,起始危虱、中轉(zhuǎn)延旧、目標(biāo)。在移動(dòng)過程中槽地,如果要保證小的在上,大的在下芦瘾,我們就必須得要借助中轉(zhuǎn)捌蚊,才可以實(shí)現(xiàn),至于中轉(zhuǎn)是誰近弟,這和(N-1)這一堆盤子所在的位置有關(guān)缅糟。
在寫遞歸程序的時(shí)候,需要注意的點(diǎn)如下圖所示:
三祷愉、總結(jié)
????????遞歸算法的核心在于遞推邏輯窗宦,因此,使用遞歸算法求解問題二鳄,我們不必要糾結(jié)每一層函數(shù)的具體操作是什么樣子的赴涵,而要把核心放在邏輯上,如果問題的求解是可歸納的订讼,有遞推關(guān)系在里面髓窜,并且是可計(jì)算的,那么邏輯上就不存在問題欺殿,一般也就可以使用遞歸算法來求解寄纵。
遞歸有單分支的遞歸和多分支遞歸,單分支相對來說簡單理解一些脖苏,比如下面的遞歸程序
int f(int n) //求n的階乘
{
int fac;
if (n == 0 || n == 1)
fac = 1;
else
fac = f(n - 1) * n;
return fac;
}
????????多分支的如漢諾塔恍涂、二叉樹遍歷等诊沪,就比較難理解一些,但是思想是一樣的。
計(jì)算機(jī)執(zhí)行遞歸程序的時(shí)候,對每一層函數(shù)的調(diào)用鹤树,是使用棧數(shù)據(jù)結(jié)構(gòu)來進(jìn)行現(xiàn)場保護(hù)的,因此在編寫遞歸程序的時(shí)候,要注意遞歸的深度至扰,防止出現(xiàn) Stack Overflow 異常。