Recursive Algorithms

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

mystery(7) = 7 + mystery(5)
mystery(5) = 5 + mystery(3)
mystery(3) = 3 + mystery(1)
mystery(1) = 1 + mystery(-1)
mystery(-1) = 0          ← base case

public static String mystery(String s) {
    if (s.length() <= 1) return s;
    return s.charAt(s.length() - 1) + mystery(s.substring(0, s.length() - 1));
}

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

                f(5)
              /      \\
          f(4)        f(3)
         /    \\      /    \\
      f(3)   f(2)  f(2)  f(1)
     /   \\   /  \\   /  \\
  f(2) f(1) f(1) f(0) f(1) f(0)
  / \\
 f(1) f(0)

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

System.out.println(gcd(48, 18));  // 6

public static int fastPower(int base, int exp) {
    if (exp == 0) return 1;
    if (exp % 2 == 0) {
        int half = fastPower(base, exp / 2);
        return half * half;
    }
    return base * fastPower(base, exp - 1);
}

public static boolean contains(int[] arr, int target, int lo, int hi) {
    if (lo > hi) return false;
    int mid = (lo + hi) / 2;
    if (arr[mid] == target) return true;
    if (target < arr[mid]) return contains(arr, target, lo, mid - 1);
    return contains(arr, target, mid + 1, hi);
}

public static boolean isSorted(int[] arr, int index) {
    if (index >= arr.length - 1) return true;
    if (arr[index] > arr[index + 1]) return false;
    return isSorted(arr, index + 1);
}

public class TowerOfHanoi {
    public static void move(int disks, String from, String to, String spare) {
        if (disks == 1) {
            System.out.println("Move disk 1 from " + from + " to " + to);
            return;
        }
        move(disks - 1, from, spare, to);     // move n-1 disks to spare
        System.out.println("Move disk " + disks + " from " + from + " to " + to);
        move(disks - 1, spare, to, from);     // move n-1 disks from spare to target
    }
    
    public static void main(String[] args) {
        move(3, "A", "C", "B");
    }
}

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C