Python 初學第八講— 遞迴. 遞迴Recursion：將大問題切成小問題

使用迴圈所寫的程式碼想法依舊不難，只是相較於遞迴的寫法而言，程式碼閱讀起來稍微不那麼直觀一些。

最後我們再來看一個同樣經典的例子，最大公因數 ... AboutccClubPython初學系列非典型程式人系列專案手把手教學sKiwithTalk系列所有文章Python初學第八講—遞迴遞迴Recursion：將大問題切成小問題Yu-HsuanChouFollowMar14,2019·13minread在解決問題時，我們經常會遇到無法輕鬆使用loop或是ifstatement就能處理的問題，像是走迷宮問題遇到死路時需要回到上一層計算、或是在解決河內塔問題時儘管操作相同，卻因為每次要進行操作的參數不同而需要寫重複的程式碼等等。

此時，一個經常被納入考慮的方法，就是利用遞迴的概念來撰寫一個函式。

如果你對於函式還不甚了解，歡迎參考Python初學第七講—函式來輔助在遞迴函式上的學習。

遞迴的基本概念有時我們解決一個問題的方法是將其拆解，再各自將小問題解決以後得到答案，這樣的概念我們稱之為“DivideandConquer”，中文稱為分治法。

遞迴這個方法就是依據此概念形成的：我們將一個龐大的問題切分成數個相似的中問題，然後將中問題再區分成許多小問題，再將這些小問題用同一個function解決，最終將這個大問題處理完，這個處理方式就稱作recursion。

在數學以及電腦科學的領域當中，當一個函式會在執行當中，會不斷地自己呼叫自己時，我們便認為這個函式具有遞迴的性質。

同時，為了避免函式永無止盡地自我呼叫(self-calling)，我們也需要設計一個明確的終止條件。

因此，我們便得到了設計一個遞迴函式的兩個重點：遞迴自我呼叫的方式以及結束呼叫的終止條件。

實作recursion函式以下我們將討論三個經典的遞迴問題，階乘、費氏數列以及最大公因數。

階乘Factorial階乘問題是我們從高中就學過的數學問題，n階n!代表的即是從1開始連乘直到n為止，意即n!=1x2x...xn。

當我們需要用程式來幫助我們寫出一個計算階乘的函式，大家可能會先想到的是迴圈，在這個函式當中，我們只需要一個n次的forloop就可以解決這個問題。

在函式當中設定一個變數用來記住目前的乘積，然後從1開始乘直到n為止，程式碼可能如下：deffactorial_loop(n):factor=1foriinrange(1,n+1):factor*=ireturnfactor執行結果如下：於此同時，我們也可以利用recursion來解決這個問題。

我們再重新檢視n階乘這個算式：n!=1x2x...x(n-1)xn如果我們將乘上n以前的乘積拿出來看：n!=[1x2x...x(n-1)]xn=(n-1)!xn不正是n-1階乘上n嗎！也就是說，我們想要得到n階，只要得到n-1階的乘積以後再乘上n即可。

以此類推，n-1階來自於n-2階乘上n-1、…、2階等於1階乘上2。

那麼1階呢？0階呢？這兩者從我們高中所學的數學可以得知，我們將兩者皆定義為1。

階乘到這裡是否有點眉目了呢？當我們想要求得n階乘，只需要找到n-1階的階乘，但此時我們就需要找到n-1階的答案，便需要轉而尋求n-2階…直到我們所要尋找的是1階為止。

如果我們使用數學式來將我們的問題釐清，可能會是如下的式子：0!=11!=1n!=n*(n-1)!,n>=1那我們該如何將剛才所說的事情寫成一個遞迴的程式碼呢？首先，我們要先思考，在甚麼條件底下我們不會繼續呼叫自己算出n-1階的答案呢？答案是n=1以及n=0的時候，我們已經將之定義為1了。

其他時候我們都需要呼叫自己算出n-1階的階乘用以乘上現在的n，而程式碼我們試寫如下：deffactorial(n):ifn==0orn==1:return1else:returnn*factorial(n-1)這個程式碼的閱讀上是不是比迴圈版本的容易理解了呢？factorial(n)這個函式的定義如下：參數n是1或0的話，就回傳1；不是的話就returnn乘上用n-1當作參數呼叫自己的回傳值，也就是factorial(n-1)。

看起來是不是和我們方才所列的數學式十分相似呢？執行結果如下：接著讓我們再來寫出下一個遞迴函式吧！費氏數列Fibonaccisequence費氏數列也是在傳達遞迴概念時，經常被提及的一個問題。

所謂的費波那契數列，指的是一個數列，每一項都等於他的前兩項的和，也就是說第n項等於第n-1項以及第n-2項的和。

費氏數列的數學式如下：f(0)=0,f(1)=1f(n)=f(n-1)+f(n-2),n>=2而我們的問題就是給定整數n，希望得到費氏數列第n項的值。

