Look at this and tell me what it returns.

function f(n) {
    if (n <= 1) return 1;
    return n * f(n - 1);
}

Most people who have written code for two years can answer it: factorial. But ask the same people to mentally execute f(5) step by step and a surprising number stall around the third level of nested calls. That stall is the whole point of this article. Recursion stops being scary the moment you stop trying to simulate the call stack in your head.

For years I read recursion the wrong way. I would trace each call, push frames in my head, pop them, write down return values, and inevitably lose track around depth four. Then a senior engineer in a code review made one offhand comment that rewired how I think about it: stop simulating, start trusting. That is the mental model I want to share.

Read recursion as a contract, not a trace

A recursive function is a contract you make with yourself. The contract says: "if smaller versions of this problem are solved correctly, I can solve the current size correctly". You do not need to verify that the smaller calls work. You just need to assume they do, and check that your combination step is right.

For f(n) = n * f(n - 1) with the base case n <= 1 returns 1, the contract is:

• I trust f(n - 1) to give me the factorial of n - 1.
• I multiply by n to extend it to the factorial of n.

That is the entire job. Once the contract is right, the recursion is right, regardless of how deep the trace goes. This is the same mental shift that makes induction tractable: you do not prove every case, you prove the step.

The four parts of every recursive function

If you write a recursive function and any of these four parts is missing, the function is wrong, full stop.

1. A base case. The smallest input where the answer is known directly. No further calls. If the base case is missing, you get infinite recursion and a stack overflow.
2. A recursive case. The rule for solving size n in terms of one or more strictly smaller subproblems.
3. Progress toward the base case. Each recursive call must operate on input that is closer to the base case than the current input. "Smaller" can mean a smaller number, a shorter list, a tree subnode, anything that monotonically approaches the base.
4. Combination. What you do with the result(s) from the recursive call(s) before returning. Multiplying, summing, choosing the max, concatenating, you name it.

When I am debugging a recursive function, I check these four parts in order. About 80 percent of the bugs I write live in the progress step (an off-by-one that makes a call repeat the same input forever) or in the combination step (forgetting to add the current node's value before returning).

Tracing without losing your mind

When you really do need to trace, draw the call tree on paper or a whiteboard. Do not try to do it in your head past depth three. Here is f(4), expanded:

f(4)
├── 4 * f(3)
│        ├── 3 * f(2)
│        │        ├── 2 * f(1)
│        │        │        └── 1   ← base case
│        │        └── returns 2
│        └── returns 6
└── returns 24

That tree is what the call stack looks like at maximum depth. The leftmost path is what is currently "on" the stack, waiting for the deeper calls to return. When you read it from bottom to top, the values bubble up: 1, then 2, then 6, then 24. The diagram is more honest than the source code, because it shows which calls are open at the same time.

Where recursion shines, and where I avoid it

This is the section I wish I had read earlier. Recursion is not always the right tool, even when the problem is naturally recursive.

Recursion is great for tree and graph problems, divide-and-conquer algorithms (merge sort, quick sort), parsing, and backtracking. It is the natural shape of the problem, and an iterative version of, say, depth-first traversal is genuinely uglier. I reach for it without thinking.

Recursion is bad for problems where the depth grows with the input size and the language has no tail-call optimization. JavaScript does not eliminate tail calls in any major engine. Python deliberately caps recursion at about 1000 frames. If you are summing a million numbers, a recursive sum will overflow the stack long before it overflows anything else. The iterative version does not.

My default rule: if I can comfortably write the iterative version and it is not significantly less readable, I write the iterative version. If the iterative version requires me to manage an explicit stack or a complicated state machine, I keep the recursion. Tree traversals almost always stay recursive. List sums almost always become iterative.

The bug that always catches me

The single most common recursion mistake I make, even now, is forgetting that recursive calls return values I have to actually use. Look at this attempt at counting nodes in a binary tree:

def count(node):
    if node is None:
        return 0
    count(node.left)
    count(node.right)
    return 1

It always returns 1. Every recursive call computes a value and discards it. The fix is one line:

def count(node):
    if node is None:
        return 0
    return 1 + count(node.left) + count(node.right)

The trap is that the broken version compiles, runs without error, and returns a number. It just returns the wrong number. Code review catches this every time it is asked to.

"To understand recursion, you must first understand recursion"

The joke is older than I am, and it is funny because it is honest. The reason recursion clicks for people is exactly the reason it does not click for them at first: you have to take the recursive step on faith. You have to trust the contract. You have to assume the smaller call returns what it claims, and then build on that.

When I teach this to interns, I write three lines on the whiteboard: "trust the recursion. check the base case. check the progress." Those three lines, in that order, are the entire framework. You can solve almost every recursive interview problem by following them. The structural traps (missing base case, no progress, broken combination) become visible once you stop trying to trace and start trying to trust. Recursion is not magic. It is a contract you write with yourself, and the only thing that makes it intimidating is the assumption that you have to verify the whole tree of calls. You do not. You just have to verify one level, and induction takes care of the rest.