在一個(gè)函數(shù)定義中，自己調(diào)用自己的編程方法稱之為遞歸（Recursion）。

一、遞歸簡(jiǎn)介

一般來(lái)說(shuō)，遞歸需要有遞歸前進(jìn)階段、遞歸邊界條件和遞歸返回階段。當(dāng)遞歸條件不滿足時(shí)，遞歸前推；當(dāng)遞歸條件滿足時(shí)，遞歸返回。

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

5! = 5 × 4!

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

4! = 4 × 3!

我們需要進(jìn)一步求出3的階乘，而

3! = 3 × 2!

我們需要進(jìn)一步求出2的階乘，而

2! = 2 × 1!

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

在求出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。上面這些步驟就是遞歸“返回”的過(guò)程。

用圖表示如下：

二、使用遞歸方法求一個(gè)數(shù)的階乘

#遞歸法求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)

執(zhí)行結(jié)果如下：

5！= 120
10！= 3628800

三、使用遞歸方法求斐波那契數(shù)列

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

def Fibonacci(n):
    if n < 0:
        raise IndexError('參數(shù)不能小于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 = " ")

輸出結(jié)果如下：

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

四、使用遞歸的利弊

使用遞歸有時(shí)使程序更加簡(jiǎn)潔，減少代碼量。但對(duì)新手來(lái)說(shuō)，遞歸比較難以理解，而且使用不當(dāng)?shù)脑挘赡苁钩绦驘o(wú)法正常終止。大多數(shù)情況下，可以使用循環(huán)來(lái)替代遞歸。

本文（完）