資料結構：遞迴
遞迴（Recursion）是程式設計中一個重要且強大的概念，尤其在處理資料結構與演算法問題時，經常扮演關鍵角色。遞迴能讓程式邏輯更簡潔，特別適合解決具有重複性質或自我相似性的問題。
一、何謂遞迴？
遞迴是指函數在其定義或執行過程中直接或間接呼叫自身的編程技巧。簡而言之，遞迴的基本結構包含兩個要素：
- 基本情況（Base Case）：定義遞迴何時停止的條件，避免無限遞迴。
- 遞迴情況（Recursive Case）：問題的解決方式是將其分解為一個或多個更小的相同問題，並呼叫自身來解決這些子問題。
二、遞迴的基本範例
範例 1：階乘
階乘的數學定義如下：
n! = n * (n - 1) * (n - 2) * ... * 1透過遞迴實現：
int factorial(int n) {
if (n == 0 || n == 1) {
return 1; // 基本情況
}
return n * factorial(n - 1); // 遞迴情況
}範例 2：費波那契數列
費波那契數列定義如下：
F(n) = F(n - 1) + F(n - 2)，其中 F(0) = 0，F(1) = 1遞迴實現：
int fibonacci(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fibonacci(n - 1) + fibonacci(n - 2);
}三、遞迴的應用
1. 資料結構中的應用
(1) 樹的遍歷
遞迴是處理樹形結構的理想工具。例如二元樹的前序、中序、後序遍歷：
struct Node {
int data;
Node *left;
Node *right;
};
void inorder(Node *root) {
if (root == nullptr) return;
inorder(root->left);
cout << root->data << " ";
inorder(root->right);
}(2) 分治法（Divide and Conquer）
像是合併排序（Merge Sort）與快速排序（Quick Sort）等演算法，都是透過遞迴將問題不斷分解，再合併解決。
2. 解決組合問題
遞迴可用於求解排列、組合等問題。例如：求解 n 個數字中選取 k 個的所有可能組合。
四、遞迴的優缺點
優點：
- 程式碼簡潔，邏輯表達清晰。
- 尤其適用於樹形結構與分治問題。
缺點：
- 可能導致大量重複計算，造成效能低落。例如費波那契遞迴。
- 過深的遞迴可能導致堆疊溢位（Stack Overflow）。
五、遞迴性能優化技巧
1. 記憶化（Memoization）
將已經計算過的結果儲存起來，以避免重複計算。例如：
unordered_map<int, int> memo;
int fibonacci(int n) {
if (n <= 1) return n;
if (memo.count(n)) return memo[n];
return memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
}2. 尾遞迴優化（Tail Recursion Optimization）
若遞迴呼叫是函數的最後一步，某些編譯器能進行尾遞迴優化，以避免額外的堆疊開銷。例如：
int factorialTail(int n, int result = 1) {
if (n == 0) return result;
return factorialTail(n - 1, n * result);
}六、遞迴與迴圈的比較
| 特性 | 遞迴 | 迴圈 |
|---|---|---|
| 可讀性 | 高，邏輯清晰 | 較低，有時複雜 |
| 效能 | 可能低於迴圈 | 通常較高 |
| 空間複雜度 | 需要堆疊開銷 | 通常較小 |
| 適用情境 | 適合樹、分治等問題 | 適合線性循環處理 |
七、結論
遞迴是資料結構與演算法領域不可或缺的工具，特別在解決樹形結構、分治問題及組合計算時，表現尤為突出。然而，遞迴並非萬能，應根據具體問題選擇最合適的解法。善用遞迴並搭配適當的優化策略，將能讓我們寫出更簡潔高效的程式碼。