递回 recursion

在写程序时，有时会遇到无法单纯使用循环解决的问题，这时候就会需要使用函数的“递回”功能，透过递回的方式，就能处理每次重复需要改变的参数或输出结果，这篇教学将会介绍 Python 函数里的递回。

快速导览：什么是递回？、使用递回函数的注意事项、使用递回 vs 使用迭代操作、n 阶层、费波那契数列

本篇使用的 Python 版本为 3.7.12，所有范例可使用 Google Colab 实作，不用安装任何软件 ( 参考：使用 Google Colab )

什么是递回？

当“一个函数会在执行当中，不断地自己呼叫自己”，这个函数便具有“递回”的特性，递回的本质很像循环，但却可以处理许多循环不容易处理的参数或回传值，要撰写一个有递回特性的函数，需要满足下列两个特征：

• 函数会自己呼叫自己。
• 具备函数停止条件 ( 避免无穷尽的呼叫自己 )。

下方的程序码表现了一个最基本的递回函数：

def a(n):                    # 建立函式 a，帶有參數 n
    if n == 0 or n == 1:     # 如果 n 等於 0 或 1
        return 1             # 回傳結果 1
    else:
        return n + a(n-1)    # 使用遞迴

print(a(3))                  # 執行結果為 6 ( 3+2+1 )

下图表现上述递回程序码的执行的顺序：

使用递回函数的注意事项

递回虽然很方便，但在使用上仍有下列几点需要注意：

• 递回虽然有时可以减少复杂度，但相对会使用更多的内存。
• Python 将递回呼叫次数限制设定为 3000 次，超过就会发生错误，被强制停止。

使用递回 vs 使用迭代操作

n 阶层

数字 n 阶层 (n!) 的定义为：(n) x (n-1) x (n-2)....x2 x1，可以使用下方递回方式处理：

def a(n):                    # 建立函式 a，帶有參數 n
    if n == 0 or n == 1:     # 如果 n 等於 0 或 1
        return 1             # 回傳結果 1
    else:
        return n * a(n-1)    # 使用遞迴
print(a(4))                  # 執行結果為 24 ( 4x3x2x1 )

下图为递回程序码的执行的顺序：

费波那契数列

下方的程序码，使用递回的方式来建立费波那契数列。

def fib(n):                         # 建立函式 fib，帶有參數 n
    if n > 1:                       # 如果 n 大於 1
        return fib(n-1) + fib(n-2)  # 使用遞迴
    return n
for i in range(20):                 # 產生 20 個數字
    print(fib(i), end = ',')        # 0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610,987,1597,2584,4181

下图为递回程序码的执行的顺序：

最大公因数

下方的程序码，使用递回的方式，搭配“辗转相除法”来找出两个数字的最大公因数。

def f(a, b):             # 建立函式 f，帶有參數 a 和 b
    if a%b == 0:         # 如果相除餘數為 0，回傳結果
        return b
    else:                # 如果相除不為 0，表示還沒找到最大公因數
        return f(b, a%b) # 使用遞迴，參數 a 使用 b，b 使用 a 除以 b 的餘數
print(f(456, 48))        # 得到結果 24

下图为递回程序码的执行的顺序：

意见反馈