SyntaxPilot
Courses/Java/Lesson 12

Java · Lesson 12 of 51 · 15 min

Recursion

queued

These are the notes for Java episode 12. You will learn what recursion is (a method that calls itself), why a method with no stopping point crashes with a StackOverflowError, the two parts of every recursive method (base case and recursive case), what happens on the call stack while it runs, tree recursion with the staircase problem (Fibonacci numbers), why naive tree recursion explodes (1.4 billion calls, timed live), how memoization makes it instant, when a loop is the better choice, and what tail position means. Every example below runs as-is in the SyntaxPilot compiler, with its real output from javac 21 (timings vary from machine to machine and run to run).

Before you start, remember from episode 11: a method is a named block of steps; static int fact(int n) takes an int parameter n and returns an int. Every time a method is called, Java gives that call a frame on the call stack to hold its parameters and local variables.

The problem: what number am I in the queue?

You are in a long ration-shop queue and can't see the front. You ask the person ahead: "What's your number? I'll add one." They don't know either, so they ask the person ahead of them: the same question, on a queue one person shorter. Finally the person at the front says "I'm number 1" without asking anyone. That answer travels back, and each person adds 1, until it reaches you.

A big question, answered by asking a smaller copy of the same question, with someone at the end who answers directly. That is recursion.

Factorial: 5 friends on a chai stall bench

Five friends, one bench with five seats. How many seating orders? The first seat has 5 choices, then 4 friends are left for 4 seats: 5 × (ways for 4). Keep going: 5 × 4 × 3 × 2 × 1 = 120.

Multiplying a number by every whole number below it, down to 1, is its factorial, written 5!. Notice the pattern: 5! = 5 × 4!. The factorial of n is n times the factorial of n - 1.

The way we already know, a loop:

public class Main {
    public static void main(String[] args) {
        int n = 5;
        int ways = 1;
        for (int i = 1; i <= n; i++) {
            ways = ways * i;
        }
        System.out.println(n + " friends, " + ways + " ways");
    }
}
5 friends, 120 ways

It works, but it doesn't look like the idea fact(5) = 5 × fact(4).

The obvious attempt: a method that calls itself

public class Main {
    static int fact(int n) {
        return n * fact(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(fact(5));
    }
}

A method that calls itself is called recursion (a recursive method). This one compiles, and then:

Exception in thread "main" java.lang.StackOverflowError
    at Main.fact(Main.java:3)
    at Main.fact(Main.java:3)
    at Main.fact(Main.java:3)
    ... (the same line, 1024 times in all)

Why it crashed

  • fact(5) calls fact(4), which calls fact(3), then fact(2), fact(1), fact(0), fact(-1), fact(-2)... nobody ever answers directly, so the calls never stop.
  • Each call can't finish: it waits for the next call's answer. Every waiting call keeps its frame (its own n) on the call stack.
  • The call stack is a small, fixed area of memory. After thousands of frames it is full, and Java throws a StackOverflowError: the stack overflowed.

The fix: base case + recursive case

In the queue In Java
The front person: "I'm number 1", no asking Base case: if (n == 1) return 1;
Everyone else asks the person ahead (a shorter queue) Recursive case: return n * fact(n - 1);
People waiting for an answer, each remembering their place Call stack frames, one per waiting call
  • Base case: the smallest version of the problem, answered directly, with no more recursive calls. It is what stops the recursion.
  • Recursive case: the method calls itself on a smaller problem (a step closer to the base case) and uses that answer.
public class Main {
    static int fact(int n) {
        if (n == 1) {
            return 1;
        }
        return n * fact(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(fact(5));
        System.out.println(fact(10));
    }
}
120
3628800

Put the base case first, before the recursive call.

Inside the call stack: calls go down, answers come up

Make fact print when it starts and when it has its answer:

public class Main {
    static int fact(int n) {
        System.out.println("call fact(" + n + ")");
        if (n == 1) {
            return 1;
        }
        int r = n * fact(n - 1);
        System.out.println("fact(" + n + ") = " + r);
        return r;
    }

