Python 遞迴函式
Jinku Hu
2023年1月30日
我們這節來學習 Python 遞迴函式。
什麼是 Python 遞迴函式
遞迴函式是一個呼叫自身的函式，這個過程稱為函式遞迴。比如，讓我們計算數字 6 的階乘。
6 * 5 * 4 * 3 * 2 * 1
在以下程式碼中，我們建立了一個遞迴函式，用來計算某個數字的階乘。
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
a = 6
print("Factorial of", a, "=", fact(a))
Factorial of 6 = 720
函式 fact(n) 是一個遞迴函式，它用引數 n-1 呼叫自身，直到引數變為 1 為止，這就是計算階乘的方法，即將數字乘以比這數字小 1 的數的階乘，fact(n)=n*fact(n-1)，就得到了這個數字的階乘。
在這個遞迴函式中，有一個結束條件，當數字變為 1 時，返回 1，不再繼續呼叫函式自身，這樣遞迴呼叫就是有限次數的呼叫。
在建立遞迴函式時，必須有一個這樣的結束條件來終止遞迴呼叫。
遞迴次數限制
也許你已經注意到了，每次函式呼叫自身時，都需要一些記憶體來儲存一些中間值。因此，遞迴函式比正常的非遞迴函式消耗更多的記憶體。Python 將遞迴呼叫次數限制設定為 3000。
>>> import sys
>>> sys.getrecursionlimit()
3000
如果遞迴次數超過 3000 次的話，它會觸發 RecursionError。
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
print(fact(4000))
Traceback (most recent call last):
File "<pyshell#2>", line 1, in <module>
print(factorial(3000))
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
File "<pyshell#1>", line 5, in factorial
return n * factorial(n-1)
[Previous line repeated 989 more times]
File "<pyshell#1>", line 2, in factorial
if n == 1:
RecursionError: maximum recursion depth exceeded in comparison
移除遞迴限制的方法
你可以通過將遞迴限制次數設定為大於所需遞迴次數的數字來解除遞迴次數的限制。
import sys
sys.setrecursionlimit(5000)
def fact(n):
"""Recursive function to find factorial"""
if n == 1:
return 1
else:
return n * fact(n - 1)
print(fact(4000))
遞迴的優點
- 使用遞迴函式，可以將問題分解為子問題來輕鬆解決。
- 程式碼變得整潔乾淨。
遞迴的缺點
- 有時很難去設計和理解遞迴函式的邏輯。
- 解決每個子問題將花費大量時間，因此遞迴函式效率低下。
