Recursion.java

import java.util.Arrays;

/**
 * Lab 主題一：遞迴（recursion）。
 *
 * 每個遞迴函式都由兩部分組成：
 *   - 基底情況（base case）：問題小到可以直接回答。
 *   - 遞迴情況（recursive case）：把問題化成「更小的同類問題」，再把答案組合起來。
 *
 * 編譯與執行：javac Recursion.java && java -ea Recursion
 */
public class Recursion {

    /** n! = n × (n-1)!，0! = 1。前置條件：n >= 0 */
    static long factorial(int n) {
        if (n == 0) {                        // 基底情況
            return 1;
        }
        return n * factorial(n - 1);         // 遞迴情況：問題變小（n-1）
    }

    /** 陣列 arr[from..] 的總和：第一個元素 + 其餘元素的總和。 */
    static int sum(int[] arr, int from) {
        if (from >= arr.length) {            // 基底：沒有元素了
            return 0;
        }
        return arr[from] + sum(arr, from + 1);
    }

    /** 反轉字串：最後一個字元 + 反轉「去掉最後一個字元的字串」。 */
    static String reverse(String s) {
        if (s.length() <= 1) {               // 基底：空字串或單一字元
            return s;
        }
        return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1));
    }

    /** 迴文判斷：頭尾相同，且中間也是迴文。 */
    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));
    }

    /** 快速冪：base^exp，利用「平方」讓問題每次減半（分治法）。前置條件：exp >= 0 */
    static long power(long base, int exp) {
        if (exp == 0) {
            return 1;
        }
        long half = power(base, exp / 2);    // 只算一次，再重複使用
        if (exp % 2 == 0) {
            return half * half;
        }
        return half * half * base;
    }

    /**
     * 遞迴二分搜尋（分治法）。
     * @param haystack 已由小到大排序的陣列
     * @return needle 的索引；找不到回傳 -1
     */
    static int binarySearch(int[] haystack, int needle, int lo, int hi) {
        if (lo > hi) {                       // 基底：範圍變空，確定不存在
            return -1;
        }
        int mid = (lo + hi) / 2;
        if (haystack[mid] == needle) {
            return mid;
        } else if (haystack[mid] < needle) {
            return binarySearch(haystack, needle, mid + 1, hi);   // 往右半邊找
        } else {
            return binarySearch(haystack, needle, lo, mid - 1);   // 往左半邊找
        }
    }

    /** 對外的簡潔版本：呼叫者不需要知道 lo/hi 這兩個「多出來的參數」。 */
    static int binarySearch(int[] haystack, int needle) {
        return binarySearch(haystack, needle, 0, haystack.length - 1);
    }

    /** 河內塔：把 n 個盤子從 from 移到 to，回傳移動次數（= 2^n - 1）。 */
    static int hanoi(int n, char from, char to, char via, boolean print) {
        if (n == 0) {
            return 0;
        }
        int moves = hanoi(n - 1, from, via, to, print);   // 先把上面 n-1 個移到暫存柱
        if (print) {
            System.out.println("    盤子 " + n + "：" + from + " → " + to);
        }
        moves = moves + 1;
        moves = moves + hanoi(n - 1, via, to, from, print); // 再把 n-1 個移到目標柱
        return moves;
    }

    /** 沒有基底情況、或永遠碰不到基底情況，就會 StackOverflowError。 */
    static int countDown(int n) {
        if (n == 0) {
            return 0;
        }
        return 1 + countDown(n - 1);
    }

    public static void main(String[] args) {
        System.out.println("=== 遞迴測試 ===");
        assert factorial(0) == 1;
        assert factorial(5) == 120;
        assert factorial(10) == 3628800L;
        System.out.println("  5! = " + factorial(5) + "，10! = " + factorial(10));

        int[] a = {3, 1, 4, 1, 5, 9, 2, 6};
        assert sum(a, 0) == 31;
        assert sum(new int[]{}, 0) == 0;
        System.out.println("  sum" + Arrays.toString(a) + " = " + sum(a, 0));

        assert reverse("").equals("");
        assert reverse("a").equals("a");
        assert reverse("Java").equals("avaJ");
        System.out.println("  reverse(\"Java\") = " + reverse("Java"));

        assert isPalindrome("");
        assert isPalindrome("racecar");
        assert !isPalindrome("Java");
        System.out.println("  isPalindrome(\"racecar\") = " + isPalindrome("racecar"));

        assert power(2, 10) == 1024;
        assert power(3, 0) == 1;
        assert power(7, 3) == 343;
        System.out.println("  2^10 = " + power(2, 10));

        int[] sorted = {1, 3, 5, 7, 9, 11, 13};
        assert binarySearch(sorted, 7) == 3;
        assert binarySearch(sorted, 1) == 0;
        assert binarySearch(sorted, 13) == 6;
        assert binarySearch(sorted, 4) == -1;
        assert binarySearch(new int[]{}, 4) == -1;
        System.out.println("  binarySearch(sorted, 7) = " + binarySearch(sorted, 7));

        System.out.println("  河內塔 3 個盤子：");
        int moves = hanoi(3, 'A', 'C', 'B', true);
        assert moves == 7;
        assert hanoi(10, 'A', 'C', 'B', false) == 1023;
        System.out.println("  共 " + moves + " 步");

        System.out.println("  countDown(1000) = " + countDown(1000));
        try {
            // 遞迴太深：每一層呼叫都要占一個堆疊框（stack frame），堆疊是有限的。
            // 實際能撐幾層取決於 JVM 設定（-Xss）與方法大小，通常是數千到數萬層。
            countDown(1_000_000);
        } catch (StackOverflowError e) {
            System.out.println("  countDown(1000000) → StackOverflowError（堆疊溢位）");
        }
        System.out.println("全部通過。");
    }
}