P-5.2 Recursion, and Trusting It

What this is and why it exists

Recursion is hard to learn for exactly one reason. People try to trace it.

The working method is the opposite. Assume the function already solves smaller cases correctly, and write only the step that makes the problem smaller.

Once that habit is in place, trees become short, sorting becomes short, and searching becomes short. There is one cost to keep in view: the call stack is finite, and careless recursion on large inputs will exhaust it.

The vocabulary

• Base case — the smallest input, answered without recursing.
• Recursive step — the part that reduces the problem and calls itself.
• Frame — the memory one call occupies while it is active.
• Depth — how many calls are active at once.
• Tail call — a recursive call in the very last position of a function.

The mental model

The recipe has two parts and no more. A base case, and a step that makes the problem smaller. A missing or unreachable base case is what produces infinite recursion, so write the base case first, every time, before the interesting part.

Now the mental move that makes the whole thing workable. Trust the recursive call. Assume it already returns the right answer for a smaller input, and write only one step. Tracing three levels down to convince yourself is how people conclude that recursion is hard. It is hard to trace, and you were never supposed to.

Trees are where this pays off most, because the structure is already recursive. A tree is a node with subtrees. A function that handles one node and calls itself on the children is a direct restatement of that definition. Nothing shorter exists, and nothing clearer does either.

The cost is the call stack. Each call takes a frame, so depth costs memory. Recursion whose depth is proportional to the input size will overflow on a large input. This connects straight back to the call stack from the data structures module: it is the same stack, and the limit is the same limit.

So sometimes a loop is the better answer. Simple linear recursion is often clearer as a loop and always cheaper. And some languages convert a call in the final position into a loop for you, which removes the depth cost entirely. Whether yours does is worth checking rather than assuming, because the two behaviours look identical until the input gets large.

What you should now be able to explain or do

Write a base case first and a step that reduces the problem. Trust the recursive call instead of tracing it, and say why tracing is the wrong method. Write a recursive function over a tree as a restatement of the structure. Say what each call costs and when depth becomes a problem. Decide when a loop is better, and check whether your language handles a final-position call as a loop.

Check yourself