Recursive vs. Iterative Algorithms: Pros and Cons

Use recursion when the problem is shaped like a tree or splits into smaller copies of itself, and the depth is small. Use a loop when the work is a straight repetition, when the depth could be large, or when you are in a language that does not optimize recursive calls. Every recursive algorithm can be rewritten as a loop with an explicit stack, so the choice is about clarity, limits and cost, not about what is possible.

The examples below are Python 3 and were all run; the outputs shown are the real ones.

The short comparison

	Recursive	Iterative
Best fit	Trees, graphs, backtracking, divide and conquer	Linear scans, counters, running totals, simple searches
Extra memory	One stack frame per active call, so O(depth)	Usually O(1), or the size of an explicit stack you manage
Depth limit	Yes. Python stops at 1000 frames by default	None from the call stack
Speed	Pays a function call per step	Usually a little faster per step
Readability	Short and close to the definition when the problem is recursive	Short for simple loops, noisy when you need a manual stack
Typical bug	Missing or wrong base case, which never stops	Off-by-one in the loop bounds, stale state between iterations

How each one works

A recursive function has a base case that returns directly, and a recursive case that calls the function on a smaller input. An iterative version has state (a counter, an accumulator) that a loop updates until a condition fails.

def factorial(n):
    if n <= 1:                 # base case
        return 1
    return n * factorial(n - 1)  # recursive case

def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

print(factorial(5), factorial_iter(5))   # 120 120

Both are O(n) time. The recursive one also uses O(n) stack space; the loop uses O(1). For factorial there is no reason to prefer recursion except as a teaching example. Factorial is a loop in disguise, which is the first thing to check: if each call makes exactly one recursive call and does nothing afterwards but combine the result, a loop is almost always the better tool.

Where recursion costs you

1. The stack has a limit

Each call takes a frame. Python’s default limit is 1000, so this fails on modest input:

import sys

def sum_to(n):
    return 0 if n == 0 else n + sum_to(n - 1)

print(sys.getrecursionlimit())   # 1000
sum_to(5000)
# RecursionError: maximum recursion depth exceeded

You can raise the limit with sys.setrecursionlimit, but the real stack is finite, so a very high value can crash the interpreter instead of raising a clean error. Java throws StackOverflowError and JavaScript throws RangeError in the same situation. The exact depth you can reach varies by language, runtime and frame size, so don’t rely on a specific number.

2. Tail recursion is not a fix in most languages

You will see advice to write the recursive call as the very last operation (tail recursion) so the compiler can reuse the frame. That works in languages that guarantee it, such as Scheme, and in Kotlin when you mark a function tailrec. CPython does not do tail-call elimination, and Java does not either, so rewriting factorial with an accumulator in Python gives you the same stack growth as before. If you need constant stack space in these languages, write the loop.

3. Repeated work

Naive recursion on overlapping subproblems recomputes the same values. Fibonacci is the standard example:

calls = 0
def fib_count(n):
    global calls
    calls += 1
    return n if n < 2 else fib_count(n - 1) + fib_count(n - 2)

fib_count(20)
print(calls)   # 21891

Computing fib(20) makes 21,891 calls, and the count grows exponentially (about 1.6 times per step). There are two standard fixes. Memoization keeps the recursive shape and caches results; a loop keeps only the last two values:

from functools import lru_cache

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

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

print(fib_memo(20), fib_iter(20))        # 6765 6765
print(fib_iter(100))                     # 354224848179261915075

Memoized recursion is O(n) time and O(n) space (the cache plus the stack); the loop is O(n) time and O(1) space. This is the same idea as top-down versus bottom-up dynamic programming, covered in our post on tabulation and memoization.

Where recursion wins

Trees and nested data are recursive by definition, and the code says so. In-order traversal of a binary tree is three lines:

class Node:
    def __init__(self, val, left=None, right=None):
        self.val, self.left, self.right = val, left, right

