Python 學習筆記 : 遞迴函式範例

這幾天發現母校圖書館已開放校友借書, 為了借新書, 這幾天把手上所借舊書再 review 一下就要拿去還了. 在下面這本書看到幾個典型的遞迴函式, 就順手做個測試紀錄一下 :

# 第一次學 Python 就上手 (旗標, 陳惠貞, 2018)

1. 階乘函式 :

Python 內建模組 math 裡有一個 factorial() 函式可用來計算階乘, 例如 :

>>> import math    

>>> math.factorial(5)        # 5!=120

120

>>> 5*4*3*2*1   

120

如果要自行實作可以用遞迴函式來做, 例如 :

>>> def factorial(n):   

    if n == 0:        # 0!=1

        return 1   

    elif n > 0:                   

        return n * factorial(n - 1)       # n-1 遞迴呼叫本身

    else:   

        return -1    # 負數無階乘, 傳回 -1         

    

>>> factorial(5)      # 5!=120

120

可見結果與呼叫 math.factorial() 一樣, 完整程式如下 :

def factorial(n):

    if n == 0:

        return 1

    elif n > 0:

        return n * factorial(n - 1)

    else:

        return -1

2. 費氏 (Fibonacci) 數列函式 :

Fibonacci 數列是從 1, 1 開始的數列, 後面的每一個值是前兩個的和 :

1, 1, 2, 3, 5, 8, 13, 21, .....

產生新的數列元素的演算法顯然有遞迴特徵, 可用如下的遞迴函式來產生 :

>>> def fib(n):    

    if n > 2:    

        return fib(n - 2) + fib(n - 1)    # 前兩個之和

    elif n == 1 or n == 2:                   # 級數初始的兩個值

        return 1     

    else:    

        return None     # 0 或負數傳回 None

>>> for i in range(1, 20):       # 走訪前 20 個數列

    print(fib(i), end=' ')    

    

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 

完整函式如下 : 

def fib(n):

    if n > 2:

        return fib(n - 2) + fib(n - 1)

    elif n == 1 or n == 2:

        return 1

    else:

        return None

3. 求最大公因數 GCD 的函式 :

兩個數 m, n 的最大公因數算法如下 :

• 若 n 可以整除 m, 則 n 即為最大公因數
• 若 n 無法整除 m, 則用 n 與 m 除以 n 的餘數求 GCD

第二項明顯具有遞迴性質, 可寫成遞迴函式來求值, 例如 :

>>> def GCD(m, n):     

    if m % n == 0:         # 整除傳回除數 n 為 GCD

        return n    

    else:    

        return GCD(n, m % n)      # 不能整除則以 n 與 m%n 繼續求 GCD

>>> GCD(4, 8)    

4

>>> GCD(8, 4)     

4

>>> GCD(18, 12)      

6

>>> GCD(12, 18)     

6

完整函式如下 : 

def GCD(m, n):

    if m % n == 0:

        return n

    else:

        return GCD(n, m % n)