Recursion vs Iteration

Recursion solves a problem by having a function call itself on a smaller instance of the same problem until it hits a base case, then combines the returned results on the way back up; iteration solves the same problem by mutating state in a loop until a condition fails. Both express repetition — the difference is where the pending work is stored: recursion pushes it onto the language call stack (implicit), iteration keeps it in your own variables or an explicit stack/heap (explicit).

Recognize the pattern

• The problem definition is naturally self-referential: solve(n) = combine(n, solve(n-1)) — factorial, Fibonacci, tree/graph traversal, divide-and-conquer (merge sort, quicksort), backtracking.
• The data is a recursive structure itself: trees, nested lists, nested JSON, linked lists.
• You need to explore multiple branches per step (backtracking, DFS) — a loop alone can't hold multiple 'return points' without an explicit stack.
• Conversely: if the work is strictly linear (walk an array once, accumulate a sum), iteration is the tell — no branching subproblem, no need for a call frame per step.

Brute force vs optimal

Recursive factorial (direct translation of the mathematical definition):

static long factorial(int n) {
    if (n == 0 || n == 1) return 1;      // base case
    return n * factorial(n - 1);          // recursive case
}

Iterative equivalent (systematic conversion — base case becomes the loop's starting state, the recursive call becomes the loop body, the combine step becomes an accumulator update):

static long factorialIter(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++) {
        result *= i;
    }
    return result;
}

Both compute the same answer. The recursive version costs one stack frame per call; the iterative version costs one register/variable, reused every step.

General recursion → iteration recipe

1. Identify the base case(s) — these become the loop's initial state or exit condition.
2. Identify the state that changes each call (parameters, accumulator) — these become loop variables.
3. Replace the recursive call with a loop step that updates that state toward the base case.
4. If work happens after the recursive call returns, check whether the deferred combine can be re-associated into an accumulator. Factorial's n * factorial(n-1) is not tail-recursive, yet factorialIter above loops fine — multiplication is associative, so the pending multiplies can be folded in front-to-back instead of back-to-front. You need an explicit stack only when that restructuring is impossible: a non-associative combine, or multiple recursive calls per step (tree traversals, backtracking), where a plain loop has no memory of the pending return points.

Complexity, derived

Recursive factorial: factorial(n) makes exactly one call to factorial(n-1), so the call chain has length n before hitting the base case → T(n) = T(n-1) + O(1), which unrolls to O(n) time. Each pending call keeps a stack frame alive until its child returns (because the multiplication happens after the recursive call), so at the deepest point there are n live frames → O(n) auxiliary space on the call stack.

Iterative factorial: one loop of n-1 iterations, each O(1) → O(n) time, but only one result variable ever exists → O(1) space.

Same time complexity, but recursion pays O(n) extra space for the call stack that iteration avoids. This gap widens for problems like naive Fibonacci: T(n) = T(n-1) + T(n-2) + O(1) solves to Θ(φⁿ) time (φ ≈ 1.618, the same characteristic-equation root as Fibonacci itself; O(2ⁿ) is the quick loose bound from "each call branches into two"), because work is recomputed instead of reused, versus an iterative bottom-up version at O(n) time, O(1) space.

Traced example: factorial(4)

Unwind: 1 → 2*1=2 → 3*2=6 → 4*6=24. Four frames were alive simultaneously at the deepest point — that's the O(n) space cost made concrete. The iterative version reaches 24 with a single variable: 1→2→6→24, never holding more than one number.

Pitfalls

• StackOverflowError — deep non-tail recursion (e.g. recursing over a 100k-element list) exhausts the call stack; iteration has no such ceiling besides heap memory.
• Assuming tail-call optimization — Java, Python, and JavaScript do not guarantee TCO, so writing a 'tail-recursive' function does not save stack space there, unlike Scheme or some functional languages.
• Redundant recomputation — naive recursive Fibonacci recomputes the same subproblems exponentially; fix with memoization or convert to iterative bottom-up DP.
• Off-by-one base cases when converting — forgetting to seed the loop variable at the correct starting value (e.g. starting the factorial loop at 1 instead of 2 wastes a no-op iteration, or starting at 0 without guarding division/multiplication can corrupt the result).

When to use / when not

Trade-off in one line: recursion trades stack space and per-call overhead for code that matches the problem's natural decomposition; iteration trades that clarity for constant space and no recursion-depth limit. When a language/runtime lacks recursion support entirely (older GPU kernels, some embedded targets), iterative conversion via an explicit stack is mandatory, not optional. One structural note: recursion's implicit stack is LIFO, so it naturally expresses DFS; BFS needs FIFO order, so it is naturally iterative with an explicit queue — recursion cannot express it without contortions.

Takeaways

• Recursion = implicit stack (call frames); iteration = explicit state (loop variables) — same repetition, different bookkeeping location.
• Time complexity is often equal between the two; the real difference is usually space: O(depth) vs O(1).
• Converting to a loop needs an explicit stack only when the deferred combine cannot be re-associated into an accumulator — non-associative combines or multiple recursive calls (trees, backtracking). Associative folds like factorial loop fine despite not being tail-recursive.
• Prefer iteration for simple linear work and when stack depth is a real risk; prefer recursion when the problem's structure is itself recursive (trees, backtracking).

Recall: Factorial written as n * factorial(n-1) is not tail-recursive, yet it converts to a plain accumulator loop. What property of the combine step makes that possible — and what kind of recursion genuinely forces you to add an explicit stack instead?

Compiled from standard recursion/iteration pedagogy (CLRS-style recurrence analysis) and the source page's recursive-to-iterative conversion framework.