Post

Python 基礎：遞迴函數的完整教學

Posted
By
18 min read
Python 基礎：遞迴函數的完整教學

Python 基礎：遞迴函數的完整教學

遞迴（Recursion）是電腦科學中一個非常重要的概念，也是一種很強大的程式設計技術。簡單來說，遞迴就是函數呼叫自己的過程。本篇文章將帶你深入了解遞迴的原理與應用，並特別說明全域變數與區域變數在遞迴中的使用方式，以及常見的錯誤與重點整理。

1. 遞迴的基本概念

1.1 什麼是遞迴？

遞迴是指函數在執行過程中直接或間接呼叫自己的現象。遞迴讓我們可以用簡潔的方式解決複雜的問題，特別是當問題可以分解為相同性質的子問題時。

讓我們用生活中的例子來理解：

從前有座山，山裡有座廟，廟裡有個老和尚，老和尚在給小和尚講故事：從前有座山，山裡有座廟…

這就是一個無限遞迴的例子。當然，我們的程式需要有結束條件，否則會陷入無限迴圈。

1.2 遞迴的組成要件

一個正確的遞迴函數必須包含兩個部分：

  1. 基本案例（Base Case）：遞迴的終止條件，當滿足這個條件時不再繼續遞迴。
  2. 遞迴案例（Recursive Case）：將問題分解為更小的子問題，繼續呼叫自己。
1
2
3
4
5
6
7
8

def 遞迴範例(n):
    if n <= 0:           # 基本案例：終止條件
        return
    print(n)
    遞迴範例(n - 1)      # 遞迴案例：呼叫自己

遞迴範例(5)
# 輸出：5, 4, 3, 2, 1

1.3 遞迴的呼叫過程

讓我們用更詳細的例子來看遞迴是如何執行的：

1
2
3
4
5
6
7
8
9
10

def 計算階乘(n):
    print(f"進入函數：n = {n}")
    if n == 1:           # 基本案例
        print(f"達到基本案例，返回 1")
        return 1
    結果 = n * 計算階乘(n - 1)  # 遞迴呼叫
    print(f"返回結果：{結果}")
    return 結果

計算階乘(3)

執行過程：

1
2
3
4
5
6

進入函數：n = 3
進入函數：n = 2
進入函數：n = 1
達到基本案例，返回 1
返回結果：2
返回結果：6

2. 經典遞迴範例

2.1 計算階乘

階乘（Factorial）是指一個正整數與它以下所有正整數的乘積，記作 n!。

1
2
3
4
5
6
7

def 階乘(n):
    if n <= 1:           # 基本案例
        return 1
    return n * 階乘(n - 1)  # 遞迴案例

print(階乘(5))   # 輸出：120
print(階乘(0))   # 輸出：1（0! = 1）

2.2 費波那契數列

費波那契數列（Fibonacci Sequence）是這樣的數列：1, 1, 2, 3, 5, 8, 13, 21, …

每一個數都是前兩個數的和。

1
2
3
4
5
6
7
8

def 費波那契(n):
    if n <= 1:           # 基本案例
        return n
    return 費波那契(n - 1) + 費波那契(n - 2)  # 遞迴案例

for i in range(10):
    print(費波那契(i), end=" ")
# 輸出：0 1 1 2 3 5 8 13 21 34

2.3 計算次方

1
2
3
4
5
6
7

def 次方(base, exponent):
    if exponent == 0:    # 基本案例
        return 1
    return base * 次方(base, exponent - 1)

print(次方(2, 10))  # 輸出：1024
print(次方(5, 3))   # 輸出：125

2.4 反轉字串

1
2
3
4
5
6
7

def 反轉字串(s):
    if len(s) <= 1:     # 基本案例
        return s
    return s[-1] + 反轉字串(s[:-1])

print(反轉字串("Hello"))  # 輸出：olleH
print(反轉字串("Python")) # 輸出：nohtyP

2.5 計算陣列總和

1
2
3
4
5
6

def 陣列總和(arr):
    if len(arr) == 0:    # 基本案例
        return 0
    return arr[0] + 陣列總和(arr[1:])

print(陣列總和([1, 2, 3, 4, 5]))  # 輸出：15

2.6 二元搜尋

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def 二元搜尋(arr, target, left, right):
    if left > right:     # 基本案例：找不到
        return -1
    
    mid = (left + right) // 2
    
    if arr[mid] == target:
        return mid       # 找到目標
    elif arr[mid] < target:
        return 二元搜尋(arr, target, mid + 1, right)  # 搜尋右半邊
    else:
        return 二元搜尋(arr, target, left, mid - 1)   # 搜尋左半邊

