Recursion

New words in this topic, in plain English. Come back here whenever one feels fuzzy.

Recursion

A method calling itself to solve a smaller version of the same problem.

Base case

An input small enough to answer directly, without another recursive call. It's what stops the recursion.

Recursive case

The part that calls the method again with a smaller input and combines the result.

Call stack

The stack of frames for all method calls that have started but not yet returned. Each recursive call adds one frame.

Recursion depth

How many recursive calls are active at the same time, which is how many frames are on the stack.

`StackOverflowError`

The error the JVM throws when a thread's call stack runs out of room, usually from runaway recursion.

Memoisation

Saving the result for each input the first time you compute it, and reusing it instead of recomputing.

Recursion tree

A drawing of every call a recursive method makes, with each call's children below it. It shows how much work is done.

1. 1

   Trace before you run

   Change the call to factorial(5, ""). Write out the full expected trace on paper first: how many lines, and what's the deepest indent? Then run and compare.

2. 2

   Feel the exponential

   In the Fibonacci example, change fib(25) to fib(30) and then fib(35). Note how the call count multiplies by about 11 for every 5 added to n (1.618 to the power 5). Then call fibMemo(35) and compare.

3. 3

   Overflow the stack on purpose

   Write static int depth(int n) { return depth(n + 1); } and call it from main. Look at the start and end of the stack trace, then delete it.

   terminalcopy cmd

   $ java Main

   ── expected output ──

   Exception in thread "main" java.lang.StackOverflowError

   at Main.depth(Main.java:2)

   at Main.depth(Main.java:2)

   at Main.depth(Main.java:2)

   ...

Errors are the best teachers. Make each change, read the error, guess what went wrong, then reveal the answer.

public class Main {
    static int countDown(int n) {
        return countDown(n - 1);
    }
    public static void main(String[] args) {
        countDown(5);
    }
}

1. 1

   A recursive method calls itself. It always has two parts: a base case, a small input it answers directly without recursing (factorial(1) is 1), and a recursive case, which calls itself on a smaller input and builds the answer from that (factorial(n) = n * factorial(n - 1)).

2. 2

   Every call gets its own stack frame with its own copy of the parameters, so factorial(4) and factorial(3) don't interfere. The calls pile up on the call stack until the base case returns, then they finish in reverse order, each using the result of the call above it.

3. 3

   If the base case is missing or never reached, the calls never stop, the stack fills up, and the JVM throws StackOverflowError. The default stack holds thousands of frames, not millions, so deep recursion on large inputs fails even when the logic is right.

4. 4

   Java does not optimise tail calls: even a recursive call in the last position uses a new frame. So any recursion whose depth grows with the input size (like recursing once per element of a long list) is risky in Java; a loop is safer there.

5. 5

   Some recursions repeat work. Naive Fibonacci (fib(n - 1) + fib(n - 2)) calls itself an exponential number of times. Storing answers you've already computed (memoisation) brings it down to a linear number of calls. That idea is the start of dynamic programming.

6. 6

   Recursion shines when the problem is naturally self-similar: trees, nested folders, divide-and-conquer sorts, backtracking searches. The DSA course's Recursion module (/dsa/recursion) trains the thinking pattern in depth: base cases, trusting the recursive call, and recursion trees.

• ↔

  Recursion expresses tree and divide-and-conquer logic clearly, but each level costs a stack frame and Java has no tail-call optimisation. Linear-depth recursion over large inputs should be a loop.

• ↔

  Memoisation turns exponential recursion into linear time, at the cost of memory for the table of answers.

• ↔

  Raising -Xss lets deeper recursion run, but it applies to every thread and multiplies memory use in programs with many threads.

• Done when you can write a recursive method with a correct base case and a recursive case that shrinks the input.

• Done when you can draw the call stack for a small recursive call and say when each frame returns.

• Done when you can recognise StackOverflowError and its causes.

• Done when you can explain why naive Fibonacci is exponential and memoise it.

• Done when you can decide between recursion and a loop for a given problem.