這一次我們不妨直接來構思該如何寫出這一個遞迴函式吧！首先，我們想要求得的是第n項的值，也就是我們的函式參數為整數n，它每一次都會呼叫以n-1為參數以及n-2為參數的函式，並且將他們的回傳值相加起來再return。

但若參數值為1或是0，根據費氏數列的定義，我們就要直接回傳1和0。

聽起來十分簡單，試寫程式碼如下：deffibonacci(n):ifn==0:return0elifn==1:return1else:returnfibonacci(n-1)+fibonacci(n-2)基本上與我們對於費氏數列數學式的理解相差無幾，執行結果如下：解釋完了遞迴的想法，不妨來思考要如何利用迴圈來解決同樣的問題吧！我們的程式碼可能長這個樣子：deffibonacci_loop(n):ifn==1orn==2:return1else:fib1=1fib2=1fib3=0foriinrange(2,n):fib3=fib1+fib2fib1=fib2fib2=fib3returnfib3對於要將前兩項加起的定義，我們使用兩個變數fib1以及fib2來記住，然後將fib3存取加起來的和，然後不斷往後推直到fib1和fib2分別等於第n-2項以及第n-1項。

如果這樣字面上解釋有些難以理解，不妨在自己嘗試的過程當中印出每一次的fib1、fib2、fib3，相信更能理解這一個函式的思維，而執行結果如下：使用迴圈所寫的程式碼想法依舊不難，只是相較於遞迴的寫法而言，程式碼閱讀起來稍微不那麼直觀一些。

最後我們再來看一個同樣經典的例子，最大公因數。

最大公因數GCD相信大家對於最大公因數的概念並不陌生，就是給定兩個整數，要求找到兩者共同的最大因數。

尋找的方法很多，有些人會從較小者每次減一然後進行檢查、有些人利用質因數分解來尋找答案，另一些人可能會使用一個特殊的方法——輾轉相除法。

如果你對於輾轉相除法的用法不甚了解，建議你可以去維基百科或是努力推廣數學知識的昌爸工作坊來了解一下他的使用方式。

將其方法解釋得簡單一點即是，每一次都用兩者間較小的數去對另一個數取餘數，然後再用這個餘數以及剛才我們所選的較小的數進行和方才相同的步驟。

不知道你有沒有注意到，輾轉相除法其實就是一個遞迴的方法，我們不斷的利用較小的數以及餘數來“呼叫”下一層，直到取得的餘數為零為止，代表我們找到了所要的答案。

基於此想法，我們試寫的函式如下：defgcd(m,n):ifn==0:returnmelse:returngcd(n,m%n)在能被整除以前，我們都會不斷地以目前被用於取餘數的數字以及取得的餘數來呼叫自己，終止條件即是整除，也就是取餘數等於零。

執行結果如下：遞迴的限制與複雜度問題在瞭解了遞迴的概念以及使用方式以後，讓我們來談一談遞迴函式的複雜度問題，以及隨之而來對於recursion的限制。

recursion的複雜度問題在了解了遞迴函式的概念以後，不知道大家是否也都有感受到遞迴有著理解上簡單明瞭，又可以縮短程式碼長度的好處。

那麼，為什麼在多數遞迴可以處理的問題當中，大家還是比較常使用迴圈而不是遞迴呢？再讓我們溫習一下剛才費氏數列的例子：#遞迴解deffibonacci(n):ifn==0:return0elifn==1:return1else:returnfibonacci(n-1)+fibonacci(n-2)我們可以看到，在程式碼當中，這一個函式呼叫了兩次自己。

但是與此同時，在進行下一層的計算以前，我們還要先記得等等下一層的函式回傳回來以後，我要將兩個回傳值相加。

也就是說，在參數為n時，我們呼叫了fibonacci(n-1)以及fibonacci(n-2)，並且在真的計算fibonacci(n-1)以及fibonacci(n-2)之前，還要先記住這裡要將他們加起來。

很顯然地，在這一個遞迴函式裡，我們在知道要計算fibonacci(n-1)+fibonacci(n-2)時，要等到將fibonacci(n-1)以及fibonacci(n-2)都計算完以後，再回來這裡將兩個回傳值相加起來。

但是電腦要怎麼知道等到得到回傳值以後，我們要將它相加呢？那就是因為電腦在看到fibonacci(n-1)+fibonacci(n-2)時就已經記住了等等要相加，才開始計算fibonacci(n-1)以及fibonacci(n-2)。

而這個“記住”的動作當然會花電腦的記憶體，等到函式得到回傳值以後再從記憶體當中拿出來。

也就是說，電腦在一層一層從參數為n、n-1、…一直計算到fibonacci(1)以前，需要記住n這麼多個加，除此之外，在其他的遞迴問題當中可能還會需要記住其他數字等等，總之需要將每一層的數值、操作等等都存在電腦暫時的記憶體當中。

除了遞迴本身需要記住每一層的資訊以外，有時我們還可能讓電腦做重複的事情。

