Thinking recursively

Real execution, step by step. Press play or scrub with the controls - every variable and array index updates live.

Start here: what this lesson is for

Recursion is the topic where people most often decide they are 'not a natural programmer'. That reaction is almost always caused by being taught it backwards - shown a clever example and asked to trace it in their head.

You are not going to trace anything in your head here. The whole approach in this lesson is to trust the smaller call and check only two things, and the animation above does the tracing for you so you can watch what your head cannot hold.

By the end you will be able to write a recursive method by answering two questions, read a stack of frames without losing your place, and know why deep recursion crashes rather than merely slowing down.

This lesson matters more than its length suggests. Trees, graphs, backtracking and dynamic programming - four later chapters - are all recursion in different clothes. Time spent here pays back four times.

A function that calls itself

Every function you've written so far calls other functions. Recursion is the moment a function calls itself - and the first time you see it, it looks like either a typo or black magic. It's neither. It's the most natural way in the world to solve any problem that contains a smaller copy of itself.

Take factorial: 5! means 5 x 4 x 3 x 2 x 1. Look closely and there's a smaller factorial hiding inside - 5! is just 5 x 4!. And 4! is 4 x 3!. Each version of the problem contains a slightly smaller version, all the way down to 1!, which we simply know: it's 1. No further work needed.

That's the entire recipe, and every recursive function you will ever write has the same two parts: a base case - the input so small you can answer it on the spot - and a recursive case - answer the big problem using the answer to the smaller one. Press play above and watch factorial(5) do exactly this.

Watch the tower rise and fall

Now turn your eyes to the call stack panel in the animation (toggle it on in Panels if it's off). Every time factorial calls itself, a new frame appears - a box holding that call's own private n. factorial(5) sits at the bottom, then factorial(4) stacks on top, then 3, 2, and finally factorial(1).

At factorial(1), the base case fires: it returns 1 without recursing. And now the beautiful part - the tower unwinds. factorial(2) had been waiting for that answer; it multiplies 2 x 1 and returns 2. factorial(3) wakes up, computes 3 x 2 = 6. Then 4 x 6 = 24, then 5 x 24 = 120. Each frame pops as it hands its answer down.

This is the mental model that beats all the confusion: a recursive call doesn't 'jump back into the function' - it creates a brand new copy of it, with its own variables, stacked on top of the caller, which simply pauses and waits.

What happens if you forget to stop

Delete the base case from factorial and run it in your head: factorial(5) calls factorial(4) calls factorial(3)... past zero, into the negatives, forever. Except not forever - each call costs a frame of memory, and the stack has a limit. When the tower hits it, the program dies with the most famous crash in programming: StackOverflowError (Java) - the error an entire website is named after.

So whenever a recursive function misbehaves, check the same two suspects in order: is there a base case, and does every recursive call actually move toward it? A call that doesn't shrink the problem is a call that never ends.

Recursion vs loops - the honest comparison

Could you write factorial with a loop? Absolutely - and for factorial, the loop is arguably simpler. So why learn recursion at all? Because loops flatten; recursion branches. A loop walks a straight line. Recursion can explore a tree of possibilities - and trees, as you'll see from Chapter 8 onward, are everywhere: file systems, decision trees, search spaces, the DOM of every web page.

The cost side: factorial(n) makes n calls doing constant work each - O(n) time, same as the loop. But it also holds up to n frames alive at once, so it spends O(n) memory on the stack, where the loop spends O(1). That trade - elegance and tree-power for stack space - is the recurring theme of this chapter, and the next lesson makes the cost side dramatic.

The two questions that write the method for you

Here is the practical technique, and it deliberately never asks you to picture the whole recursion.

Question one: when is it trivially over? That is the base case. For counting down, it is reaching zero. For a list, it is the empty list. For a tree, it is a null node. Write this first, always - a recursion without a base case is an infinite loop with extra steps.

Question two: assuming the smaller call already works, how do I use its answer? This is the leap people resist, because it feels like assuming the thing you are trying to prove. It is not. It is the same trust you place in any method you did not write: you call Math.max without re-deriving it, and you call factorial(n-1) the same way.

That is the whole method. Note what is missing: at no point did you trace five levels of calls in your head. If you find yourself doing that, you have skipped question two and you will get tired long before you get correct.

// Q1: when is it trivially over?   -> an empty array has sum 0
// Q2: if sumFrom(i+1) already works, how do I use it?
//                                  -> add a[i] to whatever it returns

int sumFrom(int[] a, int i) {
    if (i == a.length) return 0;            // Q1: base case
    return a[i] + sumFrom(a, i + 1);        // Q2: trust the smaller call
}

// the same two questions, on a string
boolean isPalindrome(String s, int lo, int hi) {
    if (lo >= hi) return true;              // Q1: 0 or 1 chars left
    if (s.charAt(lo) != s.charAt(hi)) return false;
    return isPalindrome(s, lo + 1, hi - 1); // Q2: trust the middle
}

sumFrom([3,1,4], 0)
  3 + sumFrom([3,1,4], 1)
      1 + sumFrom([3,1,4], 2)
          4 + sumFrom([3,1,4], 3)
              0            <- base case
          = 4
      = 5
  = 8

isPalindrome("racecar", 0, 6) -> true

Recap, and where this goes next

You now have three things: a way to write recursion (the two questions), a way to read it (the stack of frames, newest on top), and an understanding of why it can crash rather than merely slow down.

The stack overflow is worth holding onto. Every call keeps its own frame alive until it returns, so a recursion a hundred thousand deep needs a hundred thousand live frames - and the call stack is small and fixed. That is a hard limit, not a performance problem, and chapter 7 shows how to escape it by carrying your own stack on the heap.

Next lesson turns recursion into backtracking: the same two questions, plus the discipline of undoing a choice when it fails. After that, recursion mostly disappears as a topic and shows up as the natural way to write everything else - which is the point.