/

Python 遞迴

Python 遞迴

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

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

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

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

1
2
3
4
5
6
7
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 錯誤。

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