arr = [1, 3, 5, 7, 9, 11, 13, 15]
print(二元搜尋(arr, 7, 0, len(arr) - 1))  # 輸出：3
print(二元搜尋(arr, 6, 0, len(arr) - 1))  # 輸出：-1

3. 遞迴與迴圈的比較

3.1 兩種方式的比較

很多遞迴問題也可以用迴圈（Loop）來解決：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

# 用迴圈計算階乘
def 階乘_迴圈(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

# 用遞迴計算階乘
def 階乘_遞迴(n):
    if n <= 1:
        return 1
    return n * 階乘_遞迴(n - 1)

print(階乘_迴圈(5))   # 輸出：120
print(階乘_遞迴(5))   # 輸出：120

3.2 遞迴的優點

  1. 程式碼簡潔：用更少的程式碼表達複雜邏輯
  2. 自然表達：某些問題用遞迴表達更直觀（如樹結構遍歷）
  3. 易於理解：符合人類思考方式

3.3 遞迴的缺點

  1. 記憶體消耗：每次遞迴呼叫都需要佔用記憶體空間
  2. 效能較慢：函數呼叫有額外開銷
  3. 可能發生棧溢取：過深的遞迴會導致堆疊溢出

4. 全域變數與區域變數在遞迴中的應用

4.1 區域變數在遞迴中的使用

在遞迴函數中，區域變數會在每次呼叫時創建新的副本，這是遞迴正確運作的關鍵：

1
2
3
4
5
6
7
8
9
10

def 遞迴與區域變數(n):
    計數 = 0              # 區域變數，每次呼叫都會重新創建
    計數 += 1
    print(f"n={n}, 計數={計數}")
    
    if n > 0:
        遞迴與區域變數(n - 1)

遞迴與區域變數(3)
# 每次呼叫的計數都是 1

4.2 全域變數在遞迴中的使用

使用全域變數需要注意，遞迴中的修改會影響全域狀態：

1
2
3
4
5
6
7
8
9
10
11
12

計數 = 0  # 全域變數

def 遞迴與全域變數(n):
    global 計數
    計數 += 1
    print(f"n={n}, 計數={計數}")
    
    if n > 0:
        遞迴與全域變數(n - 1)

遞迴與全域變數(3)
print(f"最終計數：{計數}")  # 輸出：4

4.3 使用區域變數避免副作用

建議：盡量使用區域變數，避免使用全域變數造成副作用：

1
2
3
4
5
6
7
8
9
10

def 安全的遞迴(n):
    # 使用參數傳遞，避免全域變數
    def 內部遞迴(n, 計數):
        if n == 0:
            return 計數
        return 內部遞迴(n - 1, 計數 + 1)
    
    return 內部遞迴(n, 0)

print(安全的遞迴(3))  # 輸出：3

4.4 使用列表收集結果

1
2
3
4
5
6
7
8
9
10
11
12
13

def 收集所有結果(n):
    結果列表 = []  # 區域變數
    
    def 遞迴收集(i):
        if i == 0:
            return
        結果列表.append(i)  # 修改外層函數的區域變數
        遞迴收集(i - 1)
    
    遞迴收集(n)
    return 結果列表

print(收集所有結果(5))  # 輸出：[5, 4, 3, 2, 1]

5. 常見錯誤與解決方案

5.1 忘記基本案例

錯誤範例：

1
2
3
4
5

def 無限遞迴(n):
    return n + 無限遾迴(n - 1)  # 沒有終止條件，會無限遙迴

# 執行這行會導致程式崩潰
# print(無限遞迴(5))

解決方案：務必設定基本案例

1
2
3
4
5
6

def 正確的遞迴(n):
    if n <= 0:       # 基本案例
        return 0
    return n + 正確的遾迴(n - 1)

print(正確的遙迴(5))  # 輸出：15

5.2 基本案例撰寫錯誤

錯誤範例：

1
2
3
4

def 錯誤的費波那契(n):
    if n == 0:       # 錯誤的基本案例
        return 1
    return 錯誤的費波那契(n - 1) + 錯誤的費波那契(n - 2)

解決方案：正確的基本案例

1
2
3
4

def 正確的費波那契(n):
    if n <= 1:      # 正確：n=0 和 n=1 都是基本案例
        return n
    return 正確的費波那契(n - 1) + 正確的費波那契(n - 2)

5.3 遞迴深度過深

錯誤範例：

1

print(遞迴(10000))  # RecursionError: maximum recursion depth exceeded

解決方案：增加遙迴限制或改用迴圈

1
2
3
4
5
6
7
8
9
10
11
12
13

import sys

# 增加遙迴限制（不建議無限制增加）
sys.setrecursionlimit(10000)

# 或改用迴圈
def 迴圈版本(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

5.4 全域變數污染

錯誤範例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

計數 = 0

def 遙迴(n):
    global 計數
    if n == 0:
        return
    計數 += 1
    遙迴(n - 1)

遙迴(5)
print(計數)  # 輸出：5

# 再次呼叫會累加
遙迴(5)
print(計數)  # 輸出：10（出錯！）

解決方案：使用參數傳遞

1
2
3
4
5
6
7

def 正確的遙迴(n, 計數=0):
    if n == 0:
        return 計數
    return 正確的遙迴(n - 1, 計數 + 1)

print(正確的遙迴(5))  # 輸出：5
print(正確的遙迴(5))  # 輸出：5（正確）

5.5 效能問題：重複計算

錯誤範例：

1
2
3
4
5
6
7
8

# 費波那契的效率問題
def 費波那契(n):
    if n <= 1:
        return n
    return 費波那契(n - 1) + 費波那契(n - 2)

# 這個函數的複雜度是指數級 O(2^n)
# 計算費波那契(40) 需要很長時間

解決方案：使用記憶化（Memoization）

1
2
3
4
5
6
7
8
9

快取 = {}

def 費波那契優化(n):
    if n in 快取:
        return 快取[n]
    if n <= 1:
        return n
    快取[n] = 費波那契優化(n - 1) + 費波那契優化(n - 2)
    return 快取[n]

6. 遞迴的實際應用

6.1 目錄遍歷

1
2
3
4
5
6
7
8
9
10
11
12

import os

def 遍歷目錄(path, indent=0):
    items = os.listdir(path)
    for item in items:
        full_path = os.path.join(path, item)
        print("  " * indent + item)
        if os.path.isdir(full_path):
            遍歷目錄(full_path, indent + 1)

# 遍歷當前目錄
遍歷目錄(".")

6.2 解決河內塔問題

1
2
3
4
5
6
7
8
9
10

def 河內塔(n, 來源, 目標, 輔助):
    if n == 1:
        print(f"移動盤子 1 從 {來源} 到 {目標}")
        return
    河內塔(n - 1, 來源, 輔助, 目標)
    print(f"移動盤子 {n} 從 {來源} 到 {目標}")
    河內塔(n - 1, 輔助, 目標, 來源)

# 三根柱子：A、B、C
河內塔(3, 'A', 'C', 'B')

6.3 生成所有排列組合

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def 全排列(arr):
    if len(arr) <= 1:
        return [arr]
    
    結果 = []
    for i in range(len(arr)):
        當前 = arr[i]
        剩餘 = arr[:i] + arr[i+1:]
        for p in 全排列(剩餘):
            結果.append([當前] + p)
    return 結果

print(全排列([1, 2, 3]))
# 輸出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

7. 重點整理

7.1 遞迴的核心概念

  1. 基本案例（Base Case）：遞迴的終止條件
  2. 遞迴案例（Recursive Case）：將問題分解為子問題
  3. 呼叫堆疊：每次遞迴呼叫都會佔用記憶體

7.2 常見的遞迴應用

  • 階乘計算
  • 費波那契數列
  • 反轉字串
  • 二元搜尋
  • 樹結構遍歷

7.3 遞迴的優缺點

優點：

  • 程式碼簡潔
  • 符合人類思考方式
  • 適合解決可分解的問題

缺點：

  • 記憶體消耗大
  • 可能發生堆疊溢出
  • 效能可能較差

7.4 全域變數與區域變數

  • 區域變數：每次遞迴呼叫都會創建新的副本
  • 全域變數：在遞迴中修改會影響全域狀態
  • 建議：盡量使用區域變數和參數傳遞

7.5 常見錯誤提醒

  1. 務必設定基本案例
  2. 注意遞迴深度限制
  3. 避免全域變數污染
  4. 留意效能問題，使用記憶化優化

8. 結論

遞迴是程式設計中非常重要的概念，透過本篇文章，我們學習了：

  • 遞迴的基本概念與組成要件
  • 經典的遞迴範例（階乘、費波那契等）
  • 遞迴與迴圈的比較
  • 全域變數與區域變數在遞迴中的應用
  • 常見錯誤與解決方案
  • 遞迴的實際應用

掌握遙迴技巧後，你可以更優雅地解決許多複雜的問題。建議多加練習，並嘗試將一些用迴圈實現的程式改用遞迴來實現，加深對遞迴概念的理解。

持續練習，你會發現遞迴是一個非常強大的工具！

教學, 程式教學
Python 程式教學 遞迴 Recursion
This post is licensed under CC BY 4.0 by the author.

© homedad. Some rights reserved.

Using the Chirpy theme for Jekyll.