什麼是遞歸？
在編程中，遞歸（Recursion）是指一個方法直接或間接調用自身的過程。理解遞歸的核心在於兩個關鍵點：終止條件（何時停止遞歸）和遞歸關係（如何分解問題）。
想象一下生活中的例子：你想知道一個盒子裏有多少顆糖，盒子是嵌套的，你只能從最外面的盒子開始，每次打開一個盒子看裏面的糖，直到最裏面的盒子。這裏，“打開盒子”就是遞歸操作，而“盒子爲空”就是終止條件。
遞歸的核心原理¶
遞歸的執行過程可以類比爲“剝洋蔥”：每一層調用都是在解決“更小的問題”，直到遇到無法再分解的最小問題（終止條件），然後逐層返回結果。
從計算機執行角度來看，每次遞歸調用都會在內存中創建一個“方法調用棧”的新幀，用於存儲當前方法的參數、局部變量和返回地址。當遇到終止條件時，最內層的方法會先返回結果，然後外層的方法依次計算並返回。
實例1：階乘（Factorial）¶
階乘是遞歸的經典例子，數學定義爲：
- \( n! = n \times (n-1) \times (n-2) \times \dots \times 1 \)
- 特殊情況：\( 0! = 1 \)，\( 1! = 1 \)
遞歸實現思路：
1. 終止條件：當 \( n = 0 \) 或 \( n = 1 \) 時，返回 1。
2. 遞歸關係：當 \( n > 1 \) 時，返回 \( n \times \text{factorial}(n-1) \)。
Java代碼實現：
public class RecursionExample {
// 階乘遞歸方法
public static long factorial(int n) {
// 終止條件：n爲負數時拋出異常（非法參數）
if (n < 0) {
throw new IllegalArgumentException("階乘參數不能爲負數");
}
// 終止條件：n=0或n=1時返回1
if (n == 0 || n == 1) {
return 1;
}
// 遞歸關係：n * (n-1)!
return n * factorial(n - 1);
}
public static void main(String[] args) {
int num = 5;
long result = factorial(num);
System.out.println(num + "的階乘是：" + result); // 輸出：5的階乘是：120
}
}
執行過程分析：
- 調用 factorial(5) → 進入遞歸，需計算 \( 5 \times factorial(4) \)
- factorial(4) → \( 4 \times factorial(3) \)
- factorial(3) → \( 3 \times factorial(2) \)
- factorial(2) → \( 2 \times factorial(1) \)
- factorial(1) → 滿足終止條件，返回 1
- 逐層返回：\( 2 \times 1 = 2 \) → \( 3 \times 2 = 6 \) → \( 4 \times 6 = 24 \) → \( 5 \times 24 = 120 \)
實例2：斐波那契數列（Fibonacci）¶
斐波那契數列定義爲：
- \( F(0) = 0 \)，\( F(1) = 1 \)
- 當 \( n > 1 \) 時，\( F(n) = F(n-1) + F(n-2) \)
遞歸實現思路：
1. 終止條件：當 \( n = 0 \) 時返回 0，當 \( n = 1 \) 時返回 1。
2. 遞歸關係：當 \( n > 1 \) 時，返回 \( F(n-1) + F(n-2) \)。
Java代碼實現：
public class RecursionExample {
// 斐波那契遞歸方法
public static long fibonacci(int n) {
// 終止條件：n爲負數時拋出異常
if (n < 0) {
throw new IllegalArgumentException("斐波那契參數不能爲負數");
}
// 終止條件：n=0返回0，n=1返回1
if (n == 0) {
return 0;
} else if (n == 1) {
return 1;
}
// 遞歸關係：F(n) = F(n-1) + F(n-2)
return fibonacci(n - 1) + fibonacci(n - 2);
}
public static void main(String[] args) {
int n = 5;
long result = fibonacci(n);
System.out.println("斐波那契數列第" + n + "項是：" + result); // 輸出：5
}
}
執行過程分析：
- 計算 \( F(5) \) 時，會遞歸調用 \( F(4) + F(3) \)
- \( F(4) = F(3) + F(2) \)，\( F(3) = F(2) + F(1) \)，以此類推，直到 \( F(1) = 1 \) 和 \( F(0) = 0 \)
- 最終結果：\( F(5) = 5 \)
遞歸的優缺點與注意事項¶
優點：¶
- 邏輯清晰：適合描述有遞歸關係的數學問題（如階乘、斐波那契、漢諾塔）。
- 代碼簡潔：無需複雜循環，直接按數學定義轉化爲代碼。
缺點：¶
- 棧溢出風險：遞歸深度過大時（如計算 \( 1000! \)），會導致
StackOverflowError（調用棧耗盡）。 - 效率問題：部分遞歸存在重複計算（如斐波那契遞歸會重複計算 \( F(3) \) 等），可通過記憶化搜索優化。
注意事項：¶
- 必須有終止條件：否則會無限遞歸（如忘記
n == 0的終止條件，階乘會一直調用factorial(-1)直到崩潰）。 - 參數範圍：遞歸調用時參數需逐步減小，避免無限循環（如傳遞
n+1而非n-1會導致參數增大）。 - 數據類型：階乘結果增長快，需用
long而非int（如 \( 13! = 6227020800 \) 超過int範圍）。
總結¶
遞歸是解決“自相似問題”的利器，核心是分解問題爲更小的子問題並終止於最小問題。初學者建議從簡單場景（如階乘）入手，理解調用棧和終止條件，再逐步應用到複雜場景（如斐波那契、樹的遍歷）。實際開發中，若遞歸深度較大或重複計算嚴重，可改用循環或動態規劃優化，但遞歸的思想仍值得掌握。