    public static void main(String[] args) {
        System.out.println(fact(4));
    }
}
call fact(4)
call fact(3)
call fact(2)
call fact(1)
fact(2) = 2
fact(3) = 6
fact(4) = 24
24

Real-life example: a stack of plates at a wedding buffet. Each new call is a plate put on top; the top plate is always removed first (last in, first out, which is why it's called a stack).

           push                          pop (answers come back)
         ┌─────────┐
         │ fact(1) │  base case → returns 1
         ├─────────┤
         │ fact(2) │  waits ............ 2 * 1 = 2
         ├─────────┤
         │ fact(3) │  waits ............ 3 * 2 = 6
         ├─────────┤
         │ fact(4) │  waits ............ 4 * 6 = 24
         └─────────┘

Each frame has its own n: there are four different n variables alive at the deepest point, one per frame.

Four rules for every recursive method

  1. A base case, answered without calling itself.
  2. Every call gets smaller, a step closer to the base case.
  3. Trust the smaller call (the "leap of faith"): assume fact(n - 1) is right; don't trace every level in your head.
  4. Use its answer to build yours: n * fact(n - 1).

Tree recursion: the railway footbridge

You climb the footbridge stairs at a railway station, 1 or 2 steps at a time. How many different ways are there to climb n steps?

Think about the last move: you arrived either from step n - 1 (one step) or from step n - 2 (two steps). So:

ways(n) = ways(n - 1) + ways(n - 2)
ways(1) = 1        ways(2) = 2          (base cases)

These numbers (1, 2, 3, 5, 8, 13, ...), each the sum of the two before it, are the Fibonacci numbers. Because each call makes two recursive calls, the calls branch like a tree: this is tree recursion.

public class Main {
    static long ways(int n) {
        if (n <= 2) return n;
        return ways(n - 1) + ways(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(ways(4));
        System.out.println(ways(5));
        System.out.println(ways(10));
    }
}
5
8
89

(An if with a single statement may be written on one line without { }.)

The blow-up: 44 steps

Count the calls with a static variable (a variable that belongs to the class, outside every method, so all calls share it) and time it:

public class Main {
    static long calls = 0;

    static long ways(int n) {
        calls++;
        if (n <= 2) return n;
        return ways(n - 1) + ways(n - 2);
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(ways(44) + " ways");
        System.out.println(calls + " calls");
        long ms = System.currentTimeMillis() - start;
        System.out.println(ms + " ms");
    }
}
1134903170 ways
1402817465 calls
2091 ms

1.4 billion calls for one answer.

                    ways(5)
                 /           \
           ways(4)            ways(3)   ← solved here...
          /       \           /     \
     ways(3)    ways(2)   ways(2)  ways(1)
     ↑ ...and again here
    /      \
 ways(2)  ways(1)

Why: the same smaller questions (ways(3), ways(2), ...) are solved again and again. Each extra step roughly doubles the work. Growth where each step multiplies the work is called exponential; this is the exponential blow-up. 50 steps would take over half a minute.

Memoization: write the answer down

Real-life example: homework. If the same sum appears twice, you don't work it out twice: you write the answer in your notebook the first time and look it up next time.

In Java the notebook is an array, memo. Memoization = store each answer the first time it is computed, and return the stored answer on every later call.

public class Main {
    static long[] memo = new long[100];

    static long ways(int n) {
        if (n <= 2) return n;
        if (memo[n] != 0) return memo[n];
        memo[n] = ways(n - 1) + ways(n - 2);
        return memo[n];
    }

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        System.out.println(ways(44) + " ways");
        System.out.println(ways(90) + " ways");
        long ms = System.currentTimeMillis() - start;
        System.out.println(ms + " ms");
    }
}
1134903170 ways
4660046610375530309 ways
20 ms

Each ways(k) is now computed once, so ways(n) needs about n calls instead of billions. 0 works as "not solved yet" here because no answer is ever 0. Memoization is the first step of dynamic programming, which comes later in the course.

Version Calls for ways(44) Time
Plain tree recursion 1,402,817,465 about 2 seconds
Memoized about 85 a few milliseconds

Recursion vs loops

Even with a correct base case, recursion can be too deep:

public class Main {
    static long sum(int n) {
        if (n == 0) {
            return 0;
        }
        return n + sum(n - 1);
    }

    public static void main(String[] args) {
        System.out.println(sum(1000));
        System.out.println(sum(100000));
    }
}
500500
Exception in thread "main" java.lang.StackOverflowError
    at Main.sum(Main.java:6)
    at Main.sum(Main.java:6)
    ...

It would stop eventually, but 100,000 waiting frames don't fit on the stack. A loop needs no frames:

public class Main {
    public static void main(String[] args) {
        long total = 0;
        for (int i = 1; i <= 100000; i++) {
            total += i;
        }
        System.out.println(total);
    }
}
5000050000
Recursion Loop
Code short, matches "smaller copies" problems sometimes much longer for such problems
Memory one stack frame per waiting call no extra frames
Depth limit a few thousand to tens of thousands of calls, then StackOverflowError none
Best for trees, folders inside folders, staircase-style problems, divide and conquer counting, sums, simple repeats

Anything recursion can do, a loop can do too (sometimes with your own stack).

Tail position: a recursive call is in tail position when it is the very last thing the method does. return n * fact(n - 1); is not a tail call: after it returns, the method still multiplies by n. Some languages turn tail calls into loops automatically (tail-call optimization); Java does not, so deep recursion overflows either way.

Common mistakes (and the real error messages)

Mistake Real message Why Fix
No base case: return n * fact(n - 1); Exception in thread "main" java.lang.StackOverflowError it never stops calling itself add if (n == 1) return 1; first
fact(0) with base case n == 1 java.lang.StackOverflowError 0, -1, -2... never reaches 1 if (n <= 1) return 1;
Computing the answer but not returning it: int r = n * fact(n - 1); Main.java:7: error: missing return statement an int method must return a value on every path return r;
int fact(13) no error, prints 1932053504 (wrong) 13! = 6,227,020,800 doesn't fit in int use long (correct up to 20!)
Recursion 100,000 deep java.lang.StackOverflowError too many frames, even with a base case use a loop
Plain tree recursion for big n no error, just extremely slow the same subproblems are recomputed memoize
Base case after the recursive call StackOverflowError the call happens before the check check the base case first

Mini project: the lucky number of a car number plate

Many people like a "lucky number" on their car's number plate: add the digits, and keep adding until one digit is left. 4589 → 4+5+8+9 = 26 → 2+6 = 8.

  • n % 10 is the last digit, n / 10 drops the last digit.
  • digitSum(n): a single digit is its own sum (base case); otherwise last digit + digitSum of the rest.
  • lucky(n): a single digit is the answer (base case); otherwise lucky(digitSum(n)).
public class Main {
    static int digitSum(int n) {
        if (n < 10) return n;
        return n % 10 + digitSum(n / 10);
    }

    static int lucky(int n) {
        if (n < 10) return n;
        return lucky(digitSum(n));
    }

    public static void main(String[] args) {
        int plate = 4589;
        System.out.println("Digit sum: " + digitSum(plate));
        System.out.println("Lucky number: " + lucky(plate));
    }
}
Digit sum: 26
Lucky number: 8

Try lucky(9999): 36 → 9.

Practice

  1. power(2, 10) recursively: 2^n = 2 × 2^(n-1), and 2^0 = 1.
  2. Count the digits of a number recursively (4589 → 4).
  3. Reverse a String recursively: last character + reverse of the rest (chai → iahc).
  4. Memoize ways(n) and print ways(80).
  5. A countdown: countdown(5) prints 5 4 3 2 1 Liftoff!.
  6. Check a palindrome recursively: compare the first and last characters, then the middle.
Solutions and hints

All of these go inside public class Main, above main.

  1. java static long power(int base, int exp) { if (exp == 0) return 1; return base * power(base, exp - 1); } // power(2, 10) → 1024
  2. java static int countDigits(int n) { if (n < 10) return 1; return 1 + countDigits(n / 10); } // countDigits(4589) → 4
  3. java static String reverse(String s) { if (s.length() <= 1) return s; return s.charAt(s.length() - 1) + reverse(s.substring(0, s.length() - 1)); } // reverse("chai") → iahc
  4. Use the memoized ways from these notes: ways(80) → 37889062373143906, instantly.
  5. java static void countdown(int n) { if (n == 0) { System.out.println("Liftoff!"); return; } System.out.print(n + " "); countdown(n - 1); }
  6. java static boolean isPalindrome(String s) { if (s.length() <= 1) return true; if (s.charAt(0) != s.charAt(s.length() - 1)) return false; return isPalindrome(s.substring(1, s.length() - 1)); } // isPalindrome("madam") → true, isPalindrome("java") → false

Quick quiz

What does f(3) print?

static void f(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    f(n - 1);
    System.out.print(n + " ");
}

A) 3 2 1 B) 3 2 1 1 2 3 C) 1 2 3 3 2 1 D) 3 2 1 0 1 2 3

