02.1-遞迴法

遞迴法 是一種將問題分解為較小的子問題的技術，通過在每個步驟中調用自身來解決問題。遞迴的基本思想是將複雜的問題拆分為簡單的子問題，這些子問題再進一步分解，直到達到簡單的基礎情況（base case），不再需要進一步遞迴。每次遞迴都會向基礎情況推進，最終從基礎情況回溯得到問題的解。

1. 遞迴的基本結構#

一個遞迴函數通常包含兩個主要部分： 1. 基礎情況（Base case）：決定何時停止遞迴，並返回結果。 2. 遞迴步驟（Recursive step）：將問題分解為較小的子問題，並對其進行遞迴處理。

一般形式如下：

def recursive_function(n):
    if n <= 1:  # 基礎情況
        return 1
    else:  # 遞迴步驟
        return n * recursive_function(n - 1)

2. 遞迴法的特點#

分治法：遞迴可以通過將大問題分解成小問題來實現分治策略。例如，快速排序和合併排序都依賴於遞迴來分解和排序子陣列。
簡潔性：某些問題（如樹結構的遍歷、圖的深度優先搜尋等）使用遞迴可以寫得非常簡潔，能夠清晰地表達問題的結構。

3. 遞迴的工作原理#

遞迴通常表現為一個函數調用自身。每次遞迴調用都會創建一個新的執行上下文，並將該上下文的狀態保存到堆棧中。當基礎情況達成時，遞迴過程會開始回溯，從堆棧中取出狀態並完成計算。

遞迴的工作流程示例：階乘計算#

例如，計算 \(n!\) （n的階乘）： [ n! = n \times (n-1) \times (n-2) \times ... \times 1 ]

遞迴定義如下：

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

運行過程： - factorial(5) 會調用 factorial(4) - factorial(4) 會調用 factorial(3) - factorial(3) 會調用 factorial(2) - factorial(2) 會調用 factorial(1) - 當 factorial(1) 返回 1 時，開始逐層回溯，最終計算結果是 120。

4. 遞迴法的應用#

遞迴方法非常適合解決一些具有分支結構或層級結構的問題，以下是一些典型的遞迴應用場景：

4.1 階乘計算#

如上所示，計算階乘的遞迴方法簡潔而直觀。

4.2 斐波那契數列#

斐波那契數列的遞迴定義如下： [ F(n) = F(n-1) + F(n-2), \quad F(0) = 0, F(1) = 1 ]

def fibonacci(n):
    if n <= 1:  # 基礎情況
        return n
    else:  # 遞迴步驟
        return fibonacci(n - 1) + fibonacci(n - 2)

這是經典的遞迴解法，但會導致重複計算，效率較低，可以使用動態規劃進行優化。

4.3 樹結構遍歷#

對於樹結構的遍歷（如二叉樹），遞迴非常有效。以下是二叉樹的中序遍歷（中根順序遍歷）的遞迴方法：

def inorder_traversal(node):
    if node is not None:
        inorder_traversal(node.left)
        print(node.value)
        inorder_traversal(node.right)

4.4 分治法算法#

許多分治法算法（如快速排序、合併排序、二分查找）使用遞迴來解決問題： - 快速排序：將數列分為兩部分，分別排序後合併。 - 合併排序：遞迴地分割數列，對每個子數列排序後合併。

4.5 圖的深度優先搜尋 (DFS)#

圖的深度優先搜尋使用遞迴進行節點遍歷，對每個未訪問的鄰居節點遞迴調用 DFS。

def dfs(graph, node, visited):
    if node not in visited:
        print(node)
        visited.add(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited)

5. 遞迴的優缺點#

優點： - 可以簡化問題的求解過程，使得一些算法的實現更加直觀、簡潔。 - 很適合處理樹、圖等層級結構的問題。

缺點： - 性能問題：無優化的遞迴（如計算斐波那契數列）可能導致重複計算，效率低。 - 空間開銷：每次遞迴都會創建一個新的函數調用堆棧，可能導致堆棧溢出，尤其是對於深遞迴調用。 - 可讀性問題：過於複雜的遞迴函數可能難以理解，尤其是多層遞迴時。

6. 尾遞迴優化#

一些編程語言（如 Scheme）支持尾遞迴優化，這意味著編譯器能夠將尾遞迴轉換為迴圈，從而避免堆棧溢出問題，提高性能。然而，Python並不支持尾遞迴優化，因此過深的遞迴依然可能導致堆棧溢出。

7. 小結#

遞迴法是一種強大的編程技術，適用於分治策略、樹結構遍歷和圖的搜尋等問題。然而，它也存在一些性能和空間上的問題，在實際應用中需要注意其優缺點，並在必要時使用優化技巧，如動態規劃或尾遞迴優化來提高效率。