Python 遞迴函式
遞迴函式將複雜問題拆分為幾個較小的問題。你已熟悉迴圈或迭代。在某些情況下，遞迴可能是更好的解決方案。
在 Python 中，如果函式呼叫自身並具有終止條件，則該函式是遞迴的。為何需要終止條件？阻止該功能無限呼叫自身。
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 函式的情況下，函式將每個元素新增到變數 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 x (n-1)!,如果 n > 1 且 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)
但請記住，階乘函式的輸入仍然存在限制。因此，你應該明智地來使用遞迴。正如你現在瞭解的階乘問題，遞迴函式不是最佳解決方案。對於其他問題，例如遍歷目錄，遞迴可能是一個很好的解決方案。