Replacing recursion with a loop

JavaScriptJunior~3 min read

Almost any recursion can be rewritten as a loop if you carefully replace the self-call with repeating actions that change some state. A recursive call carries its state in the function arguments, while a loop carries the same state in ordinary variables, so the translation between them is mechanical.

Theory

TL;DR

Recursion always consists of two parts: a base case and a recursive step.
To get a loop, create variables for the state (the former arguments).
Repeat the steps with while or for.
Break out of the loop where the recursion would have hit its base case.
Loops are usually more efficient: less memory, faster, no risk of a blown stack.
Recursion can be logically clearer, especially for nested structures such as trees.

Quick example

javascript

// Recursive version
function factorial(n) {
  if (n === 1) return 1;
  return n * factorial(n - 1);
}

// Iterative version
function factorialIterative(n) {
  let result = 1;
  while (n > 1) {
    result *= n;
    n--;
  }
  return result;
}

console.log(factorial(5));          // 120
console.log(factorialIterative(5)); // 120

We simply "unrolled" the recursion: instead of many function calls we change n inside the loop.

The general principle

Recursion normally consists of:

a base case, where we return a result without a new call;
a recursive step, where the function calls itself with new arguments.

To turn that into a loop:

create variables for the state (that is, for the arguments);
repeat the steps with while or for;
break out once the base case is reached.

Put differently, recursion keeps its state on the call stack, while a loop keeps the same state in local variables. All the work of rewriting comes down to finding that state and making it explicit.

Example: array sum

Recursion:

javascript

function sum(arr, i = 0) {
  if (i === arr.length) return 0;
  return arr[i] + sum(arr, i + 1);
}

Loop:

javascript

function sumIterative(arr) {
  let result = 0;
  for (let i = 0; i < arr.length; i++) {
    result += arr[i];
  }
  return result;
}

The pattern is easy to see here: the index i used to be a recursion argument and became the loop counter. The accumulator result replaced the chain of additions that previously "waited" on the stack until the deepest call returned.

Example: Fibonacci numbers

Recursive:

javascript

function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

Iterative:

javascript

function fibIterative(n) {
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

Here the loop is far more efficient: the naive recursion performs exponentially many calls because it recomputes the same values over and over, while the loop runs only n iterations and keeps two numbers in memory.

The general conversion template

Recursion element	In a loop
Function arguments	Local variables
Recursive call	Loop iteration
Base case	Exit condition (`if`, `while`)
Returning a value	Return after the loop

The order of steps is always the same: identify the base case and turn it into an exit condition, move the state into variables, and change them on every iteration.

When to pick a loop and when recursion

Any recursion can be written as a loop if you identify the base case, move the state into variables and change them on each iteration.
Loops are usually more efficient: less memory, faster, no RangeError: Maximum call stack size exceeded.
Recursion can be clearer logically, especially for nested structures (trees or the DOM, for example).
When the recursion branches (as a tree traversal does), a simple counter is no longer enough: the state moves into an explicit stack array.

javascript

// Tree traversal without recursion: our own stack instead of the call stack
function collectValues(root) {
  const out = [];
  const stack = [root];
  while (stack.length > 0) {
    const node = stack.pop();
    if (!node) continue;
    out.push(node.value);
    for (const child of node.children ?? []) stack.push(child);
  }
  return out;
}

Common mistakes

Forgetting the exit condition. Recursion without a base case throws RangeError, while a loop without an exit condition simply freezes the tab forever, which is harder to notice.
Not changing the state inside the loop body. If you forget n-- or i++, the condition never becomes false.
Mixing up the order of computation. The recursion n * factorial(n - 1) multiplies on the way back up the stack, so when rewriting it as a loop you must watch which side the result accumulates from.
Assuming recursion is always slower. It is not inherently slow: what makes the naive fib slow is recomputing the same values, not recursion itself. With memoization the recursive version is linear too.
Rewriting as a loop something that reads better recursively. For trees and graphs a loop with an explicit stack is often longer and more confusing than three lines of recursion.

Short Answer

Interview ready

Premium

A concise answer to help you respond confidently on this topic during an interview.