Recursion vs Iteration

Recursion and iteration are the two fundamental ways to make a program repeat work. Iteration repeats a block of code with a loop (for, while) and state variables you update by hand. Recursion instead has a function call itself with a smaller version of the same problem, relying on the call stack to hold state, until it reaches a base case simple enough to answer directly. Both techniques can solve many of the same problems, but they differ sharply in how they use memory, how naturally they express certain problems, and how easily they can go wrong — which makes choosing between them, and converting between them, one of the most practical skills in DSA and in coding interviews.

Overview: How Recursion and Iteration Work

Imagine counting down from 5 to 1 and printing each number. With iteration, you write a loop and mutate a counter variable yourself: i = 5, then i -= 1 each pass, until a condition stops the loop. The computer only ever needs to remember the current value of i; nothing about the previous iterations is kept around.

With recursion, you instead write a function that calls itself with a smaller argument: countdown(5) prints 5 and calls countdown(4), which prints 4 and calls countdown(3), and so on, until countdown(0) does nothing and simply returns. Every well-formed recursive function has two parts: a base case (the smallest input, answered directly, with no further recursive call) and a recursive case (the function calls itself on a smaller version of the problem, then combines that result with the current step). If you omit the base case, or the recursive case never actually shrinks toward it, the function calls itself forever — in Python this doesn’t loop forever in practice, because Python enforces a default recursion limit (about 1000 frames, viewable with sys.getrecursionlimit()); once exceeded, Python raises RecursionError: maximum recursion depth exceeded.

The reason recursion behaves differently from iteration under the hood is the call stack. Every function call — recursive or not — gets its own stack frame holding its local variables and the point it should resume at once the call it made returns. A loop reuses the same stack frame for every pass, which is why iteration typically uses constant extra memory. A recursive function, by contrast, keeps adding a new frame for every call that hasn’t returned yet, so a recursive function with recursion depth n uses O(n) extra memory for the stack alone, even if the work being done at each step is trivial. This is the central tradeoff: recursion often reads closer to the mathematical definition of a problem (especially for trees, graphs, divide-and-conquer, and backtracking, where an explicit iterative version would need to manage its own stack anyway), while iteration is usually more memory-efficient and avoids any risk of hitting the recursion limit.

Time and Space Complexity

Complexity isn’t a property of \”recursion\” or \”iteration\” in the abstract — it depends on the specific algorithm. But two patterns show up constantly enough to be worth memorizing:

Approach	Time	Space	Why
Factorial — recursive	O(n)	O(n)	One call per value from n down to 1; each call adds a stack frame that isn’t popped until the base case returns, so the call stack grows to depth n.
Factorial — iterative	O(n)	O(1)	A single loop runs roughly n times using a fixed number of variables; no extra memory grows with input size.
Naive Fibonacci — recursive	O(2^n)	O(n)	Each call branches into two more calls, forming a call tree with roughly 2^n nodes because the same subproblems (like fib(5)) are recomputed many times over. Space is only O(n) because at any instant only one root-to-leaf path of that tree is actually sitting on the call stack.
Fibonacci — iterative	O(n)	O(1)	A single loop computes each value exactly once, carrying only the previous two numbers forward.

The Fibonacci row is the classic warning about recursion: a direct, \”obvious\” recursive translation of a recurrence relation can be exponentially slower than an iterative (or memoized) version, because naive recursion has no memory of work it already did.

Examples

Example 1: Factorial, recursive vs iterative

Both versions compute the same result; the recursive version expresses \”n! = n × (n-1)!\” almost literally, while the iterative version accumulates a running product in a loop.

def factorial_recursive(n: int) -> int:
    if n <= 1:
        return 1
    return n * factorial_recursive(n - 1)


def factorial_iterative(n: int) -> int:
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result


print(factorial_recursive(5))
print(factorial_iterative(5))

Output:

120
120

factorial_recursive(5) calls itself with 4, then 3, then 2, then 1 (the base case, returning 1 immediately), and each return then multiplies by the value at that level: 1, then 2*1=2, then 3*2=6, then 4*6=24, then 5*24=120. factorial_iterative(5) reaches the same answer by multiplying result by 2, 3, 4, then 5 inside one loop, with no extra stack frames created.

