Recursion vs Iteration When Each Wins in DSA Javascript - Trade-offs & Analysis

Mental Model

Recursion solves problems by breaking them into smaller copies of themselves, while iteration solves problems by repeating steps in a loop.

Analogy: Recursion is like a set of nested Russian dolls, each doll opening to reveal a smaller one inside, while iteration is like walking down stairs step by step until you reach the bottom.

Recursion:
main() -> call1 -> call2 -> call3 -> base case
Iteration:
start -> step -> step -> step -> end

Dry Run Walkthrough

Input: Calculate factorial of 4 using recursion and iteration

Goal: Show how recursion and iteration solve the same problem differently and when each is better

Step 1: Recursion calls factorial(4), which calls factorial(3)

factorial(4) -> factorial(3) ↑

Why: Recursion breaks problem into smaller parts

Step 2: Recursion calls factorial(2) from factorial(3)

factorial(4) -> factorial(3) -> factorial(2) ↑

Why: Keep breaking down until base case

Step 3: Recursion calls factorial(1) from factorial(2), hits base case

factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Base case stops recursion

Step 4: Recursion returns 1 from factorial(1), then factorial(2) returns 2

returning: factorial(1)=1 -> factorial(2)=2

Why: Combine results going back up

Step 5: Recursion returns factorial(3)=6 and factorial(4)=24

returning: factorial(3)=6 -> factorial(4)=24

Why: Final result computed

Step 6: Iteration starts with result=1 and i=1

result=1, i=1 ↑

Why: Initialize loop variables

Step 7: Iteration multiplies result by i=1, increments i to 2

result=1, i=2 ↑

Why: Multiply step by step

Step 8: Iteration multiplies result by i=2, increments i to 3

result=2, i=3 ↑

Why: Continue multiplication

Step 9: Iteration multiplies result by i=3, increments i to 4

result=6, i=4 ↑

Why: Continue multiplication

Step 10: Iteration multiplies result by i=4, loop ends

result=24, i=5 (end)

Why: Final factorial computed

Result:

Final factorial = 24
Recursion stack: factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) -> base case
Iteration result: 24

Annotated Code

DSA Javascript

class Factorial {
  // Recursive factorial
  static factorialRecursive(n) {
    if (n <= 1) return 1; // base case stops recursion
    return n * Factorial.factorialRecursive(n - 1); // recursive call
  }

  // Iterative factorial
  static factorialIterative(n) {
    let result = 1;
    for (let i = 1; i <= n; i++) {
      result *= i; // multiply step by step
    }
    return result;
  }
}

// Driver code
const n = 4;
console.log("Recursive factorial of", n, "=", Factorial.factorialRecursive(n));
console.log("Iterative factorial of", n, "=", Factorial.factorialIterative(n));

if (n <= 1) return 1; // base case stops recursion

stop recursion when problem is smallest

return n * Factorial.factorialRecursive(n - 1); // recursive call

break problem into smaller subproblem and combine

