Recursion is the programming concept most beginners memorise and most seniors misuse. It maps directly onto problems with self-similar structure — trees, graphs, combinatorics — but reaches for it on flat lists or unbounded input causes stack overflows and puzzling bugs. This is the 2026 guide to understanding recursion well enough to know when to avoid it.
What changed in 2026
- LLM code completions over-produce recursion. AI assistants often suggest elegant recursive solutions that blow the stack on real data. Developers need to recognise when to push back.
- Python's default recursion limit is still 1 000. Despite proposals, CPython 3.13 has not changed
sys.setrecursionlimit. Deep recursion in Python requires explicit iteration or sys.setrecursionlimit + risk.
- V8 and modern JS runtimes still do not guarantee TCO. The ECMAScript tail-call spec was written but never universally implemented. Do not rely on it in production JS.
- Rust and Haskell remain the safe zones. Rust's
stacker crate and Haskell's lazy evaluation make deep recursion manageable with explicit tools.
How recursion works
A recursive function calls itself with a smaller version of the problem. Two parts are non-negotiable:
- Base case — the condition where the function stops and returns a concrete value.
- Recursive case — the call that moves toward the base case.
def factorial(n: int) -> int:
if n == 0: # base case
return 1
return n * factorial(n - 1) # recursive case
Each call pushes a frame onto the call stack. factorial(5) creates 6 frames. factorial(100_000) crashes Python with RecursionError.
The call stack in practice
Every function call consumes stack space. The default stack size is ~1–8 MB depending on OS and runtime. At ~10 000–50 000 frames most runtimes throw a stack overflow.
factorial(5)
factorial(4)
factorial(3)
factorial(2)
factorial(1)
factorial(0) → 1
→ 1
→ 2
→ 6
→ 24
→ 120
For inputs where depth could exceed a few thousand, convert to an explicit loop.
Tail recursion and its limits
A tail call is when the recursive call is the very last operation — no work happens after it returns.
// Tail-recursive (last operation is the recursive call)
function factorial(n, acc = 1) {
if (n === 0) return acc;
return factorial(n - 1, n * acc); // tail call
}
Languages with guaranteed TCO (Scheme, Elixir, Scala) optimise this into a loop internally. JavaScript, Python, and Java do not. Even though V8 partially implements it, you cannot rely on it across engines. Always use an explicit loop for unbounded depth in these languages.
Memoisation: fixing exponential recursion
Naive recursive Fibonacci has O(2^n) time complexity because the same subproblems are solved repeatedly.
# Naive — O(2^n), unusable above n ≈ 40
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
# Memoised — O(n)
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n <= 1:
return n
return fib(n - 1) + fib(n - 2)
Any recursion with overlapping subproblems needs memoisation or bottom-up dynamic programming. See Dynamic programming explained in 2026 for the full treatment.
Where recursion shines: trees and graphs
Tree traversal is the canonical recursive use case. The call stack mirrors the tree depth, which is usually O(log n) for balanced trees.
interface TreeNode {
value: number;
left?: TreeNode;
right?: TreeNode;
}
function inorder(node: TreeNode | undefined): number[] {
if (!node) return [];
return [...inorder(node.left), node.value, ...inorder(node.right)];
}
Depth-first search on a graph is equally natural — just track visited nodes to avoid infinite cycles.
Recursion vs iteration comparison
| Dimension |
Recursion |
Iteration |
| Code clarity |
High for tree/graph/divide-and-conquer |
High for linear sequences |
| Stack safety |
Risky for deep input |
Always safe |
| Performance |
Extra call-frame overhead |
Typically faster |
| Tail-call opt. |
Language-dependent |
N/A — loops are already O(1) stack |
| Mutable state |
Avoided naturally |
Requires care |
| Debugging |
Harder (deep call stacks) |
Easier |
How to pick
- Is the data structure recursive (tree, trie, nested object)? → Recursion is natural; bound the depth.
- Are subproblems overlapping? → Add memoisation or switch to dynamic programming.
- Is input size unbounded? → Use iteration; or use recursion with an explicit depth limit.
- Is the language Python, JS, or Java? → No TCO guarantee; prefer iteration for deep calls.
- Is the depth bounded by O(log n)? (e.g., binary search tree height) → Recursion is safe.
Common mistakes
Missing the base case. Even experienced developers occasionally forget the termination condition and hit a stack overflow. Always write the base case first.
Mutating shared state inside recursion. Recursive calls sharing a mutable list without copying lead to subtle bugs. Either pass a copy or use an accumulator pattern.
Ignoring stack depth on user input. A JSON parser that recurses on nesting depth crashes if a user sends a 10 000-deep object. Cap the depth explicitly.
Forgetting that memoisation caches by argument. If arguments are mutable objects, the cache key may not work as expected. Use immutable keys (tuples, not lists).
What to skip
- Recursive file-system walks on user-supplied paths — symlink loops cause infinite recursion. Use
os.walk or Path.rglob which handle cycles.
- Recursive string parsing without a real parser — regex or a grammar-based parser handles edge cases recursion misses.
- Recursive solutions proposed by AI autocomplete on flat data — loops are clearer and safer. See Big-O notation explained in 2026 to reason about the complexity trade-off.
FAQ
Why does Python have a recursion limit?
CPython has no tail-call optimisation, so every call grows the C call stack. The 1 000-frame default prevents a runaway recursive function from segfaulting the interpreter. You can raise it with sys.setrecursionlimit, but the safer fix is iteration.
Is recursion slower than iteration?
Usually yes — function-call overhead is real. For tree traversal the difference is small and readability wins. For tight inner loops on flat data, use iteration.
What is a trampoline?
A technique where a recursive function returns a callable instead of calling itself directly. The trampoline loop drives execution iteratively. Useful in languages without TCO.
How do I debug a recursive function?
Add a depth counter and print or log it. Use your debugger's call-stack panel. If the stack is hundreds deep, you likely have a missing base case or missing cycle check.
Where to go next