python遞歸_Python遞歸（recursion）專題

我想把Python中的遞歸作為一個專題讨論一下。我在學習的時候，嘗試使用“Python遞歸”作為關鍵詞，在Google和百度中搜尋，發現結果大部分是對某個具體例子的遞歸應用讨論，而對我這樣的小白來說，切入點有點高。而我現在需要做的，是從基礎概念開始。

想到讨論遞歸問題，是因為那個著名的“字典序”問題，但還是先從最基本的遞歸概念開始。我希望我讨論完了這個，自己對遞歸也有一個基本的了解了。

遞歸的概念很簡單，如果函數包含了對其自身的調用，該函數就是遞歸的。拗口一點的定義是，如果一個新的調用能在相同過程中較早的調用結束之前開始，那麼個該過程就是遞歸。兩個定義都來自《Python核心程式設計第二版》的第304頁。

該書應用了一個經典的例子，來講述遞歸的應用：

階乘函數的定義是：

N! = factorial(N) = 1 * 2 * 3 * ... * N

那麼可以用這種方法來看階乘函數：

factorial(N) = N!

= N * (N - 1)!

= N * (N - 1) * (N - 2)!

= N * (N - 1) * (N - 2) * ... * 3 * 2 * 1

= N * factorial(N - 1)

于是我們有了階乘函數的遞歸版本：

def factorial(n):

if n == 0 or n == 1: return 1

else: return (n * factorial(n - 1))

print factorial(6)

可以很輕易的得到，6!的結果是720。

上面就是這本書關于遞歸的内容了，但關于Python的遞歸不僅僅就這麼一點知識吧？

來看看這個問題：

還是這個函數factorial(N)，讓我們試試N = 999和N = 1000，問題來了，N = 999時能輸出正确答案，但當N = 1000時，就出現下面的錯誤了：

RuntimeError: maximum recursion depth exceeded

于是，請記住，預設的Python有一個可用的遞歸深度的限制，以避免耗盡計算機中的記憶體。在我的電腦，這是1000。

接着再來看看在我的第一個遞歸程式中遇到的問題：

為了試試手，我打算寫一個簡單函數計算那個傳統的問題，1 + 2 + 3 + ... + 100，當然，必須使用遞歸來做：

我的腳本是這樣的，結果出錯了。

>>> def add(n):

... if n > 0: return n + add(n - 1)

...

>>> add(100)

Traceback (most recent call last):

File "", line 1, in ?

File "", line 2, in add

File "", line 2, in add

...

File "", line 2, in add

TypeError: unsupported operand type(s) for +: 'int' and 'NoneType'

上網問了之後，得知應該這樣寫這個腳本：

>>> def add(n):

... if n <= 0: return 0

... if n > 0: return n + add(n - 1)

...

>>> add(100)

5050

我本意想偷懶，在n小于等于零的時候，不傳回任何東西。但Pyhton所做的和我想的卻不一樣。如果一個Python函數被設計成不傳回任何東西，它會傳回None。

這裡插入一些關于遞歸的網方解釋，因為我是從網上搜到的這些内容：

（1）遞歸就是在過程或函數裡調用自身；

（2）在使用遞歸政策時，必須有一個明确的遞歸結束條件，稱為遞歸出口。

遞歸算法一般用于解決三類問題：

（1）資料的定義是按遞歸定義的。（比如Fibonacci函數）

（2）問題解法按遞歸算法實作。（回溯）

（3）資料的結構形式是按遞歸定義的。（比如樹的周遊，圖的搜尋）

遞歸的缺點：遞歸算法解題的運作效率較低。在遞歸調用的過程當中系統為每一層的傳回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等。

遞歸程式的基本步驟，來自上面這篇文章

每一個遞歸程式都遵循相同的基本步驟：

1.初始化算法。遞歸程式通常需要一個開始時使用的種子值（seed value）。要完成此任務，可以向函數傳遞參數，或者提供一個入口函數，這個函數是非遞歸的，但可以為遞歸計算設定種子值。

2.檢查要處理的目前值是否已經與基線條件相比對（base case）。如果比對，則進行處理并傳回值。

3.使用更小的或更簡單的子問題（或多個子問題）來重新定義答案。

4.對子問題運作算法。

5.将結果合并入答案的表達式。

6.傳回結果。

基線條件（base case）。基線條件是遞歸程式的最底層位置，在此位置時沒有必要再進行操作，可以直接傳回一個結果。所有遞歸程式都必須至少擁有一個基線條件，而且必須確定它們最終會達到某個基線條件；否則，程式将永遠運作下去，直到程式缺少記憶體或者棧空間。

自己總結了一下，要寫一個遞歸的程式，需要這樣做：

1.一個基線條件。請在遞歸函數的一開始就處理這個基線條件。

2.一系列的規則，使對遞歸函數的每次調用都趨進于直至達到這個基線條件。

好吧，現在看來，基本概念已經差不多了，在回到“字典序”問題之前，先看看這個全排列的問題。題目要求很簡單，輸入n個數，能自動列印出全排列（Permutation）。比如輸入1，2，3，那它的全排列就是123，132，213，231，312，321。

【參考】

在《Pyhon核心程式設計》第二版第209頁第八章練習 續 中，題8-6在函數findPrimeFactors中使用了遞歸，可以參考： http://www.cnblogs.com/balian/archive/2012/01/11/2318679.html