在一個函數定義中，自己調用自己的編程方法稱之為遞歸（Recursion）。

一、遞歸簡介

一般來說，遞歸需要有遞歸前進階段、遞歸邊界條件和遞歸返回階段。當遞歸條件不滿足時，遞歸前推；當遞歸條件滿足時，遞歸返回。

如我們要求5的階乘（5!），則：

5! = 5 × 4!

我們需要求出4的階乘后再乘以5就行了，而要求4!：

4! = 4 × 3!

我們需要進一步求出3的階乘，而

3! = 3 × 2!

我們需要進一步求出2的階乘，而

2! = 2 × 1!

這時我們知道1的階乘是1。以上這些步驟就是遞歸的“前推”過程。

在求出1的階乘后，我們就知道

2! = 2 × 1! = 2× 1 = 2

則：

3! = 3 × 2! = 3 × 2 = 6

則：

4! = 4 × 3! = 4 × 6 = 24

則：

5! = 5 × 4! = 5 × 24 = 120

這樣，我們就得到了5！是120。上面這些步驟就是遞歸“返回”的過程。

用圖表示如下：

二、使用遞歸方法求一個數的階乘

#遞歸法求n!

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)

result = factorial(5)
print("5！= ", result)
result = factorial(10)
print("10！= ", result)

執行結果如下：

5！= 120
10！= 3628800

三、使用遞歸方法求斐波那契數列

在前面文章中《Python使用while循環輸出斐波那契數列》介紹了斐波那契數列的算法，并給出了幾種求斐波那契數列的算法。這里再重新給出一遍。

def Fibonacci(n):
    if n < 0:
        raise IndexError('參數不能小于0。')
    if n == 0:
        return 0
    elif n <= 2:
        return 1
    else:
        return Fibonacci(n - 1) + Fibonacci(n - 2)

for i in range(16):
    print(Fibonacci(i), end = " ")

輸出結果如下：

0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610

四、使用遞歸的利弊

使用遞歸有時使程序更加簡潔，減少代碼量。但對新手來說，遞歸比較難以理解，而且使用不當的話，可能使程序無法正常終止。大多數情況下，可以使用循環來替代遞歸。

本文（完）