// Week 12 – Classic recursive functions
// Run: java RecursionExamples.java
public class RecursionExamples {

    // Sum of the elements of an array: the first element + the sum of the rest
    static int sum(int[] a, int from) {
        if (from == a.length) return 0;                 // the sum of an empty part is 0
        return a[from] + sum(a, from + 1);
    }

    // Exponentiation: x^n = x · x^(n−1) – O(n) calls
    static long power(long x, int n) {
        if (n == 0) return 1;
        return x * power(x, n - 1);
    }

    // Fast exponentiation: x^n = (x^(n/2))² – O(log n) calls
    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;
    }

    // Reversing a string: the first character goes to the end
    static String reverse(String s) {
        if (s.isEmpty()) return s;
        return reverse(s.substring(1)) + s.charAt(0);
    }

    // Palindrome: the first and the last are equal, and the inner part is a palindrome too
    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);
    }

    // Euclidean algorithm recursively (week 1)
    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);   // tail recursion
    }

    // Binary search recursively (week 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);
    }

    // Number of digits
    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));
    }
}