Recursion vs Iteration: Which Should You Use?

Recursion and iteration are two ways to repeat work: recursion repeats by having a function call itself, while iteration repeats with a loop (for/while). Anything you can write one way you can write the other — they are equally powerful. The real question is which is clearer and which is cheaper for a given problem. This page gives you a framework for choosing and the technique to convert between them.

The same algorithm, both ways

Factorial side by side. The recursive version reads like the math definition; the iterative one is a plain loop with no extra stack frames.

long long factRec(int n) {            // recursive: O(n) time, O(n) stack
    if (n <= 1) return 1;
    return n * factRec(n - 1);
}
long long factIter(int n) {           // iterative: O(n) time, O(1) space
    long long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

long factRec(int n) {                 // recursive: O(n) time, O(n) stack
    if (n <= 1) return 1;
    return n * factRec(n - 1);
}
long factIter(int n) {                // iterative: O(n) time, O(1) space
    long result = 1;
    for (int i = 2; i <= n; i++) result *= i;
    return result;
}

function factRec(n) {                  // recursive: O(n) time, O(n) stack
  if (n <= 1) return 1;
  return n * factRec(n - 1);
}
function factIter(n) {                 // iterative: O(n) time, O(1) space
  let result = 1;
  for (let i = 2; i <= n; i++) result *= i;
  return result;
}

def fact_rec(n):                       # recursive: O(n) time, O(n) stack
    if n <= 1:
        return 1
    return n * fact_rec(n - 1)

def fact_iter(n):                      # iterative: O(n) time, O(1) space
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

Both are O(n) time. The crucial difference is space: recursion holds n paused stack frames (O(n)), while the loop uses a single accumulator (O(1)).

How they compare

Aspect	Recursion	Iteration
Readability	Great for self-similar problems (trees, divide & conquer)	Great for linear sweeps
Stack space	O(depth) — risks stack overflow	O(1) extra
Speed	Slight call overhead per frame	Usually a bit faster
Natural fit	Trees, graphs, backtracking, recurrences	Arrays, counters, accumulation

Converting recursion to a loop

Any recursion can become iteration. Linear (tail-like) recursion turns into a simple loop, as factIter shows. Branching recursion (like a tree walk) converts by using an explicit stack to mimic what the call stack did for you. Here is iterative depth-style traversal of a binary tree using your own stack:

void traverse(TreeNode* root) {
    std::stack<TreeNode*> st;
    if (root) st.push(root);
    while (!st.empty()) {
        TreeNode* node = st.top(); st.pop();
        visit(node);
        if (node->right) st.push(node->right); // push right first
        if (node->left)  st.push(node->left);  // so left is processed first
    }
}

void traverse(TreeNode root) {
    Deque<TreeNode> st = new ArrayDeque<>();
    if (root != null) st.push(root);
    while (!st.isEmpty()) {
        TreeNode node = st.pop();
        visit(node);
        if (node.right != null) st.push(node.right); // push right first
        if (node.left  != null) st.push(node.left);  // so left is processed first
    }
}

function traverse(root) {
  const st = [];
  if (root) st.push(root);
  while (st.length) {
    const node = st.pop();
    visit(node);
    if (node.right) st.push(node.right); // push right first
    if (node.left)  st.push(node.left);  // so left is processed first
  }
}

def traverse(root):
    st = [root] if root else []
    while st:
        node = st.pop()
        visit(node)
        if node.right:
            st.append(node.right)   # push right first
        if node.left:
            st.append(node.left)    # so left is processed first

This is exactly what you do when recursion would be too deep and risk a stack overflow.

Going deeper: A tail-recursive call is one where the recursive call is the last action, so nothing is left to do after it returns. Such calls could reuse one frame, but C++, Java, JavaScript, and Python do not reliably optimize them — treat deep tail recursion as if it still costs O(depth) stack and rewrite it as a loop when depth is large.

When to choose which

Choose recursion when the data is recursive — trees, graphs, backtracking, divide and conquer. The code mirrors the structure and is far easier to get right.
Choose iteration for simple linear repetition, when recursion depth could blow the stack, or when you need the last bit of performance in a hot loop.

For beginners: Write it recursively first to get a correct solution that matches the problem’s shape. Convert to iteration later only if depth or speed forces you to. Clarity first, optimization second.

Next: a powerful recursive pattern — backtracking. Or practice on the recursion exercises.