Python遞迴函式

我們這節來學習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))

遞迴的優點:

  • 使用遞迴函式,可以將問題分解為子問題來輕鬆解決。
  • 程式碼變得整潔乾淨。

遞迴的缺點:

  • 有時很難去設計和理解遞迴函式的邏輯。
  • 解決每個子問題將花費大量時間,因此遞迴函式效率低下。