// 第 12 周 – 经典的递归函数
// 运行：java RecursionExamples.java
public class RecursionExamples {

    // 数组元素之和：第一个元素 + 其余部分的和
    static int sum(int[] a, int from) {
        if (from == a.length) return 0;                 // 空部分的和为 0
        return a[from] + sum(a, from + 1);
    }

    // 乘方：x^n = x · x^(n−1) – O(n) 次调用
    static long power(long x, int n) {
        if (n == 0) return 1;
        return x * power(x, n - 1);
    }

    // 快速幂：x^n = (x^(n/2))² – O(log n) 次调用
    static long fastPower(long x, int n) {
        if (n == 0) return 1;
        long half = fastPower(x, n / 2);
        return (n % 2 == 0) ? half * half : half * half * x;
    }

    // 字符串逆序：第一个字符放到末尾
    static String reverse(String s) {
        if (s.isEmpty()) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    // 回文：第一个和最后一个相等，并且中间部分也是回文
    static boolean isPalindrome(String s, int i, int j) {
        if (i >= j) return true;
        return s.charAt(i) == s.charAt(j) && isPalindrome(s, i + 1, j - 1);
    }

    // 递归的欧几里得算法（第 1 周）
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);   // 尾递归
    }

    // 递归的二分查找（第 2 周）
    static int binarySearch(int[] a, int x, int lo, int hi) {
        if (lo > hi) return -1;
        int mid = lo + (hi - lo) / 2;
        if (a[mid] == x) return mid;
        if (a[mid] < x) return binarySearch(a, x, mid + 1, hi);
        return binarySearch(a, x, lo, mid - 1);
    }

    // 位数
    static int digits(int n) {
        return n < 10 ? 1 : 1 + digits(n / 10);
    }

    public static void main(String[] args) {
        int[] a = { 3, 1, 4, 1, 5, 9, 2, 6 };
        System.out.println("sum = " + sum(a, 0));
        System.out.println("power(2, 10) = " + power(2, 10) + ", fastPower(3, 13) = " + fastPower(3, 13));
        System.out.println("reverse(\"recursion\") = " + reverse("recursion"));
        System.out.println("isPalindrome(\"racecar\") = " + isPalindrome("racecar", 0, 6) + ", (\"recursion\") = " + isPalindrome("recursion", 0, 8));
        System.out.println("gcd(1071, 462) = " + gcd(1071, 462));
        int[] s = { 2, 5, 8, 12, 16, 23, 38, 56, 72, 91 };
        System.out.println("binarySearch(23) = " + binarySearch(s, 23, 0, s.length - 1));
        System.out.println("digits(2026) = " + digits(2026));
    }
}