Article URL: https://blog.gaborkoos.com/posts/2026-05-09-Your-Recursion-Is-Lying-to-You/ Comments URL: https://news.ycombinator.com/item?id=49089406 Points: 4 # Comments: 4

Recursion is one of those ideas developers learn early and trust for years. If the recursive step is simple and the base case is correct, the code feels clean and safe. It is elegant for a reason: many problems are naturally recursive, and the code often mirrors how we explain the logic out loud. For tree walks, nested structures, and divide-and-conquer patterns, recursion can be easier to read than explicit loops. The catch is physical limits. Even with a correct base case and sound logic, each recursive call still consumes stack space. At some depth, you crash with stack overflow. If you read Your Debounce Is Lying to You and Your Throttling Is Lying to You, this is the recursion version of the same pattern: elegant abstraction, hidden operational edge. Even dependency management can lie to you, as explored in Your Package Manager Is Lying to You. For a different category of silent failure, Your JS Date Is Lying to You covers the parsing, mutation, and timezone traps built into the JavaScript Date API. You can run everything below directly in a browser console. Let's start simple: a recursive sum of all integers from 1 to n. What just happened? The function is logically correct, but each call to sum stays on the stack until the one below it returns. At depth 100,000 the runtime runs out of stack space and throws. It has nothing to do with the result being wrong, it is purely a physical limit on how many nested frames the runtime can hold at once. The usual next step is tail call optimization. The idea is simple: make the recursive call the last thing the function does, so the runtime can reuse the same frame instead of pushing a new one. Note that sum is not tail-recursive, even though the recursive call appears on the last line. After sum(n - 1) returns, there is still pending work: the result must be added to n. A call is only in tail position when its return value is forwarded immediately, with no pending computation afterward.