Python 遞迴

Python 中的函數可以呼叫自己，這就是遞迴。在許多情境中，遞迴是非常有用的。

通常用階乘計算來解釋遞迴。一個數字的階乘即是該數字 n 乘上 n-1，再乘上 n-2…，一直到達 1 為止：

3! = 3 × 2 × 1 = 6
4! = 4 × 3 × 2 × 1 = 24
5! = 5 × 4 × 3 × 2 × 1 = 120

利用遞迴，我們可以撰寫一個函數來計算任何數字的階乘：

def factorial(n):
 if n == 1: return 1
 return n × factorial(n-1)

print(factorial(3)) # 6
print(factorial(4)) # 24
print(factorial(5)) # 120

如果在 factorial() 函數內呼叫的是 factorial(n) 而不是 factorial(n-1)，將會導致無窮遞迴。Python 預設會在執行 1000 次遞迴後停止，當達到這個限制時，你將會得到一個 RecursionError 錯誤。

遞迴在許多情境中都很有幫助，它可以在沒有其他最佳解法的情況下簡化我們的程式碼，因此瞭解這個技巧是很好的。