Java 遞迴 (Recursion)

遞迴是指方法呼叫自己的技術。

基本概念

遞迴方法需要：

1. 終止條件：何時停止遞迴
2. 遞迴呼叫：呼叫自己，但問題規模變小

public static void countdown(int n) {
    // 終止條件
    if (n <= 0) {
        System.out.println("發射！");
        return;
    }
    
    // 遞迴主體
    System.out.println(n);
    countdown(n - 1);  // 遞迴呼叫
}

// countdown(3) 輸出：3, 2, 1, 發射！

階乘

public static int factorial(int n) {
    // 終止條件
    if (n <= 1) {
        return 1;
    }
    
    // 遞迴呼叫
    return n * factorial(n - 1);
}

// factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

執行過程：

factorial(5)
= 5 * factorial(4)
= 5 * 4 * factorial(3)
= 5 * 4 * 3 * factorial(2)
= 5 * 4 * 3 * 2 * factorial(1)
= 5 * 4 * 3 * 2 * 1
= 120

費波那契數列

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

// 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

優化版本（記憶化）

public static int fibonacciMemo(int n, int[] memo) {
    if (n <= 1) return n;
    
    if (memo[n] != 0) {
        return memo[n];  // 已計算過
    }
    
    memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
    return memo[n];
}

總和

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

// sum(5) = 5 + 4 + 3 + 2 + 1 = 15

次方

public static int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

// power(2, 3) = 8

最大公因數

public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

// gcd(48, 18) = 6

陣列操作

陣列總和

public static int arraySum(int[] arr, int index) {
    if (index < 0) return 0;
    return arr[index] + arraySum(arr, index - 1);
}

int[] numbers = {1, 2, 3, 4, 5};
int total = arraySum(numbers, numbers.length - 1);  // 15

二分搜尋

public static int binarySearch(int[] arr, int target, int left, int right) {
    if (left > right) return -1;  // 找不到
    
    int mid = left + (right - left) / 2;
    
    if (arr[mid] == target) {
        return mid;
    } else if (arr[mid] > target) {
        return binarySearch(arr, target, left, mid - 1);
    } else {
        return binarySearch(arr, target, mid + 1, right);
    }
}

字串操作

反轉字串

public static String reverse(String s) {
    if (s.isEmpty()) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}

// reverse("hello") = "olleh"

檢查回文

public static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true;
    
    if (s.charAt(0) != s.charAt(s.length() - 1)) {
        return false;
    }
    
    return isPalindrome(s.substring(1, s.length() - 1));
}

河內塔

public static void hanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        System.out.println("移動盤子 1 從 " + from + " 到 " + to);
        return;
    }
    
    hanoi(n - 1, from, aux, to);
    System.out.println("移動盤子 " + n + " 從 " + from + " 到 " + to);
    hanoi(n - 1, aux, to, from);
}

// hanoi(3, 'A', 'C', 'B');

遞迴 vs 迴圈

階乘的迴圈版本

public static int factorialLoop(int n) {
    int result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

尾遞迴

某些語言可以優化尾遞迴，但 Java 不會：

// 尾遞迴形式
public static int factorialTail(int n, int acc) {
    if (n <= 1) return acc;
    return factorialTail(n - 1, n * acc);
}

// 呼叫
factorialTail(5, 1);

Stack Overflow

遞迴太深會造成 StackOverflowError：

public static void infinite(int n) {
    System.out.println(n);
    infinite(n + 1);  // 沒有終止條件
}
// StackOverflowError!

避免方式：

1. 確保有終止條件
2. 確保問題規模會縮小
3. 考慮使用迴圈替代