CodingwithDom
Subscribe

Recursion vs iteration: which should I use?

CS Fundamentals 2 min read
Short answer

Use iteration for linear sequences. Use recursion when the data itself is nested — trees, folders, JSON, graphs — because the alternative is hand-rolling your own stack.

python
# Iterative — fast, constant memory
def factorial(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

# Recursive — clearer for some problems, costs a stack frame per call
def factorial(n):
    return 1 if n <= 1 else n * factorial(n - 1)

For factorial, the loop wins on every measure. It is the classic teaching example precisely because it is small enough to write both ways.

#Where recursion genuinely wins

python
def total_size(folder):
    total = 0
    for entry in folder.entries:
        total += entry.size if entry.is_file else total_size(entry)
    return total

Writing that iteratively means maintaining an explicit stack of folders to visit — which is exactly what recursion does for you, more clearly.

The rule: recursive data structure, recursive function.

#The cost

Each call adds a stack frame. Python's default limit is around 1000; exceed it and you get RecursionError. Deep recursion on user-supplied data is a denial-of-service vector.

#Tail calls

python
def factorial(n, acc=1):
    return acc if n <= 1 else factorial(n - 1, acc * n)

Some languages — Racket, Scheme, Elixir — optimise this into a loop, so it uses constant stack. Python, JavaScript and C# do not. Do not rely on it there.

#Memoisation

Naive recursive Fibonacci is O(2ⁿ) because it recomputes the same values repeatedly:

python
from functools import cache

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

One decorator takes it from exponential to linear.

Related answers