The Two Parts Every Recursive Function Needs
- Base case: the simplest possible input, answered directly without another call. Without one, the function recurses forever and crashes.
- Recursive case: calls itself with an input that is strictly closer to the base case.
What Happens on the Call Stack
Calling factorial(5) pushes a new stack frame for every call, then unwinds as each call returns:
Each arrow down is a new stack frame being pushed; each "returns" is a frame popping off as the result bubbles back up.
⚠️ Forgetting the Base Case = Stack Overflow
If factorial never checked n <= 1, it would call itself indefinitely — eventually exceeding the call stack's size limit and crashing with a "Maximum call stack size exceeded" (or equivalent) error.
Recursion vs Iteration: Same Problem, Two Approaches
| Aspect | Recursion | Iteration |
|---|---|---|
| Mechanism | Function calls itself | Loop repeats a block of code |
| Memory | Uses call stack — O(n) extra space for n calls | Usually O(1) extra space |
| Readability | Often clearer for naturally recursive problems | Often clearer for simple linear processing |
| Risk | Stack overflow on deep recursion | No stack risk |
| Best for | Trees, graphs, divide-and-conquer | Flat lists, simple counters, accumulation |
The Same Logic, Two Ways
Both versions compute the same answer. The iterative version uses a single stack frame and a loop counter; the recursive version expresses the mathematical definition of factorial almost word-for-word (n! = n * (n-1)!).
Why Fibonacci Shows Recursion's Weakness
Naive recursive Fibonacci recalculates the same sub-problems over and over — fib(5) calls fib(3) twice, fib(2) three times, and so on — leading to exponential O(2ⁿ) time. This is exactly the kind of waste that memoization fixes by caching results of sub-problems already computed, and it connects directly to Big O analysis when reasoning about algorithm cost.
Tail Call Optimization
A tail call is a recursive call that is the very last operation in a function — nothing happens after it returns. Some languages (Scheme, Erlang) guarantee tail call optimization: they reuse the current stack frame instead of pushing a new one, making tail-recursive functions run in constant stack space, just like a loop.
⚠️ JavaScript Mostly Doesn't Optimize Tail Calls
Despite being specified in ES2015, most JavaScript engines (including V8/Chrome/Node) never shipped tail call optimization. Writing tail-recursive JS code does not protect you from stack overflows the way it would in Scheme or Erlang.
💡 Rule of Thumb
If you can express the problem as "solve a smaller version of this same problem, then combine," reach for recursion. If you're just walking through a flat sequence once, a loop is simpler and safer.
How We Research and Update This Guide
We test the underlying formula or workflow, compare outputs with reliable references, and revise examples whenever the page content changes.
- The workflow or formula is tested directly in the tool and compared against independent reference examples.
- Examples are kept practical so readers can verify the result without hidden assumptions.
- Pages are revised whenever the interface, calculation flow, or surrounding guidance materially changes.
Frequently Asked Questions — Recursion
Recursion is when a function calls itself to solve a smaller version of the same problem, until it reaches a base case that can be answered directly without further calls. Each recursive call is pushed onto the call stack, and results are combined as calls return — making recursion a natural fit for problems that are naturally defined in terms of smaller versions of themselves, like tree traversal or factorial.
The base case is the condition under which the function stops calling itself and returns a direct answer — without it, recursion never terminates and causes a stack overflow. The recursive case is where the function calls itself again with a smaller or simpler input, moving closer to the base case on every call.
Every recursive call adds a new stack frame to the call stack, holding that call's local variables and return address. Each frame uses memory, and the call stack has a fixed size limit. If recursion goes too deep — for example, processing a list with a million items recursively — the stack frame limit is exceeded and the program crashes with a stack overflow error.
Tail call optimization (TCO) is a compiler/runtime technique that reuses the current stack frame for a recursive call if that call is the very last operation in the function (a "tail call"), instead of pushing a new frame. This turns tail-recursive functions into something as memory-efficient as a loop. JavaScript engines mostly do not implement TCO; some languages like Scheme, Erlang, and certain Lisp dialects guarantee it.
Generally yes, in most mainstream languages — each recursive call has function-call overhead (creating a stack frame, pushing arguments, returning) that a simple loop avoids. However, for problems that are naturally recursive (like tree or graph traversal), recursive code is often dramatically simpler and easier to prove correct, and the performance difference rarely matters outside hot loops.
Use recursion when the problem has a naturally recursive structure — tree traversal, graph DFS, divide-and-conquer algorithms (merge sort, quick sort), or parsing nested data (JSON, file system directories). Use iteration when processing a flat, linear sequence where a simple loop is just as clear and avoids stack depth concerns.