Answer

B) 3 2 1 1 2 3. Each call prints its n on the way down, waits for f(n - 1), then prints its n again on the way back up (top plate first). f(0) prints nothing.

Interview questions

  1. What is recursion? A method that solves a problem by calling itself on a smaller version of the same problem, until it reaches a base case answered directly.
  2. What happens if a recursive method has no base case? It keeps calling itself; frames pile up on the call stack until it is full and the JVM throws java.lang.StackOverflowError.
  3. Is StackOverflowError an exception you should catch? It is an Error, not an Exception: it signals a serious problem (usually missing/unreachable base case or too-deep recursion). Fix the code instead of catching it.
  4. Why is naive recursive Fibonacci slow? It recomputes the same subproblems; the number of calls grows exponentially (about 1.4 billion calls for n = 44 in our version).
  5. What is memoization? Caching the result of each subproblem the first time it is computed so later calls return it immediately. It turns exponential Fibonacci into linear time.
  6. Recursion or iteration? Recursion for naturally recursive structures (trees, nested folders, divide and conquer); loops for simple repetition or very deep repetition, since loops don't use stack frames.
  7. Does Java do tail-call optimization? No. A recursive call in tail position still uses a new stack frame in Java.
  8. What is stored in a stack frame? The method's parameters, its local variables, and where to continue in the caller when it returns.

