遞歸的各種例子： “要理解遞歸，你必須先了解遞歸”，“一個人他的母親是人類”。你可能想知道，這是與編程有毛線關係？
您可能要拆一個複雜的問題分解成幾個較小的塊。如果已經熟悉了循環或迭代，但在某些情況下，遞歸可能是一個更好的解決方案。在Python中，函數如果它調用自己，具有終止條件就是遞歸。為什麼終止條件？調用自己時可能無法終止。
遞歸與列表
讓我們先從一個非常簡單的例子：增加所有數字在列表中。無需遞歸，這可能是：#!/usr/bin/env python
def sum(list):
sum = 0
# Add every number in the list.
for i in range(0, len(list)):
sum = sum + list[i]
# Return the sum.
return sum
print(sum([5,7,3,8,10]))
我們在這裡隻需調用 sum 函數，該函數將每個元素的變量相加之後的總和並返回。要做到這一點也可用遞歸：
#!/usr/bin/env python
def sum(list):
if len(list) == 1:
return list[0]
else:
return list[0] + sum(list[1:])
print(sum([5,7,3,8,10]))
如果列表的長度為1則返回列表（終止條件）。否則，它返回元素和調用函數 sum() 減去列表中的一個元素。如果所有調用執行時，它返回達到終止條件，並返回結果（答案）。
階乘遞歸
階乘的數學定義是： n! = n * (n-1)!, 如果 n > 1 and f(1) = 1. 例如: 3! = 3 x 2 x 1 = 6. 我們可以在 Python 使用遞歸函數實現這一點：
#!/usr/bin/env python
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print factorial(3)
當調用階乘函數 n = 3. 那麼返回：n * factorial(n-1). 這一過程將持續直到 n = 1. 如果 n==1 ，這將返回結果。
遞歸的限製
每當一個函數調用自身並存儲一些內存。 因此，一個遞歸函數比傳統的函數需要更多的內存。 Python會在 1000 次調用的深度後停止函數調用。如果運行下麵這個例子：#!/usr/bin/env python
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print factorial(3000)
會得到錯誤如下：
RuntimeError: maximum recursion depth exceeded
在其他編程語言，程序可以簡單地崩潰。可以通過修改的遞歸調用次數來解決此問題：
#!/usr/bin/env python
import sys
sys.setrecursionlimit(5000)
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)
print factorial(3000)
但要記住仍有限製階乘函數的輸入。出於這個原因，應該明智地使用遞歸。正如現在了解到的階乘問題，遞歸函數不是最好的解決方案。 對於其他問題，如遍曆目錄，遞歸可能是一個很好的解決方案。
