Python 遞歸(Recursion)

在本文中，您將學習如何創(chuàng)建遞歸函數(shù)(調(diào)用自身的函數(shù))。

什么是Python中的遞歸？

遞歸是根據(jù)自身定義某些內(nèi)容的過程。

一個物理世界的示例是放置兩個彼此面對的平行反射鏡。它們之間的任何對象都將遞歸地反映出來。

Python遞歸函數(shù)

在Python中，我們知道一個函數(shù)可以調(diào)用其他函數(shù)。函數(shù)甚至可能會調(diào)用自身。這些類型的構(gòu)造稱為遞歸函數(shù)。

以下是查找整數(shù)的階乘的遞歸函數(shù)的示例。

數(shù)字的階乘是從1到該數(shù)字的所有整數(shù)的乘積。例如，階乘6（表示為6！）是1 * 2 * 3 * 4 * 5 * 6 = 720。

遞歸函數(shù)示例

def calc_factorial(x):
    """這是一個
    求整數(shù)階乘的遞歸函數(shù)"""

    if x == 1:
        return 1
    else:
        return (x * calc_factorial(x-1))


num = 4
print("The factorial of", num, "is", calc_factorial(num))

在上面的示例中，它calc_factorial()是一個遞歸函數(shù)，它調(diào)用了自己。

當我們用正整數(shù)調(diào)用此函數(shù)時，它將通過減少數(shù)量來遞歸調(diào)用自身。

每個函數(shù)將數(shù)字乘以該數(shù)字下面的數(shù)字的階乘，直到它等于1。可以在以下步驟中解釋此遞歸調(diào)用。

calc_factorial(4)              # 1st call with 4
4 * calc_factorial(3)          # 2nd call with 3
4 * 3 * calc_factorial(2)      # 3rd call with 2
4 * 3 * 2 * calc_factorial(1)  # 4th call with 1
4 * 3 * 2 * 1                  # return from 4th call as number=1
4 * 3 * 2                      # return from 3rd call
4 * 6                          # return from 2nd call
24                             # return from 1st call

當數(shù)字減少到1時，遞歸結(jié)束。這稱為基本條件。

每個遞歸函數(shù)必須具有停止遞歸的基本條件，否則該函數(shù)將無限調(diào)用自身。

Python解釋器限制了遞歸的深度，以幫助避免無限遞歸，從而導致堆棧溢出。

默認情況下，最大遞歸深度為 1000。如果超出限制，則結(jié)果為RecursionError。讓我們看一個這樣的條件。

def recursor():
    recursor()
recursor()

輸出結(jié)果

Traceback (most recent call last):
  File "<string>", line 3, in <module>
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  File "<string>", line 2, in a
  [Previous line repeated 996 more times]
RecursionError: maximum recursion depth exceeded

遞歸的優(yōu)點

1. 遞歸函數(shù)使代碼看起來干凈整潔。

2. 使用遞歸可以將復雜的任務(wù)分解為更簡單的子問題。

3. 與使用嵌套嵌套相比，使用遞歸更容易生成序列。

遞歸的缺點

1. 有時，遞歸背后的邏輯很難遵循。

2. 遞歸調(diào)用很昂貴（效率低），因為它們占用大量內(nèi)存和時間。

3. 遞歸函數(shù)很難調(diào)試。