深入理解 Python 中的遞迴(Recursion)

更新日期: 2024 年 10 月 10 日

在學習程式設計的過程中,遞迴(Recursion) 是一個重要且強大的概念。

遞迴允許函式在執行過程中呼叫自己,用於解決許多複雜的問題,例如計算階乘、斐波那契數列和樹狀資料結構的遍歷。

對於新手來說,理解遞迴可能有些困難,但一旦掌握,將大大提升你的編程能力。

本文將帶你深入了解 Python 中的遞迴。


什麼是遞迴?

遞迴 是指一個函式直接或間接地呼叫自己。

在處理遞迴問題時,通常需要考慮兩個重要部分:

  1. 遞迴基礎(Base Case):定義何時停止遞迴,避免無限遞迴。
  2. 遞迴步驟(Recursive Step):將問題分解為較小的子問題,並呼叫自身解決。

遞迴的基本結構

def recursive_function(parameters):
    if base_case_condition:
        return base_case_value
    else:
        # 遞迴步驟
        return recursive_function(modified_parameters)
  • 基礎條件(base_case_condition):當滿足此條件時,函式不再呼叫自身,返回結果。
  • 遞迴步驟:函式呼叫自身,並使用修改後的參數。

範例解析

計算階乘

問題描述:計算一個非負整數 n 的階乘,即 n! = n * (n-1) * ... * 1

遞迴解法

def factorial(n):
    if n == 0 or n == 1:
        return 1  # 基礎條件
    else:
        return n * factorial(n - 1)  # 遞迴步驟

print(factorial(5))  # 輸出:120
  • 基礎條件:當 n01 時,階乘為 1
  • 遞迴步驟:將 n 乘以 factorial(n - 1)

執行流程

  • factorial(5) 需要 factorial(4)
  • factorial(4) 需要 factorial(3)
  • factorial(3) 需要 factorial(2)
  • factorial(2) 需要 factorial(1)
  • factorial(1) 符合基礎條件,返回 1
  • 計算順序:
    • factorial(2) = 2 * 1 = 2
    • factorial(3) = 3 * 2 = 6
    • factorial(4) = 4 * 6 = 24
    • factorial(5) = 5 * 24 = 120

費氏數列

問題描述:計算費氏數列的第 n 個數。費氏數列定義如下:

  • F(0) = 0
  • F(1) = 1
  • F(n) = F(n-1) + F(n-2)

遞迴解法

def fibonacci(n):
    if n == 0:
        return 0  # 基礎條件
    elif n == 1:
        return 1  # 基礎條件
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)  # 遞迴步驟

print(fibonacci(6))  # 輸出:8

執行流程

  • fibonacci(6) 需要 fibonacci(5)fibonacci(4)
  • 這種情況下,遞迴呼叫會非常頻繁,存在大量重複計算。

優化建議

  • 使用備忘錄(Memoization):儲存已計算的結果,避免重複計算。
  • 使用迭代法:改用迴圈實現,效率更高。

遍歷嵌套列表

問題描述:計算一個包含多層嵌套列表的所有元素之和。

遞迴解法

def sum_nested_list(lst):
    total = 0
    for element in lst:
        if isinstance(element, list):
            total += sum_nested_list(element)  # 遞迴呼叫
        else:
            total += element
    return total

nested_list = [1, [2, [3, 4], 5], 6]
print(sum_nested_list(nested_list))  # 輸出:21

遞迴的優缺點

優點

  • 代碼簡潔:遞迴能使代碼更容易閱讀和理解,特別是對於樹狀或階層結構的問題。
  • 自然表達:許多問題天然適合遞迴表達,如樹遍歷、圖遍歷。

缺點

  • 性能問題:遞迴可能導致大量的函式呼叫,消耗較多的內存和時間。
  • 堆疊溢出:如果遞迴深度過大,可能會導致堆疊溢出錯誤。

To iterate is human, to recursive, divine!

遞迴只應天上有,凡人應當用迴圈


遞迴與迭代的比較

  • 遞迴:函式呼叫自身,適合解決可分解為相似子問題的情況。
  • 迭代:使用循環結構(如 forwhile),適合需要重複執行某段代碼的情況。

示例:使用迭代計算階乘

def factorial_iterative(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial_iterative(5))  # 輸出:120

遞迴的注意事項

  1. 確保基礎條件正確:避免無限遞迴。
  2. 警惕堆疊溢出:對於深度較大的遞迴,考慮優化或改用迭代。
  3. 優化性能:對於存在大量重複計算的遞迴,考慮使用備忘錄或其他優化方法。

實際應用

樹和圖的遍歷

  • 前序、中序、後序遍歷:常用於二叉樹的遍歷。
  • 深度優先搜索(DFS):適合用遞迴實現。

分治法

  • 快速排序
  • 合併排序

其他算法

  • 背包問題
  • 漢諾塔問題

結論

遞迴是 Python 編程中一個強大而重要的工具,能夠以簡潔的方式解決複雜的問題。

對於新手來說,理解遞迴的工作原理和應用場景非常關鍵。

希望通過本文的介紹,你能夠掌握遞迴的基本概念,並在實際編程中靈活運用。


進一步學習

  • 備忘錄技術(Memoization):學習如何優化遞迴算法的性能。
  • 尾遞迴優化:瞭解 Python 對尾遞迴的支持情況。
  • 練習題:嘗試解決更多遞迴相關的問題,如八皇后、迷宮尋路等。

Similar Posts