Classical examples

n! is n × (n - 1)! with 0! = 1. It has one recursive call per level, so n + 1 calls and a stack n + 1 frames deep. You saw its call stack in lesson 5.01.

Watch the range: 12! fits in an int, but 13! does not (6,227,020,800 exceeds 2,147,483,647). A long holds up to 20!. For larger values use BigInteger.

fib(n) = fib(n - 1) + fib(n - 2) with fib(0) = 0 and fib(1) = 1. The recursion has two calls per level, so the tree branches. Run n = 6 in the first animation and look at the tree: fib(3) is computed three times and fib(2) five times.

The number of calls T(n) satisfies T(n) = T(n - 1) + T(n - 2) + 1, which grows like φⁿ with φ ≈ 1.618. The second animation adds a memo array. Each value is computed once, the tree collapses into a chain with cache hits (dashed green), and the cost drops to O(n).

1static long fib(int n) {
2    if (n <= 1) return n;                       // base cases
3    return fib(n - 1) + fib(n - 2);             // two recursive calls
4}

1static long[] memo = new long[100];
2static long fib(int n) {
3    if (n <= 1) return n;                       // base cases
4    if (memo[n] != 0) return memo[n];           // already solved: reuse it
5    return memo[n] = fib(n - 1) + fib(n - 2);   // solve once, remember
6}

To sum the digits of n, take the last digit n % 10 and add the digit sum of the rest, n / 10. The recursion stops at 0.

The number of calls equals the number of digits plus one, so the work is O(log₁₀ n). This pattern, peel off a piece and recurse on the remainder, is the same as walking a list.

1static int sumDigits(int n) {
2    if (n == 0) return 0;               // no digits left
3    return n % 10 + sumDigits(n / 10);  // last digit + the rest
4}

To reverse a[lo..hi], swap the two ends and reverse the inside a[lo + 1..hi - 1]. The base case is a range with zero or one element. The recursion depth is about n / 2.

An iterative two-pointer loop does the same with no stack. The recursive version is a good way to practise stating the invariant: positions outside lo..hi are already final.

1static void reverse(int[] a, int lo, int hi) {
2    if (lo >= hi) return;               // zero or one element: nothing to do
3    swap(a, lo, hi);                    // fix the two outer elements
4    reverse(a, lo + 1, hi - 1);         // reverse the inside
5}

Computing x^n with n multiplications is O(n). Halving the exponent is much faster: x^n = (x^(n/2))² for even n and (x^(n/2))² · x for odd n. One recursive call with the smaller exponent is reused, not repeated.

The depth is ⌊log₂ n⌋ + 1. Try 2^16: only 5 calls and a handful of multiplications. Calling power(x, n / 2) twice instead of storing it in half would silently bring back O(n).

1static long power(long x, int n) {
2    if (n == 0) return 1;                           // x^0 = 1
3    long half = power(x, n / 2);                    // solve a problem half the size
4    return (n % 2 == 0) ? half * half : half * half * x;
5}

Euclid's algorithm uses gcd(a, b) = gcd(b, a % b) and stops when b is 0. It works because any number that divides both a and b also divides the remainder a % b. Try 252 and 105: the pairs go (252, 105), (105, 42), (42, 21), (21, 0), so the answer is 21.

The numbers shrink at least by half every two steps, so it takes O(log min(a, b)) calls. The slowest inputs are consecutive Fibonacci numbers, such as the “Fibonacci pair” preset. The call is a tail call, so it is easy to write as a loop.

1static int gcd(int a, int b) {
2    if (b == 0) return a;               // base case
3    return gcd(b, a % b);               // same answer, smaller numbers
4}

Binary search is recursion on a range: look at the middle, then search the left or right half. The base case is an empty range. The call is a tail call, and the depth is O(log n).

This is the same algorithm you traced in Chapter 16. Compare the animation here with the iterative version: the call stack panel replaces the loop variables lo and hi.

1public static int search(int[] arr, int target, int lo, int hi) {
2    if (lo > hi) {
3        return -1;
4    }
5    int mid = lo + (hi - lo) / 2;
6    if (arr[mid] == target) {
7        return mid;
8    }
9    if (arr[mid] < target) {
10        return search(arr, target, mid + 1, hi);
11    }
12    return search(arr, target, lo, mid - 1);
13}