All Roadmaps›🧠 Data Structures & Algorithms›Phase 1›Iteration vs Recursion

Iteration vs Recursion

0/12 in this phase0/57 across the roadmap

📖 Concept

Every recursive solution can be converted to an iterative one and vice versa. Choosing between them involves tradeoffs in readability, performance, and stack safety.

Iteration: Uses loops (for, while). Runs in O(1) extra space (no stack frames). Best for simple repetitive tasks.

Recursion: Function calls itself. Uses O(n) stack space (one frame per call). Best for problems with recursive structure (trees, graphs, divide & conquer).

When to use each:

Criteria Iteration Recursion
Stack space O(1) O(n) stack frames
Readability Better for simple loops Better for tree/graph/divide problems
Performance Slight edge (no function call overhead) Function call overhead per frame
Stack overflow risk None Yes, for deep recursion
Natural fit Arrays, counting, accumulating Trees, graphs, backtracking, D&C

Converting recursion to iteration: The universal technique is using an explicit stack (or queue) to simulate the call stack:

  1. Replace function calls with pushing to a stack
  2. Replace returns with popping from the stack
  3. Replace parameters with data in the stack

Tail recursion: A special form where the recursive call is the LAST operation. Some engines can optimize this to use O(1) space (tail call optimization / TCO). JavaScript supports TCO in strict mode in Safari only.

🏠 Real-world analogy: Iteration is like walking up stairs one step at a time. Recursion is like giving instructions: "Go up one step, then follow these same instructions." Both reach the top, but recursion requires remembering where you are at each step (stack frames).

💻 Code Example

codeTap to expand ⛶
1// FACTORIAL — Both ways
2// Recursive: O(n) time, O(n) space
3function factorialRecursive(n) {
4  if (n <= 1) return 1;
5  return n * factorialRecursive(n - 1);
6}
7

8// Iterative: O(n) time, O(1) space ✅
9function factorialIterative(n) {
10  let result = 1;
11  for (let i = 2; i <= n; i++) {
12    result *= i;
13  }
14  return result;
15}
16

17// FIBONACCI — Both ways
18// Recursive: O(2ⁿ) time, O(n) space 💀
19function fibRecursive(n) {
20  if (n <= 1) return n;
21  return fibRecursive(n - 1) + fibRecursive(n - 2);
22}
23

24// Iterative: O(n) time, O(1) space ✅
25function fibIterative(n) {
26  if (n <= 1) return n;
27  let prev = 0, curr = 1;
28  for (let i = 2; i <= n; i++) {
29    [prev, curr] = [curr, prev + curr];
30  }
31  return curr;
32}
33

34// TREE TRAVERSAL — Recursion is natural, but can be iterative
35// Recursive DFS
36function inorderRecursive(node, result = []) {
37  if (!node) return result;
38  inorderRecursive(node.left, result);
39  result.push(node.val);
40  inorderRecursive(node.right, result);
41  return result;
42}
43

44// Iterative DFS with explicit stack
45function inorderIterative(root) {
46  const result = [];
47  const stack = [];
48  let current = root;
49  while (current || stack.length) {
50    while (current) {
51      stack.push(current);
52      current = current.left;
53    }
54    current = stack.pop();
55    result.push(current.val);
56    current = current.right;
57  }
58  return result;
59}
60

61// TAIL RECURSION — O(1) space if engine supports TCO
62function factorialTail(n: number, acc: number = 1): number {
63  if (n <= 1) return acc;
64  return factorialTail(n - 1, n * acc); // Tail position!
65}
66// The recursive call is the LAST thing — no work after it
67// Compiler can reuse the same stack frame (TCO)
68

69// CONVERTING RECURSION TO ITERATION — General pattern
70// Recursive:
71function sumRecursive(arr, i = 0) {
72  if (i >= arr.length) return 0;
73  return arr[i] + sumRecursive(arr, i + 1);
74}
75

76// Converted to iterative:
77function sumIterative(arr) {
78  let total = 0;
79  for (let i = 0; i < arr.length; i++) {
80    total += arr[i];
81  }
82  return total;
83}

🏋️ Practice Exercise

Practice Problems:

  1. Convert recursive fibonacci to iterative — compare speed for fib(40)
  2. Convert recursive binary search to iterative
  3. Write both recursive and iterative versions of array reversal
  4. Convert recursive tree traversal (preorder) to iterative using a stack
  5. Write a recursive function to print numbers 1 to n, then convert to iterative
  6. Implement GCD using both recursion and iteration
  7. Convert a recursive string reversal to iterative
  8. Write tail-recursive versions of: sum, factorial, fibonacci
  9. When would you PREFER recursion over iteration despite the stack overhead?
  10. Measure the maximum n for recursive factorial before stack overflow in your runtime

⚠️ Common Mistakes

  • Always using recursion because it 'looks elegant' — for simple problems, iteration is clearer and more efficient

  • Not realizing iterative tree traversal needs an explicit stack — you replace the implicit call stack with your own

  • Thinking tail call optimization works everywhere — only Safari supports TCO in JavaScript; Node.js does NOT

  • Converting recursion to iteration incorrectly — the explicit stack must mirror the call stack's behavior exactly

  • Assuming recursion is always slower — for tree/graph problems, recursive code often runs at the same speed

💼 Interview Questions

🎤 Mock Interview

Practice a live interview for Iteration vs Recursion

← PreviousCall Stack & Memory Model (Stack vs Heap)Next →Math for DSA (Logarithms, Powers, Modular Arithmetic)