遞歸是編程中一個(gè)相對(duì)難以理解但是卻又很重要的概念. 對(duì)于從命令式語(yǔ)言開(kāi)始學(xué)習(xí)編程的程序員天生對(duì)此有理解缺陷, 而對(duì)于從類似C++這種對(duì)函數(shù)式編程范式不友好的語(yǔ)言開(kāi)始學(xué)習(xí)編程的程序員就更加如此了.(比如我自己) 碰巧(其實(shí)不巧)最近在讀這本書(shū)(這本書(shū)國(guó)內(nèi)沒(méi)有引進(jìn), 網(wǎng)上只有巨貴的亞馬遜賣的原版, 我讀的是網(wǎng)上的中文版), Paul Graham在書(shū)中講述的如何寫(xiě)遞歸函數(shù)的部分, 讓我印象深刻. 因?yàn)樵瓡?shū)是講Lisp的, 當(dāng)然這個(gè)部分也是用Lisp作為例子描述的, 考慮到國(guó)內(nèi)會(huì)看這本書(shū)的人太少, 能看懂Lisp的就更不多了, 我這里根據(jù)自己的理解, 重新整理一下. 最重要的是, 書(shū)中原來(lái)的例子太少, 太簡(jiǎn)單, 我自己提供了一些額外的, 并且更加復(fù)雜的例子. 以期對(duì)問(wèn)題能有更好的理解.
迭代的是人，遞歸的是神
–L. Peter Deutsch
簡(jiǎn)單的定義: “當(dāng)函數(shù)直接或者間接調(diào)用自己時(shí)竖般，則發(fā)生了遞歸.” 說(shuō)起來(lái)簡(jiǎn)單, 但是理解起來(lái)復(fù)雜, 因?yàn)檫f歸并不直觀, 也不符合我們的思維習(xí)慣, 相對(duì)于遞歸, 我們更加容易理解迭代. 因?yàn)槲覀內(nèi)粘Ｉ钪械乃季S方式就是一步接一步的, 并且能夠理解一件事情做了N遍這個(gè)概念. 而我們?nèi)粘Ｉ钪袔缀醪粫?huì)有遞歸思維的出現(xiàn).
舉個(gè)簡(jiǎn)單的例子, 即在C/C++中計(jì)算一個(gè)字符串的長(zhǎng)度. 下面是傳統(tǒng)的方式, 我們一般都這樣通過(guò)迭代來(lái)計(jì)算長(zhǎng)度, 也很好理解.
size_tlength(constchar*str){size_tlength=0;while(*str!=0){++length;++str;}returnlength;}
而事實(shí)上, 我們也可以通過(guò)遞歸來(lái)完成這樣的任務(wù).
size_tlength(constchar*str){if(*str==0){return0;}returnlength(++str)+1;}
只不過(guò), 我們都不這么做罷了, 雖然這樣的實(shí)現(xiàn)有的時(shí)候可能代碼更短, 但是很明顯, 從思維上來(lái)說(shuō)更加難以理解一些. 當(dāng)然, 我是說(shuō)假如你不是習(xí)慣于函數(shù)式語(yǔ)言的話. 這個(gè)例子相對(duì)簡(jiǎn)單, 稍微看一下還是能明白吧.
迭代的算法可以這樣描述: 從第一個(gè)字符開(kāi)始判斷字符串的每一個(gè)字符, 當(dāng)該字符不為0的時(shí)候, 該字符串的長(zhǎng)度加一.
遞歸的算法可以這樣描述: 當(dāng)前字符串的長(zhǎng)度等于當(dāng)前字符串除了首字符后, 剩下的字符串長(zhǎng)度+1.
作為這么簡(jiǎn)單的例子, 兩種算法其實(shí)大同小異, 雖然我們習(xí)慣迭代, 但是, 也能看到, 遞歸的算法無(wú)論是從描述上還是實(shí)際實(shí)現(xiàn)上, 并不比迭代要麻煩.
在初學(xué)遞歸的時(shí)候, 看到一個(gè)遞歸實(shí)現(xiàn), 我們總是難免陷入不停的回溯驗(yàn)證之中, 因?yàn)榛厮菥拖穹催^(guò)來(lái)思考迭代, 這是我們習(xí)慣的思維方式, 但是實(shí)際上遞歸不需要這樣來(lái)驗(yàn)證. 比如, 另外一個(gè)常見(jiàn)的例子是階乘的計(jì)算. 階乘的定義: “一個(gè)正整數(shù)的階乘（英語(yǔ)：factorial）是所有小于或等于該數(shù)的正整數(shù)的積搂捧，并且0的階乘為1冲泥』巢矗” 以下是Ruby的實(shí)現(xiàn):
deffactorial(n)ifn<=1thenreturn1elsereturnn*factorial(n-1)endend
我們?cè)趺磁袛噙@個(gè)階乘的遞歸計(jì)算是否是正確的呢? 先別說(shuō)測(cè)試, 我說(shuō)我們讀代碼的時(shí)候怎么判斷呢?
回溯的思考方式是這么驗(yàn)證的, 比如當(dāng)n = 4時(shí), 那么factoria(4)等于4 * factoria(3), 而factoria(3)等于3 * factoria(2),factoria(2)等于2 * factoria(1), 等于2 * 1, 所以factoria(4)等于4 * 3 * 2 * 1. 這個(gè)結(jié)果正好等于階乘4的迭代定義.
用回溯的方式思考雖然可以驗(yàn)證當(dāng)n = 某個(gè)較小數(shù)值是否正確, 但是其實(shí)無(wú)益于理解.
Paul Graham提到一種方法, 給我很大啟發(fā), 該方法如下:
當(dāng)n=0, 1的時(shí)候, 結(jié)果正確.
假設(shè)函數(shù)對(duì)于n是正確的, 函數(shù)對(duì)n+1結(jié)果也正確.
如果這兩點(diǎn)是成立的本砰，我們知道這個(gè)函數(shù)對(duì)于所有可能的n都是正確的蜒蕾。
這種方法很像數(shù)學(xué)歸納法, 也是遞歸正確的思考方式, 事實(shí)上, 階乘的遞歸表達(dá)方式就是1!=1及汉，n!=(n-1)!×n(見(jiàn)wiki). 當(dāng)程序?qū)崿F(xiàn)符合算法描述的時(shí)候, 程序自然對(duì)了, 假如還不對(duì), 那是算法本身錯(cuò)了…… 相對(duì)來(lái)說(shuō), n,n+1的情況為通用情況, 雖然比較復(fù)雜, 但是還能理解, 最重要的, 也是最容易被新手忽略的問(wèn)題在于第1點(diǎn), 也就是基本用例(base case)要對(duì). 比如, 上例中, 我們?nèi)サ鬷f n <= 1的判斷后, 代碼會(huì)進(jìn)入死循環(huán), 永遠(yuǎn)不會(huì)結(jié)束.
既然遞歸比迭代要難以理解, 為啥我們還需要遞歸呢? 從上面的例子來(lái)看, 自然意義不大, 但是很多東西的確用遞歸思維會(huì)更加簡(jiǎn)單……
經(jīng)典的例子就是斐波那契數(shù)列, 在數(shù)學(xué)上, 斐波那契數(shù)列就是用遞歸來(lái)定義的:
·F0 = 0
·F1 = 1
·Fn = Fn – 1 + Fn – 2
有了遞歸的算法, 用程序?qū)崿F(xiàn)實(shí)在再簡(jiǎn)單不過(guò)了:
deffibonacci(n)ifn==0thenreturn0elsifn==1thenreturn1elsereturnfibonacci(n-1)+fibonacci(n-2)endend
改為用迭代實(shí)現(xiàn)呢? 你可以試試.
上面講了怎么理解遞歸是正確的, 同時(shí)可以看到在有遞歸算法描述后, 其實(shí)程序很容易寫(xiě), 那么最關(guān)鍵的問(wèn)題就是, 我們?cè)趺凑业揭粋€(gè)問(wèn)題的遞歸算法呢?
Paul Graham提到, 你只需要做兩件事情:
你必須要示范如何解決問(wèn)題的一般情況, 通過(guò)將問(wèn)題切分成有限小并更小的子問(wèn)題.
你必須要示范如何通過(guò)有限的步驟, 來(lái)解決最小的問(wèn)題(基本用例).
如果這兩件事完成了, 那問(wèn)題就解決了. 因?yàn)檫f歸每次都將問(wèn)題變得更小, 而一個(gè)有限的問(wèn)題終究會(huì)被解決的, 而最小的問(wèn)題僅需幾個(gè)有限的步驟就能解決.
這個(gè)過(guò)程還是數(shù)學(xué)歸納法的方法, 只不過(guò)和上面提到的一個(gè)是驗(yàn)證, 一個(gè)是證明.
現(xiàn)在我們用這個(gè)方法來(lái)尋找漢諾塔這個(gè)游戲的解決方法.(這其實(shí)是數(shù)學(xué)家發(fā)明的游戲)
有三根桿子A沮趣，B，C坷随。A桿上有N個(gè)(N>1)穿孔圓盤房铭，盤的尺寸由下到上依次變小驻龟。要求按下列規(guī)則將所有圓盤移至C桿：
1.每次只能移動(dòng)一個(gè)圓盤.
2.大盤不能疊在小盤上面.
這個(gè)游戲在只有3個(gè)盤的時(shí)候玩起來(lái)較為簡(jiǎn)單, 盤越多, 就越難, 玩進(jìn)去后, 你就會(huì)進(jìn)入一種不停的通過(guò)回溯來(lái)推導(dǎo)下一步該干什么的狀態(tài), 這是比較難的. 我記得第一次碰到這個(gè)游戲好像是在大航海時(shí)代某一代游戲里面, 當(dāng)時(shí)就覺(jué)得挺有意思的. 推薦大家都實(shí)際的玩一下這個(gè)游戲, 試試你腦袋能想清楚幾個(gè)盤的情況.
現(xiàn)在我們來(lái)應(yīng)用Paul Graham的方法思考這個(gè)游戲.
一般情況:
當(dāng)有N個(gè)圓盤在A上, 我們已經(jīng)找到辦法將其移到C杠上了, 我們?cè)趺匆苿?dòng)N+1個(gè)圓盤到C杠上呢? 很簡(jiǎn)單, 我們首先用將N個(gè)圓盤移動(dòng)到C上的方法將N個(gè)圓盤都移動(dòng)到B上, 然后再把第N+1個(gè)圓盤(最后一個(gè))移動(dòng)到C上, 再用同樣的方法將在B杠上的N個(gè)圓盤移動(dòng)到C上. 問(wèn)題解決.
基本用例:
當(dāng)有1個(gè)圓盤在A上, 我們直接把圓盤移動(dòng)到C上即可.
算法描述大概就是上面這樣了, 其實(shí)也可以看作思維的過(guò)程, 相對(duì)來(lái)說(shuō)還是比較自然的. 下面是Ruby解:
defhanoi(n,from,to,other)ifn==1thenputsfrom+' -> '+toelsehanoi(n-1,from,other,to)hanoi(1,from,to,other)hanoi(n-1,other,to,from)endend
當(dāng)n=3時(shí)的輸出:
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
上述代碼中, from, to, other的作用其實(shí)也就是提供一個(gè)桿子的替代符, 在n=1時(shí), 其實(shí)也就相當(dāng)于直接移動(dòng). 看起來(lái)這么復(fù)雜的問(wèn)題, 其實(shí)用遞歸這么容易, 沒(méi)有想到吧. 要是想用迭代來(lái)解決這個(gè)問(wèn)題呢? 還是你自己試試吧, 你試的越多, 就能越體會(huì)到遞歸的好處.
當(dāng)然, 這個(gè)世界上沒(méi)有啥時(shí)萬(wàn)能的, 遞歸也不例外, 首先遞歸并不一定適用所有情況, 很多情況用迭代遠(yuǎn)遠(yuǎn)比用遞歸好了解, 其次, 相對(duì)來(lái)說(shuō), 遞歸的效率往往要低于迭代的實(shí)現(xiàn), 同時(shí), 內(nèi)存好用也會(huì)更大, 雖然這個(gè)時(shí)候可以用尾遞歸來(lái)優(yōu)化, 但是尾遞歸并不是一定能簡(jiǎn)單做到.
