什麼是遞歸？
在計算機科學中，遞歸（Recursion） 是指一個函數在其定義中調用自身的過程。遞歸是一種強大的編程技巧，特別適用於解決具有“自相似”結構的問題，比如樹的遍歷、階乘計算、斐波那契數列等。
在 Java 中，遞歸函數必須滿足兩個基本條件：
- 基準條件（Base Case）：遞歸必須有一個明確的終止條件，否則會導致無限遞歸，最終引發
StackOverflowError。 - 遞歸條件（Recursive Case）：函數在每次調用時，問題規模應逐步縮小，向基準條件靠近。
遞歸的基本結構
public returnType recursiveMethod(parameters) {
// 基準條件：終止遞歸
if (baseCondition) {
return baseValue;
}
// 遞歸調用：問題規模縮小
return recursiveMethod(modifiedParameters);
}經典遞歸案例
1. 計算階乘（Factorial）
階乘是遞歸最經典的例子之一。n! = n × (n-1) × ... × 1
public static int factorial(int n) {
// 基準條件
if (n <= 1) {
return 1;
}
// 遞歸調用
return n * factorial(n - 1);
}測試代碼：
System.out.println(factorial(5)); // 輸出：1202. 斐波那契數列（Fibonacci）
斐波那契數列定義為：F(0)=0, F(1)=1, F(n)=F(n-1)+F(n-2)
public static int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}⚠️ 注意：上述實現時間複雜度為 O(2^n)，效率極低。實際開發中建議使用動態規劃或記憶化優化。
3. 二叉樹的前序遍歷
假設我們有如下二叉樹節點類：
class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) { val = x; }
}遞歸實現前序遍歷（根 → 左 → 右）：
public void preorderTraversal(TreeNode root) {
if (root == null) return; // 基準條件
System.out.print(root.val + " "); // 訪問根節點
preorderTraversal(root.left); // 遍歷左子樹
preorderTraversal(root.right); // 遍歷右子樹
}遞歸 vs 循環
|
特性
|
遞歸
|
循環（迭代）
|
|
代碼簡潔性
|
更簡潔、直觀
|
有時邏輯較複雜
|
|
性能
|
函數調用開銷大，可能棧溢出
|
效率高，內存佔用少
|
|
適用場景
|
樹、圖、分治等結構
|
簡單重複任務
|
✅ 建議：對於簡單問題（如求和、計數），優先使用循環；對於天然遞歸結構（如樹、回溯），使用遞歸更清晰。
遞歸的常見陷阱
1. 忘記設置基準條件
// 錯誤示例：無限遞歸！
public static void badRecursion() {
badRecursion(); // 沒有退出條件
}運行結果：Exception in thread "main" java.lang.StackOverflowError
2. 遞歸深度過大
即使有基準條件，如果輸入數據過大（如 factorial(10000)），仍可能導致棧溢出。
解決方案：
- 改用迭代
- 使用尾遞歸優化（Java 不支持尾遞歸優化，需手動轉換）
- 增加 JVM 棧大小（
-Xss參數）
尾遞歸簡介（Java 中的侷限）
尾遞歸是指遞歸調用是函數的最後一個操作。某些語言（如 Scala、Scheme）會自動優化尾遞歸為循環，但 Java 不支持尾遞歸優化。
例如，階乘的尾遞歸寫法：
public static int factorialTail(int n, int acc) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc);
}
// 調用方式
factorialTail(5, 1); // 120雖然邏輯上是尾遞歸，但在 Java 中依然會消耗棧空間。
