Java 遞歸演算法入門：費波那契數列、爬樓梯、漢諾塔與九九乘法表實作

核心概念

遞歸：方法直接或間接呼叫自身。必須有基準情況 結束遞歸，並向基準情況收斂。

經典案例一：兔子繁殖 (費波那契數列)

規則：第 3 個月開始每月產一對，滿 3 個月的兔子也開始產。每月總數 = 上月總數 + 上上月總數。

public static int rabbit(int month) {
    if (month == 1 || month == 2) return 1;
    return rabbit(month - 1) + rabbit(month - 2);
}

經典案例二：爬樓梯

N 階樓梯，每步可跨 1 或 2 階。走法數 f(n) = f(n-1) + f(n-2)。

public static int climbStairs(int n) {
    if (n <= 2) return n;
    return climbStairs(n - 1) + climbStairs(n - 2);
}

經典案例三：漢諾塔

移動 n 個盤子從 A 到 C (借助 B)。步驟：移動 n-1 到 B → 移動最大到 C → 移動 n-1 從 B 到 C。移動次數 f(n) = 2*f(n-1) + 1。

public static int hanoiMoves(int n) {
    if (n == 1) return 1;
    return 2 * hanoiMoves(n - 1) + 1;
}
// 遞歸列印移動步驟
public static void hanoi(int n, char from, char aux, char to) {
    if (n == 1) { System.out.println(from + " -> " + to); return; }
    hanoi(n - 1, from, to, aux);
    System.out.println(from + " -> " + to);
    hanoi(n - 1, aux, from, to);
}

經典案例四：遞歸列印九九乘法表

public static void printMultiplicationTable(int i) {
    if (i == 1) { System.out.println("1*1=1"); return; }
    printMultiplicationTable(i - 1); // 先列印上一行
    for (int j = 1; j <= i; j++) {
        System.out.print(j + "*" + i + "=" + (j*i) + " ");
    }
    System.out.println();
}

遞歸 vs 迭代

遞歸適合邏輯天然遞歸的問題 (樹、圖、分治)，大量重複計算場景需配合記憶化或改寫為迭代/動態規劃。