Java 遞歸演算法實戰：費波那契數列與河內塔問題解析

遞歸核心概念

遞歸是方法直接或間接呼叫自身，解決可分解為相同子問題的場景。需具備基底條件與遞歸步驟，否則導致堆疊溢位。

案例一：費波那契數列（第 30 項）

規則：F(1)=1, F(2)=1, F(n)=F(n-1)+F(n-2)

public static int fibonacci(int n) {
    if (n <= 2) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}
// 注意：雙重遞歸導致指數級時間複雜度 O(2^n)，大 n 需用動態規劃或矩陣快速冪優化

案例二：河內塔（漢諾塔）

傳說：64 個金盤從 A 柱移至 C 柱，借助 B，大盤不可壓小盤。移動次數 2^64 - 1，極其驚人。

遞歸策略：

1. 將上方 n-1 個盤從 A 借助 C 移至 B
2. 將第 n 個盤從 A 移至 C
3. 將 n-1 個盤從 B 借助 A 移至 C

public static void hanoi(int n, char from, char aux, char to) {
    if (n == 1) {
        System.out.println("移動 " + n + " 號盤子從 " + from + " 到 " + to);
    } else {
        hanoi(n - 1, from, to, aux);
        System.out.println("移動 " + n + " 號盤子從 " + from + " 到 " + to);
        hanoi(n - 1, aux, from, to);
    }
}
// 測試：hanoi(3, 'A', 'B', 'C');

複雜度分析

• 時間：O(2^n) — 必須產生所有移動步驟
• 空間：O(n) — 遞歸呼叫堆疊深度

遞歸雖簡潔，但對大規模問題需考慮效能與堆疊限制，必要時改寫為迭代或加入備忘錄。