遞回: 在函式的定義中，函式內部的陳述句呼叫函式本身，
1、遞回的原理
學習任何計算機語言程序中，“遞回”一直是所有人心中的疼，不知你是否聽過這個冷笑話：“一個面包，走著走著餓了，于是就把自己吃了”，
呵呵，
常理推斷，特別是解釋型語言，當程式執行函式內部的陳述句時，這個函式還沒有定義完，沒定義完怎么可以呼叫本身呢，
但實質上，當你執行函式內部的陳述句時，一定有函式外部的陳述句呼叫了這個函式，此時該函式的所有代碼和陳述句，已經在記憶體中形成了邏輯，這就是遞回函式的原理，
在Python當中很重要的就是遞回的使用，
2、遞回的玩法
牛叔語錄：人類創造出的任何復雜的概念，都是為了讓事情變得更簡單一些，
遞回是為了更好的解決，“自已定義自己”的數學或是哲學難題，
用好遞回，有2個、2個、2個（重要的事情說3遍）要點，必須要同時注意，下面請各位評委看我的表演，
(1) 認清自己
認清自己是遞回玩法的核心，與處理任何事情一樣，首先要問的就是：如何準確地定義好“當前要做的事情”，處理好這個問題，我們就已經成功了一半，
此處我們拿數學函式為例， 因為數學函式的定義有公式，顯而易見，它的意義就是根據變數來計算出結果，最容易被小白理解，栗子如下：
假設數學函式：
f(n) = (f(n-1) + 1)*2 ，告訴你f(1)=1，問f(10)是多少？
我們直接把這個f(n)定義成函式，并且計算f(10) 如下：
def f(n):
if n==1:
return 1
else:
return (f(n-1)+1)*2
print(f(10))
結果是1534，運行正確，恭喜你這是一道著名的數學難題，你竟然輕松解決了，原題這樣：
猴子有一堆桃子，每天吃前一天剩下的一半多1個，昨天吃完發現剩了1個，那么前10天它剩下多少個桃子？
我們公式中的n就表示前n天，公式結果就表示剩下了多少桃子，昨天的桃子y總比今天的x有這樣的關系：x = y/2 -1 所以：y=(x+1)*2，這個就是上面的公式，
在寫本遞回函式時，陳述句基本上照抄數學公式，我們不知道解題程序就能求出答案，真是太神奇了！只要定義好，遞回跑不了！慢著，別下結論，我們再看看如下的點，
（2）把握好方向
與上面的“猴子摘桃”同一個問題，原題我們改一下說法，問：
猴子第1天摘了一堆桃子吃了一半又多一個，第2天吃了剩下的一半又多一個，...，第10天早上時發現只有1個桃子了，問第1天摘了多少？這回我們把n設為第n天（而不是前n天）
與上面函式f類似，后項也是根據前項值來確定，為區別我們使用g()代表該函式:
g(n) = g(n-1)/2 -1 ，告訴你 g(10)=1，問g(1) 是多少？
牛叔說了，“只要定義好，遞回跑不了”，我們先不管三七二十一，照抄上面的數學公式，“迅速而又準確”地把g(n)函式用如下的代碼造了出來，如下：
def g(n):
if n==10:
return 1
else:
return g(n-1)/2 - 1
print(g(1))
運行后卻出現了如下的錯誤，提示遞回溢位！
這是怎么回事呢？因為我們還有第2個點，您沒有注意！
這個點就是 “要想遞回不出錯，開車方向不能錯”，這個方向是指: 程式求解的方向必須和定義的方向相同，
此處我們要根據n=10的結果來求n=1，方向是：后項(10)->前項(1)，而程式中翻譯的公式是 前項（n-1)->后項(n)，根據公式寫的程式，也只能完成公式的求解順序，即：n從小到大的推導，
所以此時如果求g(100)，結果是這樣的，完全沒有問題（但沒有任何意義）：
-2.0
所以此處要通過我們的智慧把這個公式，“顛倒”過來變成：
g(n-1) = (g(n)+1) * 2 => g(n) = (g(n+1)+1) * 2
這樣根據公式寫的代碼，就可以完成從后項（n+1)推導到前項（n)的功能了！
如果不理解，小學二年級的代數再看一遍，具體程式如下：
1 def g(n):
2 if n==10:
3 return 1
4 else:
5 return 2*(g(n+1)+1)
6
7 print(g(1))
終于得出了正確的結果，1534，答案和第1題一樣！猴子終于滿意了，10天的口糧有著落了，
3、分解質因數練習
小學生專用名詞，別給嚇住了，其實就是把數字分解成不能再分解的乘法，比如：8=2*2*2， 10 = 2*5，而不是 8 = 2 * 4 這種可以再分解的，
此遞回問題，是編程競賽常客，拿來練手比較合適，如下Python代碼，對于本問題的解答充分說明了遞回的方便之處，以分解了980這個整數為示例：
1 def defactor(N): #定義一個函式名稱為defactor，意義是回傳N的所有因子
2 for i in range(2,N): #從2開始試試
3 if N%i ==0: #如果試到i是N的因子的話，就回傳i的所有因子和N/i的所有因子 的串列
4 return defactor(i)+defactor(int(N/i))
5 else:#如果沒有試到就說明這個N是一個質數，就直接包含它的 串列
6 return [N]
7
8 print(defactor(980))
運行的答案是：
[2, 2, 5, 7, 7]
Bingo，在這里函式defactor(N)
（1）定義: 求出引數N所有因子的陣列，
（2）方向：整數 -> 最小的質數
首先，理解else:部分（代碼中的第5，6兩行），
這是函式的，把方向的部分，小牛叔稱他為：結果產生部分，它能確保程式不會跑偏的代碼，如果傳入的數字N沒有可以被整除的數字，即回圈到頭了，才會執行這個部分，每一個質數因子都會從這個部分產生，因為最終的結果只能是質數，下圖樹中的所有葉節點（沒有子節點的葉子：2，2，5，7，7），就是從這個部分產生的，當執行到這個部分時，程式不會再往向下遞回，所以不會產生下層的樹型結構，
再理解，遞回的部分（2，3，4行）
通過回圈來試因子，如果試到i是N的因子（即N可以被i整除）的話，就回傳i的所有因子和 N/i的所有因子 組成的串列，因此下圖中所有從上到下的兩個箭頭對，就代表著這兩個遞回呼叫，
通過這個樹形解題的程序，您會更加明白！
在整個程式遞回執行時，看起來是從頂980開始向下求解執行，而求解的程序中結果卻是從最下層的7，7開始向上匯集，
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/192010.html
標籤：Python
上一篇：Python3標準庫：collections容器資料型別
下一篇：數值運算_第1周