python之遞歸實現

一、遞歸函數

概念：遞歸演算法是一種直接或者間接的調用自身演算法的過程。在電腦編寫程式中，遞歸演算法對解決一大類問題是十分有效的。

特點：

①遞歸就是在過程或者函數里調用自身。

②在使用遞歸策略時，必須有一個明確的遞歸條件，稱為遞歸出口。

③遞歸演算法解題通常顯得很簡潔，但遞歸演算法解題的效率較低。所以一般不倡導使用遞歸演算法設計程式。

④在遞歸調用的過程當中系統的每一層的返回點、局部變數等開闢了棧來存儲。遞歸函數次數過多容易造成棧溢出等。

   所以一般不倡導用遞歸演算法設計程式。

要求：

遞歸演算法所體現的"重覆"一般有三個條件：

①每次在調用規模上都有所縮小（通常是減半）。

②相鄰兩次重覆之間有緊密的聯繫，前一次要為後一次做準備（通常前一次的輸出就作為後一次的輸入）。

③在問題的規模極小時必須用直接接觸解答而不再進行遞歸調用，因而每次遞歸調用都是有條件的（以規模未達到直接解答的大小為條件），

   無條件的遞歸調用將會成為死迴圈而不能正常結束。

 1 """非遞歸方式呈現"""
 2 sum = 0
 3 for obj in range(1,101):
 4     sum+=obj
 5 print sum
 6 
 7 """"1+2+3+...+100"""
 8 def foo(n):
 9     if n>0:return n+foo(n-1)
10     if n<=0:return 0
11 print foo(100)
12 
13 """階乘"""
14 def fac(n):
15     if n==0 or n==1:
16         return 1
17     else:
18         return n*fac(n-1)
19 print fac(10)   

遞歸演算法一般用於解決三類問題：
（1）數據的定義是按遞歸定義的。（比如Fibonacci函數）
（2）問題解法按遞歸演算法實現。（回溯）
（3）數據的結構形式是按遞歸定義的。（比如樹的遍歷，圖的搜索，二分法查找等）