同樣使用剛才費氏數列的例子，我們在計算第n項的值時需要計算第n-1項以及第n-2項的數值，而第n-1項的值又來自於n-2以及n-3項，第n-2項的計算又要用到第n-3項以及第n-4項…費氏數列遞迴示意圖然而，電腦並沒有聰明到記得你剛才想要計算f(n)的時候已經呼叫過f(n-2)了，在你呼叫f(n-1)時又會呼叫f(n-2)一次，因此光是f(n-2)這個函式就執行了兩次。

而f(n-3)更是在計算f(n-1)時被呼叫一次，然後在計算兩次f(n-2)時又被各自呼叫一次…更別提最後的f(1)、f(0)會被呼叫多少次了！而且這些函式所回傳的值也通通都會被存在記憶體裡直到同一層的函式都被執行完為止，因此佔用了大量的空間，而且經常會把曾經做過的事情又拿來重新做一遍，不只浪費時間，也浪費空間，造成了程式的不效率(inefficiency)。

接著讓我們比較一下迴圈的寫法吧！#迴圈解deffibonacci_loop(n):ifn==1orn==2:return1else:fib1=1fib2=1fib3=0foriinrange(2,n):fib3=fib1+fib2fib1=fib2fib2=fib3returnfib3在這一個迴圈的解法當中，只額外使用了三個整數的儲存空間，並且免去了呼叫其他函式的時間，也不用暫且記住這一個函式的數值以等待其他函式計算完成，更不用做完全相同的事情，這個loop完成的同時，這個函式也就基本上結束了。

用比較電腦科學的話來講，就是遞迴這樣的方法會增加時間複雜度(timecomplexity)：在這個費氏數列的例子底下，使用迴圈解時，隨著我們輸入的n變大m倍，也只是迴圈多跑m倍的次數而已，也就是說時間的增加是線性的(linear-time)；但是在遞迴解的情況底下，m倍的n所增加的時間可不只是m倍而已，而是指數增加(exponential-time)。

於此同時，遞迴的使用也會增加空間複雜度(spacecomplexity)。

recursion的使用限制最後，讓我們來談談recursion使用的限制吧！如同我們前面所說的，recursion的概念即是不斷地呼叫自已，電腦必須要利用記憶體先替你記住這一層的中間值，然後去下一層繼續進行計算，直到終止條件被滿足。

然而，萬一我們不小心參數過大、recursion設計不良使得終止條件一直沒有被滿足或是像方才所提的記住了太多重複的東西的話，電腦裡的計算資源不就通通都被recursion所佔滿了嗎？為了避免這件事情的發生，Python對於遞迴次數（或者可以稱之為深度）有所限制，也就是說，它透過限制呼叫遞迴函式的次數，來達成杜絕你的遞迴無止盡地跑下去這個可能性。

透過sys這個module當中的函式，我們可以了解到Python對於遞迴的限制次數是3000次。

假如你超過了這個次數的限制，可能會遇到RecursionError:maximumrecursiondepthexceeded這樣的error。

目前為止大家所撰寫的程式應該都還不需要、也不建議大家使用需要遞迴次數太多的函式，因此，如何增加其次數上限的方法我們在這裡就姑且不談。

小結最後，讓我們來總結一下遞迴這個讓人又愛又害怕的概念吧！基本上，大多數能被遞迴解決的問題，都可以找出迴圈解。

如果使用遞迴的概念解題，通常可以將艱難的問題用簡單的想法解決；但是使用迴圈來改寫的話，通常可以增進程式運行的效率。

有一句話是這麼說的：Toiterateishuman,torecursedivine.——L.PeterDeutschiterate的意思是迭代，或著目前來說我們可以用迴圈的想法來理解這個概念。

這句話想要表達的究竟是什麼呢？是指迴圈解較容易想出來，遞迴解需要靈光一現、相對需要思考嗎？還是想表達迴圈解在閱讀上顯得有些冗長不平易近人，遞迴解優美又簡潔？抑或是想比較兩者之間的什麼特質呢？總歸一句話，當我們在解決問題的同時，遞迴與迴圈的選擇值得我們深思。

我們是ccClub團隊，致力於讓Python成為大家的第二外語，希望能用淺顯易懂、循序漸進的方式，帶領新手一步步跨入程式設計的世界。

如果你喜歡這篇文章，請給我們1~10個掌聲。

如果你喜歡「Python初學」的教學系列文，請給我們11個以上的掌聲。

Facebook:ccClubPython讀書會ccClub自2016開始舉辦Python讀書會的我們，是致力於將程式語言變成大家的第二外語的團隊。

2K1BeginnerPython教學Python入門2K claps2K1ccClub自2016開始舉辦Python讀書會的我們，是致力於將程式語言變成大家的第二外語的團隊。

WrittenbyYu-HsuanChouFollowNTUEconomics|MicrosoftTechnologyCenterTAIccClub自2016開始舉辦Python讀書會的我們，是致力於將程式語言變成大家的第二外語的團隊。