7. 遞迴

前言

函式間也可以相互呼叫，除了呼叫別的函式外，也可呼叫自己本身，這種函式呼叫自己的方式稱為「遞迴」。每一次呼叫，皆會產生不一樣的效果，直到遇到終止再呼叫函式自身的條件或效果時，才會停止遞迴離開函式。如果遞迴的函式內沒有設定終止呼叫的條件，則這樣的函式會形成無窮遞迴。

遞迴在數學或電玩遊戲上常被使用，例如：數列、階乘、費氏數列、輾轉相除法、排列、組合、堆疊、河內塔、八個皇后、老鼠走迷宮…。有些程式雖然使用for、while…等重複結構也能處理，但使用遞迴函式會較為簡潔易懂。以「階乘」為例，正整數的階乘是所有小於及等於該數 n 的正整數的積，用 n!表示。階乘的通式為 n! = n * (n-1) * (n-2) * … * 2 * 1
例如： 5! = 5 * 4 * 3 *2 *1 = 120。

[簡例] 使用階乘函式計算n!=1*2*3*(n-1)*n的結果,其中由使用者輸入。n的輸入值必須大於等於1。 (檔名:factorial.py)

[結果]

n = 6 ↵
6! = 720

[不用遞迴]

factorial-1.py

def factorial(n):
    """
    使用迴圈計算 n! (非遞迴寫法)
    n! = 1 * 2 * 3 * ... * (n-1) * n
    """
    # 初始化乘積變數，因為是連乘，所以初始值必須設定為 1 (設為 0 會導致結果全為 0)
    result = 1
    # 使用 for 迴圈產生 1 到 n 的整數序列 
    # range(1, n + 1) 的範圍包含 1，但不包含 (n + 1)，所以正好是 1 ~ n
    for i in range(1, n + 1):
        # 相當於 result = result * i，將每個數字陸續累乘進去
        result *= i
    # 傳回最終計算完成的階乘數值    
    return result
# 使用 while True 建立無限迴圈，直到使用者輸入合格的數字為止
def main():
    # 使用 while 迴圈確保使用者輸入符合規則 (正整數 >= 1)
    while True:
        try:
            # 取得使用者輸入的字串，並嘗試轉為整數 (int)
            user_input = int(input("請輸入一個大於等於 1 的整數 n: "))
            # 檢查輸入的數值是否符合規定 (大於等於 1)
            if user_input >= 1:
                # 輸入數值合格，跳出 while 迴圈
                break
            else:
                # 數值小於 1，提示錯誤並繼續執行迴圈重新要求輸入
                print("【錯誤】輸入值必須大於等於 1，請重新輸入！\n")
               
        except ValueError:
            # 如果使用者輸入非數字（例如字母、小數或空白），int() 會引發 ValueError 錯誤 
            # 透過 except 攔截錯誤，避免程式崩潰
            print("【錯誤】輸入內容非有效整數，請重新輸入！\n")
 
    # 將驗證合格的 user_input 傳入 factorial 函式中計算，並用 ans 接收回傳值
    ans = factorial(user_input)
 
    # 使用 f-string 格式化字串，印出最終計算結果
    print(f"\n計算結果：{user_input}! = {ans}")
# 這是 Python 的最佳實踐（Best Practice）。確保當這個 `.py` 檔被其他程式當作模組（Module）匯入時，不會自動執行 `main()` 的互動輸入流程。
if __name__ == "__main__":
   main()

factorial-2.py

# 定義階乘函數 d(n)（使用遞迴 Recursive）
# 當 n <= 1 時，回傳 1（基礎條件 Base Case，防止無限遞迴）。
# 當 n > 1 時，回傳 n*d(n-1)（遞迴呼叫，持續向下計算乘積）。
# 例如計算 d(5)：會推導為 5 * d(4)= 5*(4*d(3)) = 5 * 4 * (3*d(2)) = 5 * 4 * 3 * (2*d(1)) = 5 * 4 * 3 * 2 * 1。
def d(n):
   if n <= 1:
       return 1
   else :            # n > 1        
       return n * d(n-1) 
 
while True:
   n = eval(input('n = '))
   if (n >= 1):
       break
   else:
       print('輸入資料不符, 請重新輸入...')
 
fac = d(n)
print (f'{n}! = {fac}')

---

相關主題與延伸閱讀

• 3. 自定函式：遞迴是自定函式呼叫自己本身的特殊應用方式。
• 1. for 迴圈：許多遞迴可處理的問題也能改用 for 迴圈等重複結構實作。
• 6. 全域變數與區域變數：每次遞迴呼叫都會產生獨立的區域變數空間。
• 2. while 迴圈：本篇範例使用 while 迴圈驗證使用者輸入，可對照學習。