Recursion Explained: When to Use It and When Not To

A function that calls itself has a maximum depth, and it is smaller than most people expect: 1,000 calls in CPython by default, roughly 10,000-15,000 in Node and browser engines depending on how much each frame holds. Go past it and the program does not slow down gracefully. It crashes. Python raises RecursionError: maximum recursion depth exceeded; JavaScript raises RangeError: Maximum call stack size exceeded.

Both errors have the same cause, and once you see it you will know when recursion is the right tool and when it is a liability.

What a recursive function actually does to the call stack

Every function call pushes a frame onto the call stack: the arguments, the local variables, and the address to return to. A normal call returns and its frame pops off. A recursive call can’t return yet, because it is waiting on the call it just made, so every frame stays on the stack until the one below it finishes.

1
2
3
4

def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n - 1)

factorial(4) builds four stack frames before any of them produce a value:

1
2
3
4

factorial(4) -> 4 * factorial(3)
                     factorial(3) -> 3 * factorial(2)
                                          factorial(2) -> 2 * factorial(1)
                                                               factorial(1) -> 1   # base case, stack stops growing

Only when factorial(1) returns 1 does the stack unwind: 2 * 1, then 3 * 2, then 4 * 6, giving 24.

Two parts make this work. The base case (n <= 1) stops the recursion. The recursive case calls the function again with input that moves toward the base case. Drop either one and the function never stops calling itself; in Python you hit RecursionError within a thousand calls, in a language without a limit the process dies with a stack overflow.

When recursion is the right tool: nested data

Recursion earns its place when the data is nested to a depth you don’t know in advance: a tree, a filesystem, arbitrarily nested JSON. A loop over that kind of data needs a stack you manage by hand. Recursion gets one for free, because the call stack is the stack you needed.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def flatten(nested):
    result = []
    for item in nested:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

flatten([1, [2, 3, [4, [5, 6]], 7], 8])
# [1, 2, 3, 4, 5, 6, 7, 8]

Each call to flatten handles one level. When it meets a nested list, it hands that list to a new call, and the call stack remembers where to resume in the outer list once the inner one is done. The iterative version would have to track that position itself.

Walking a directory tree has the same shape:

1
2
3
4
5
6

from pathlib import Path

def total_size(path: Path) -> int:
    if path.is_file():
        return path.stat().st_size
    return sum(total_size(child) for child in path.iterdir())

total_size does not care whether a directory is one level deep or ten. Each call handles its own path.

When recursion is the wrong tool: flat, long input

Summing a flat list is the opposite case. There is no nesting, so recursion buys nothing except stack risk.

1
2
3
4

def sum_recursive(nums):
    if not nums:
        return 0
    return nums[0] + sum_recursive(nums[1:])

It works on small input and falls over on real input:

1
2
3
4

>>> sum_recursive(list(range(2000)))
Traceback (most recent call last):
  ...
RecursionError: maximum recursion depth exceeded

Two thousand items, one frame per item, double the default limit. The loop version uses a single frame no matter how long the list is:

1
2
3
4
5

def sum_iterative(nums):
    total = 0
    for n in nums:
        total += n
    return total

sum_iterative(list(range(1_000_000))) returns instantly. In Big O notation both versions are O(n) in time, but the recursive one also costs O(n) stack space, and that space is capped at a thousand frames.

Does tail-call optimization fix deep recursion in Python or JavaScript?

No. In sum_recursive, the last thing that happens is the addition, not the recursive call, so each frame has to stay alive to receive a result and add to it. You can rewrite it so the recursive call is the very last operation, carrying the running total as an argument:

1
2
3
4

def sum_tail(nums, acc=0):
    if not nums:
        return acc
    return sum_tail(nums[1:], acc + nums[0])

In a language with tail-call optimization, the compiler sees that nothing in the caller’s frame is needed after the call and reuses that frame instead of pushing a new one. The recursion becomes a loop under the hood.

CPython doesn’t do this, by design: the core developers have rejected it because it would make tracebacks harder to read. sum_tail still hits the limit on a 2,000-item list. JavaScript’s ES2015 spec includes proper tail calls, but V8 (Chrome, Node.js) and SpiderMonkey (Firefox) never shipped them; only Safari’s JavaScriptCore does.

So the rule is the same in both languages. If the size of the input decides how deep the recursion goes, don’t count on the engine to save you. Convert it to a loop, or cap the depth.

How memoization fixes slow recursion

Some recursive functions never get close to the depth limit. Their problem is that they compute the same thing over and over. Naive recursive Fibonacci is the textbook case:

1
2
3
4

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

fib(5) calls fib(4) and fib(3), and fib(4) calls fib(3) again. That duplication compounds at every level, so the number of calls grows exponentially with n (by a factor of about 1.6 per step, usually written as the O(2^n) upper bound). In CPython, fib(30) already takes around a tenth of a second and fib(40) takes over ten seconds.

The fix leaves the recursion alone and caches results, so each distinct input is computed once:

1
2
3
4
5
6
7

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    if n < 2:
        return n
    return fib_memo(n - 1) + fib_memo(n - 2)

lru_cache is a decorator, the same mechanism covered in Python decorators explained. It wraps fib_memo, and when an argument repeats it returns the stored result instead of running the body again. fib_memo(40) returns immediately.

The depth doesn’t change: fib_memo(40) still needs about 40 stack frames. What changes is the call count, which drops from exponential to linear. You pay O(n) memory for the cache and get O(n) time instead of exponential.

Recursion vs iteration: which one to use

One case deserves more than a table row. If the recursion depth is controlled by input you don’t trust, it is a denial-of-service vector. A recursive parser that goes one level deeper per nested bracket in user-supplied text can be crashed by anyone who sends a few thousand [ characters. Cap the depth explicitly, or don’t recurse.

How to convert a recursive function to a loop

The direct replacement for recursion over a tree is an explicit stack: a list you push and pop yourself, driven by a while loop. Here is flatten rewritten that way:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def flatten_iterative(nested):
    result = []
    stack = [iter(nested)]
    while stack:
        for item in stack[-1]:
            if isinstance(item, list):
                stack.append(iter(item))
                break
            result.append(item)
        else:
            stack.pop()
    return result

It produces the same output with one stack frame, however deep the input goes. The cost is the bookkeeping you can see: the stack of iterators is exactly what the call stack was tracking for you.

Next time you write a recursive function, ask how deep it could get. If the answer is small and known (a config file, a UI component tree, a parse tree for your own grammar), keep the recursion. If the answer is “whatever the input says”, write the loop.

Related articles

• Big O Notation Explained With Code Examples
• Python Decorators Explained With Examples
• How to Use Git Bisect to Find a Broken Commit