Glossary

Term Meaning Example
recursion a method calling itself to solve a smaller copy of the problem fact calls fact
recursive method a method that uses recursion static int fact(int n)
base case the smallest case, answered directly with no recursive call if (n == 1) return 1;
recursive case the part that calls the method on a smaller problem return n * fact(n - 1);
call stack the memory area where Java keeps one frame per running method call fact(4), fact(3), ... waiting
stack frame one call's own box on the call stack: its parameters and local variables each call's own n
last in, first out (LIFO) the newest item is removed first a stack of plates
StackOverflowError the error Java throws when the call stack is full no base case
factorial (n!) n × (n-1) × ... × 1 5! = 120
Fibonacci numbers each number is the sum of the two before it 1, 2, 3, 5, 8, 13
tree recursion each call makes two or more recursive calls ways(n-1) + ways(n-2)
exponential each extra step multiplies the work (here: roughly doubles it) 1.4 billion calls for 44
exponential blow-up the run time explodes because the work grows exponentially naive ways(44)
memoization storing answers to reuse them instead of recomputing memo[n]
dynamic programming solving a problem by reusing answers to its smaller subproblems memoized ways
static variable a variable that belongs to the class, shared by all calls static long calls
tail position the recursive call is the very last thing the method does return f(n - 1);
leap of faith trusting the smaller call to be correct while writing the method assume fact(n-1) works
n % 10 / n / 10 the last digit / the number without its last digit 4589 % 10 = 9, 4589 / 10 = 458

Summary

  • Recursion is a method calling itself on a smaller copy of the problem.
  • Every recursive method needs a base case (stops it) and a recursive case (gets smaller each time). No base case, or one that is never reached, means StackOverflowError.
  • Calls go down the call stack (one frame each), answers come back up, last in, first out.
  • Tree recursion (two calls per call) can explode exponentially; memoization stores answers so each one is computed once.
  • Very deep repetition is safer as a loop: Java does not optimize tail calls.

Next episode: Basics project: a student marks system, using variables, loops, arrays, Strings, StringBuilder, methods and recursion together.