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