for (let i = 1; i <= n; i++) {

repeat multiplication from 1 to n

result *= i; // multiply step by step

accumulate product iteratively

Output

Recursive factorial of 4 = 24

Iterative factorial of 4 = 24

Complexity Analysis

Time: O(n) because both recursion and iteration multiply n numbers once

Space: Recursion: O(n) due to call stack; Iteration: O(1) uses constant space

vs Alternative: Iteration uses less memory and avoids call stack overhead, recursion is simpler to write for problems naturally defined by smaller subproblems

Edge Cases

n = 0 or 1

Both return 1 immediately as base case

DSA Javascript

if (n <= 1) return 1; // base case stops recursion

n is negative

No handling, recursion will run infinitely or iteration returns 1 (incorrect)

DSA Javascript

No explicit guard; input should be validated before calling

When to Use This Pattern

When a problem can be broken into smaller similar problems, recursion is natural; when you need simple repeated steps without overhead, iteration wins.

Common Mistakes

Mistake: Forgetting base case in recursion causing infinite calls
Fix: Always include a base case that stops recursion

Mistake: Using recursion for very large inputs causing stack overflow
Fix: Use iteration or tail recursion optimization if available

Summary

Recursion solves problems by calling itself with smaller inputs; iteration solves by looping.

Use recursion when problem naturally divides into smaller subproblems; use iteration for simple repeated steps or large inputs.

The key insight is recursion uses call stack to remember state, iteration uses loops to repeat steps.

Practice

1. Which scenario is best suited for using recursion instead of iteration?

easy

A. When the problem requires simple repeated loops

B. When the problem can be divided into smaller similar subproblems

C. When you want to avoid function call overhead

D. When memory usage must be minimal

Solution

1. Step 1: Understand recursion use case

   Recursion works well when a problem can be broken down into smaller versions of itself, like tree traversals or factorial calculation.

2. Step 2: Compare with iteration scenarios

   Iteration is better for simple repeated tasks without nested subproblems, so recursion is preferred for divide-and-conquer problems.

3. Final Answer:

   When the problem can be divided into smaller similar subproblems -> Option B

4. Quick Check:

   Recursion fits divide-and-conquer = C [OK]

Hint: Recursion fits problems breaking into smaller similar parts [OK]

Common Mistakes:

• Thinking iteration is always faster
• Ignoring function call overhead in recursion
• Confusing simple loops with recursive problems

2. Which of the following is the correct syntax for a recursive function in JavaScript?

easy

A. function recurse(n) { while(n > 0) { n--; } return n; }

B. function recurse(n) { for(let i=0; i

C. function recurse(n) { if (n <= 0) return 0; return n + recurse(n - 1); }

D. function recurse(n) { if(n > 0) { return n * recurse(n + 1); } else { return 1; } }

Solution

1. Step 1: Identify recursive call and base case

   function recurse(n) { if (n <= 0) return 0; return n + recurse(n - 1); } has a base case (n <= 0) and calls itself with a smaller argument (n - 1), which is correct recursion.

2. Step 2: Check other options for recursion errors

   function recurse(n) { while(n > 0) { n--; } return n; } uses a loop, not recursion. function recurse(n) { for(let i=0; i 0) { return n * recurse(n + 1); } else { return 1; } } calls recurse with n + 1, causing infinite recursion.

3. Final Answer:

   function recurse(n) { if (n <= 0) return 0; return n + recurse(n - 1); } -> Option C

4. Quick Check:

   Base case + smaller recursive call = B [OK]

Hint: Look for base case and smaller recursive call [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursive calls
• Increasing argument in recursive call causing stack overflow

3. What is the output of the following JavaScript code?

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}
console.log(factorial(4));

medium

A. 24

B. 10

C. 16

D. Error

Solution

1. Step 1: Trace recursive calls for factorial(4)

   factorial(4) calls factorial(3), factorial(3) calls factorial(2), factorial(2) calls factorial(1), factorial(1) calls factorial(0) which returns 1.

2. Step 2: Calculate return values step-by-step

   factorial(1) = 1 * 1 = 1, factorial(2) = 2 * 1 = 2, factorial(3) = 3 * 2 = 6, factorial(4) = 4 * 6 = 24.

3. Final Answer:

   24 -> Option A

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial n! = n * (n-1)! [OK]

Common Mistakes:

• Confusing factorial with sum
• Forgetting base case returns 1
• Miscomputing multiplication order

4. Identify the error in this recursive function and choose the fix:

function sumTo(n) {
  if (n === 1) return 1;
  return n + sumTo(n);
}

medium

A. Change return to console.log

B. Add a base case for n === 0

C. Replace recursion with a for loop

D. Change sumTo(n) to sumTo(n - 1) in the return statement

Solution

1. Step 1: Analyze recursive call argument

   The function calls sumTo(n) again without changing n, causing infinite recursion and stack overflow.

2. Step 2: Fix recursive call to reduce problem size

   Changing sumTo(n) to sumTo(n - 1) reduces n each call, eventually reaching base case n === 1.

3. Final Answer:

   Change sumTo(n) to sumTo(n - 1) in the return statement -> Option D

4. Quick Check:

   Recursive call must reduce argument = A [OK]

Hint: Recursive calls must progress toward base case [OK]

Common Mistakes:

• Calling function with same argument causing infinite loop
• Missing or wrong base case
• Confusing recursion with iteration fixes

5. You want to process a large list of numbers to find their sum. Which approach is better and why?

hard

A. Iteration is better because it uses less memory and avoids stack overflow

B. Recursion is better because it is easier to write for large lists

C. Recursion with memoization is best for summing lists

D. Recursive function without base case is best for performance

Solution

1. Step 1: Consider recursion limits for large lists

   Recursion uses call stack for each call, which can cause stack overflow for large lists.

2. Step 2: Compare iteration benefits

   Iteration uses constant memory and avoids stack overflow, making it safer and more efficient for large data.

3. Final Answer:

   Iteration is better because it uses less memory and avoids stack overflow -> Option A

4. Quick Check:

   Iteration safer for large data = A [OK]

Hint: Use iteration for large data to avoid stack overflow [OK]

Common Mistakes:

• Assuming recursion always simpler for large data
• Ignoring stack overflow risk
• Misusing memoization for simple sums