Field notes on recursion. Short version: it is a good tool, it is overused, and the failures are predictable.
What it is
A recursive function solves a problem by calling itself on a smaller piece of the same problem. It needs two things. A base case, where the answer is known without further calls. And a recursive case, which must make progress toward that base case. Miss either and you get an infinite chain of calls.
Factorial is the textbook example: the factorial of 5 is 5 times the factorial of 4, and the factorial of 0 is 1. Fine as a teaching toy. Where recursion earns its place in real code is on naturally nested data: folders containing folders, JSON containing JSON, an organisation chart, an expression tree, a comment thread with replies. The data is recursive, so the code mirrors it, and the loop version would need you to manage the nesting by hand.
What the machine does
Each function call gets a stack frame: a block of memory holding the arguments, local variables and the address to return to. Frames are stacked. When a function returns, its frame is popped.
Recursion to depth n therefore needs n frames alive at once. Calling the factorial of 5 means five frames waiting on each other, the deepest one finishing first, and the answers unwinding back up. The stack is a fixed-size region. Usually a few hundred kilobytes to a few megabytes per thread, depending on language, operating system and settings. Go past it and you get a stack overflow in Java or C, or in Python a RecursionError, because Python imposes its own limit, 1,000 frames by default, which you can raise but should do so carefully.
My opinion: if your recursion depth is bounded by the size of user data, treat it as a bug waiting for an unlucky input. A recursive walk of a folder tree is fine, since trees are rarely 5,000 levels deep. A recursive function that processes a linked list of a million records is not.
The second failure: repeated work
Consider the naive Fibonacci: each number is the sum of the previous two, so a function calls itself twice. For the 40th Fibonacci number, this makes about 331 million calls, because it recomputes the same smaller values over and over. The depth is only 40, so the stack is fine. The time is the problem. The number of calls grows roughly by a factor of 1.6 with each step up in n, exponential growth.
The fix is memoisation: remember each result the first time you compute it and look it up afterwards. Now each value from 1 to 40 is computed once, around forty meaningful calls. Same idea, different algorithm class: from exponential to linear. When you hear “overlapping subproblems”, this is what is meant, and it is the doorway to dynamic programming, which is just memoisation done systematically, often bottom-up with a loop.
Tail calls: a promise not everyone keeps
A tail call is when the recursive call is the very last thing the function does, with nothing left to do after it returns. In principle a compiler can reuse the current frame, making such recursion as cheap as a loop. Some languages guarantee this (Scheme, for one). Many popular ones do not: Python does not perform tail-call elimination, and Java does not either. Do not rely on tail-call optimisation unless you have checked your language and version. Rewriting as a loop, or using an explicit stack, is the portable fix.
Turning recursion into a loop
Anything recursive can be written iteratively with your own stack. For walking a tree, push the root onto a list, then repeat: pop a node, handle it, push its children. The call stack is replaced by a data structure living on the heap, which is limited only by available memory, not by the small fixed stack. This is how you keep a file-search tool from dying on a pathological directory structure.
When I would reach for it
- Data with natural nesting, where depth is small and bounded.
- Divide-and-conquer algorithms like merge sort or binary search, where depth is about log n. A million items is only around twenty levels.
- Backtracking, such as generating permutations or solving puzzles, where the “undo” happens naturally when a call returns.
And when I would not: simple counting or accumulation that a loop expresses plainly, or any case where depth tracks input size without a ceiling.
A habit that helps when debugging: before running a recursive function, write down the base case and say aloud why each call is closer to it. If you cannot, the stack trace will tell you later, usually at the least convenient time. A stack trace thousands of lines long, repeating the same two function names, is the classic sign of a missing or unreachable base case.
Leave a Reply