public class Main {
    static long factorial(int n) {
        if (n <= 1) return 1;                 // base case
        return n * factorial(n - 1);          // recursive case: smaller input
    }

    static int sumDigits(int n) {
        return n < 10 ? n : n % 10 + sumDigits(n / 10);
    }

    static String reverse(String s) {
        return s.isEmpty() ? "" : reverse(s.substring(1)) + s.charAt(0);
    }

    public static void main(String[] args) {
        System.out.println(factorial(5) + " " + factorial(20));
        System.out.println(sumDigits(9875));
        System.out.println(reverse("stack"));
    }
}

120 2432902008176640000
29
kcats

public class Main {
    static int depth = 0;

    static void dive() {
        depth++;
        dive();                               // no base case
    }

    public static void main(String[] args) {
        try {
            dive();
        } catch (StackOverflowError e) {      // an Error, not an Exception
            System.out.println("StackOverflowError after " + (depth > 1000 ? "thousands of" : "few") + " calls");
        }
    }
}

StackOverflowError after thousands of calls

import java.util.*;

public class Main {
    static int calls = 0;

    static long fibNaive(int n) {
        calls++;
        return n < 2 ? n : fibNaive(n - 1) + fibNaive(n - 2);    // O(2^n)
    }

    static Map<Integer, Long> memo = new HashMap<>();
    static long fibMemo(int n) {
        if (n < 2) return n;
        Long cached = memo.get(n);
        if (cached != null) return cached;
        long v = fibMemo(n - 1) + fibMemo(n - 2);                // O(n)
        memo.put(n, v);
        return v;
    }

    static long fibIter(int n) {                                 // O(n) time, O(1) space
        long a = 0, b = 1;
        for (int i = 0; i < n; i++) { long t = a + b; a = b; b = t; }
        return a;
    }

    public static void main(String[] args) {
        System.out.println(fibNaive(25) + " in " + calls + " calls");
        System.out.println(fibMemo(90) + " " + fibIter(90));
    }
}

75025 in 242785 calls
2880067194370816120 2880067194370816120

import java.util.*;

public class Main {
    static int binarySearch(int[] a, int target, int lo, int hi) {
        if (lo > hi) return -1;
        int mid = (lo + hi) >>> 1;
        if (a[mid] == target) return mid;
        return a[mid] < target ? binarySearch(a, target, mid + 1, hi)
                               : binarySearch(a, target, lo, mid - 1);
    }

    static void subsets(int[] nums, int i, Deque<Integer> cur, List<String> out) {
        if (i == nums.length) { out.add(cur.toString()); return; }
        subsets(nums, i + 1, cur, out);            // exclude nums[i]
        cur.addLast(nums[i]);
        subsets(nums, i + 1, cur, out);            // include nums[i]
        cur.removeLast();                          // backtrack
    }

    static void hanoi(int n, char from, char to, char via, List<String> moves) {
        if (n == 0) return;
        hanoi(n - 1, from, via, to, moves);
        moves.add(from + ">" + to);
        hanoi(n - 1, via, to, from, moves);
    }

    public static void main(String[] args) {
        System.out.println(binarySearch(new int[]{1, 3, 5, 7, 9}, 7, 0, 4));
        List<String> out = new ArrayList<>();
        subsets(new int[]{1, 2, 3}, 0, new ArrayDeque<>(), out);
        System.out.println(out);
        List<String> moves = new ArrayList<>();
        hanoi(3, 'A', 'C', 'B', moves);
        System.out.println(moves.size() + " moves: " + moves);
    }
}

3
[[], [3], [2], [2, 3], [1], [1, 3], [1, 2], [1, 2, 3]]
7 moves: [A>C, A>B, C>B, A>C, B>A, B>C, A>C]