def inorder_rec(root, out):
    if root:
        inorder_rec(root.left, out)
        out.append(root.val)
        inorder_rec(root.right, out)
    return out

The iterative version has to do by hand what the call stack did for you: remember where to come back to.

def inorder_iter(root):
    out, stack, cur = [], [], root
    while cur or stack:
        while cur:                 # go as far left as possible
            stack.append(cur)
            cur = cur.left
        cur = stack.pop()          # visit the node
        out.append(cur.val)
        cur = cur.right            # then its right subtree
    return out

t = Node(4, Node(2, Node(1), Node(3)), Node(6, Node(5), Node(7)))
print(inorder_rec(t, []))   # [1, 2, 3, 4, 5, 6, 7]
print(inorder_iter(t))      # [1, 2, 3, 4, 5, 6, 7]

For a balanced tree the recursion depth is about log n, so the recursive version is fine and easier to read. The difference shows up on a degenerate tree, such as a linked chain of 5,000 right children:

root = Node(0); cur = root
for i in range(1, 5000):
    cur.right = Node(i); cur = cur.right

inorder_rec(root, [])          # RecursionError
print(len(inorder_iter(root))) # 5000

The recursive one raises RecursionError; the iterative one is fine because its stack is a list on the heap. The same applies to depth-first search on a graph: a long path can overflow the call stack, and an explicit stack cannot.

Backtracking (permutations, subsets, N-Queens, Sudoku) is the other place where recursion is clearly the right default. The “try a choice, recurse, undo the choice” structure is awkward to write with loops.

Binary search: both are fine

Binary search recurses once per call and throws away half the range, so depth is only log n. That makes either style safe, and most people write the loop because it has no extra parameters:

def binary_search_iter(a, target):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target:
            return mid
        if a[mid] > target:
            hi = mid - 1
        else:
            lo = mid + 1
    return -1

print(binary_search_iter([1, 3, 5, 7, 9, 11], 7))   # 3
print(binary_search_iter([1, 3, 5, 7, 9, 11], 4))   # -1

The difference in speed between the two versions is small. Don’t choose between them on performance; choose on which one you can get right under pressure.

Converting recursion to a loop

When you need to remove the depth limit, follow these steps:

1. Identify what a call needs: its arguments and, if work happens after the recursive call returns, what to do on the way back.
2. Create an explicit stack holding those arguments (and a marker for “post-work” if needed).
3. Loop while the stack is not empty: pop, handle the base case, otherwise do the work and push the sub-calls.
4. Push children in reverse order if you want the same visiting order as the recursion.

Pre-order traversal is the simplest case, because no work happens after the recursive calls:

def preorder_iter(root):
    out, stack = [], [root] if root else []
    while stack:
        node = stack.pop()
        out.append(node.val)
        if node.right: stack.append(node.right)   # right first, so left pops first
        if node.left:  stack.append(node.left)
    return out

print(preorder_iter(t))   # [4, 2, 1, 3, 6, 5, 7]

Post-order and in-order need the extra bookkeeping shown above, which is why those are common interview follow-ups.

Choosing in practice

• Use a loop for anything that is a plain counter, accumulator or scan over an array or string.
• Use recursion for trees, nested structures, backtracking and divide and conquer (merge sort, quicksort), where the depth is logarithmic or otherwise bounded.
• Check the worst-case depth before recursing on user input or on graphs and linked structures. A skewed tree or a long path is the usual failure.
• Check for overlapping subproblems. If the same call can happen twice, add memoization or switch to a table or loop.
• Prefer what your team can read. A clear recursive function beats a clever manual stack, and a plain loop beats a clever recursion.

In interviews

Interviewers often accept either, but they ask follow-ups. Be ready to state the time and space complexity including the stack, to say what happens on a deep input, and to describe how you would convert your solution. A good pattern is to write the recursive version first because it is faster to get correct, then mention the loop-with-stack alternative and when you would need it. To practice both styles, work through the Recursion lesson and Inorder Tree Traversal. For more exercises, see 10 coding exercises for mastering recursion.