Example 2: Fibonacci, recursive vs iterative — counting the work

This example makes the complexity difference concrete by literally counting how many times each function is called.

def fib_recursive(n: int, calls: list[int]) -> int:
    calls[0] += 1
    if n <= 1:
        return n
    return fib_recursive(n - 1, calls) + fib_recursive(n - 2, calls)


def fib_iterative(n: int) -> int:
    if n <= 1:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr


calls = [0]
result_recursive = fib_recursive(10, calls)
result_iterative = fib_iterative(10)
print(f\"Recursive fib(10) = {result_recursive}, calls made = {calls[0]}\")
print(f\"Iterative fib(10) = {result_iterative}\")

Output:

Recursive fib(10) = 55, calls made = 177
Iterative fib(10) = 55

Both functions agree on the answer, 55, but fib_recursive needed 177 separate function calls to get there, because it recomputes smaller Fibonacci values over and over (for example, fib(7) gets computed independently inside the branch for fib(9) and again inside the branch for fib(8)). fib_iterative computes the answer with a single pass and no repeated work, which is why its time complexity is O(n) instead of O(2^n).

Example 3: Reversing a string, recursive vs iterative

The iterative version uses the classic two-pointer swap; the recursive version peels off the first character and appends it after the reverse of the rest.

def reverse_string_recursive(text: str) -> str:
    if len(text) <= 1:
        return text
    return reverse_string_recursive(text[1:]) + text[0]


def reverse_string_iterative(text: str) -> str:
    chars = list(text)
    left, right = 0, len(chars) - 1
    while left < right:
        chars[left], chars[right] = chars[right], chars[left]
        left += 1
        right -= 1
    return \"\".join(chars)


word = \"recursion\"
print(reverse_string_recursive(word))
print(reverse_string_iterative(word))

Output:

noisrucer
noisrucer

reverse_string_recursive(\"recursion\") keeps slicing off the first character and recursing on the rest until it hits a 1-character (or empty) string, then rebuilds the reversed string as the calls return. Note this version is O(n) calls but each slice text[1:] and each concatenation creates a new string, so it’s actually O(n^2) time overall — the iterative two-pointer version swaps in place inside a list and joins once, which is O(n) time and much closer to how you’d solve this in production code or an interview.

How It Works Step by Step

Trace factorial_recursive(4) to see the call stack grow and then unwind:

factorial_recursive(4)
  -> factorial_recursive(3)
       -> factorial_recursive(2)
            -> factorial_recursive(1) returns 1
            returns 2 * 1 = 2
       returns 3 * 2 = 6
  returns 4 * 6 = 24

Each arrow represents a new stack frame being pushed; none of those calls can finish until the one below it returns, because each one is waiting to multiply n by whatever its recursive call eventually produces. factorial_recursive(1) is the base case — it returns immediately without making another call, which is what stops the stack from growing further. Then the calls unwind in reverse (last in, first out): 1 is returned to the n=2 frame, which computes 2 * 1 = 2 and returns that to the n=3 frame, which computes 3 * 2 = 6, and finally the n=4 frame computes 4 * 6 = 24. At the deepest point of this trace, there are 4 stack frames alive at once (for n=4,3,2,1) — that’s exactly the O(n) space cost from the complexity table above.

Common Mistakes

Mistake 1: forgetting the base case

Without a base case, a recursive function never stops calling itself, and Python’s recursion limit turns that into a crash rather than an infinite loop:

def factorial_broken(n: int) -> int:
    return n * factorial_broken(n - 1)


print(factorial_broken(5))

This looks reasonable at a glance, but there is no condition that ever stops the recursion — n keeps decreasing past 1, into 0, -1, -2, and so on forever. Running it raises RecursionError: maximum recursion depth exceeded once Python’s call stack limit (around 1000 frames) is hit. The fix is the factorial_recursive function from Example 1, which checks if n <= 1: return 1 before making any further call — always write and test the base case first, and confirm every recursive call passes an argument that’s strictly closer to it.

Mistake 2: mutable default arguments in a recursive accumulator

It’s tempting to thread an \”accumulator\” list through recursive calls using a default argument:

def collect_even_numbers(nums: list[int], index: int = 0, acc: list[int] = []) -> list[int]:
    if index == len(nums):
        return acc
    if nums[index] % 2 == 0:
        acc.append(nums[index])
    return collect_even_numbers(nums, index + 1, acc)

The bug: default argument values in Python are created once, when the function is defined, not each time the function is called. Since acc defaults to the same list object every time collect_even_numbers is called without an explicit third argument, values appended during one top-level call stay attached to that list and silently show up the next time the function is called with its default — a classic, hard-to-spot source of bugs. The fix is to default to None and create a fresh list inside the function body:

def collect_even_numbers(nums: list[int], index: int = 0, acc: list[int] | None = None) -> list[int]:
    if acc is None:
        acc = []
    if index == len(nums):
        return acc
    if nums[index] % 2 == 0:
        acc.append(nums[index])
    return collect_even_numbers(nums, index + 1, acc)


numbers = [1, 2, 3, 4, 5, 6]
print(collect_even_numbers(numbers))

Output:

[2, 4, 6]

Now each fresh top-level call gets its own new list, since acc is only built the first time index is 0 and no caller supplied their own list. This same mutable-default trap applies to dictionaries and sets, and shows up constantly in backtracking code that accumulates a \”current path\” or \”visited\” collection across recursive calls.

Best Practices

• Reach for recursion when the problem has a naturally recursive structure — trees, graphs, divide-and-conquer, backtracking — where an iterative version would need to manage its own explicit stack anyway.
• Prefer iteration for simple linear accumulation (sums, scans over a list) — it avoids function-call overhead and any risk of hitting the recursion limit.
• Always write the base case before the recursive case, and double-check that every recursive call’s argument moves strictly closer to it (a shrinking index, a smaller n, a smaller sub-list).
• Remember Python has no tail-call optimization: even a recursive call written as the very last operation still adds a real stack frame, so it offers no performance advantage over a loop.
• Watch out for Python’s recursion limit (sys.getrecursionlimit(), roughly 1000 by default) on deep or unbounded recursion, such as DFS on a large graph; convert to an iterative version with an explicit stack rather than raising the limit.
• Never use a mutable object ([], {}) as a default argument in a recursive helper — default to None and initialize inside the function.
• When a recursive solution revisits the same subproblem repeatedly (like naive Fibonacci), add memoization — either a manual dictionary cache or functools.lru_cache — before assuming recursion is \”too slow\” for the problem.

Practice Exercises

1. Write both a recursive and an iterative version of sum_list(nums: list[int]) -> int that returns the sum of all elements. Test both on [1, 2, 3, 4, 5]; both should print 15.
2. Write a recursive function is_palindrome(text: str) -> bool that checks whether a string reads the same forwards and backwards, using slicing so the base case is a string of length 0 or 1. Test it on \"level\" (expected True) and \"python\" (expected False).
3. Take the naive fib_recursive function from Example 2 and rewrite it using functools.lru_cache to memoize results. For n = 20, compare (in a comment or printed count) how many times the un-memoized version would be called versus the memoized version, and explain in one sentence why memoization changes the time complexity from O(2^n) to O(n).

Summary

• Iteration repeats code with an explicit loop and reuses one stack frame, typically giving O(1) extra space; recursion repeats code by having a function call itself, adding a new stack frame per call, typically giving O(n) extra space for a recursion depth of n.
• Every correct recursive function needs a base case that returns without recursing, and every recursive case must move strictly closer to that base case — otherwise Python raises RecursionError once its default recursion limit (~1000) is exceeded.
• A direct recursive translation of a recurrence relation, like naive Fibonacci, can be exponentially slow (O(2^n)) because it recomputes overlapping subproblems; an iterative or memoized version fixes this by computing each subproblem once (O(n)).
• Recursion tends to read most naturally for trees, graphs, divide-and-conquer, and backtracking; iteration is usually preferable for simple linear scans where no explicit stack is otherwise needed.
• Python has no tail-call optimization, so writing a recursive call as the \”last\” operation gives no performance benefit over a loop — it’s purely a readability choice.
• Never default a recursive accumulator parameter to a mutable object like []; default to None and create the collection inside the function body.