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

Mental Model

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

Analogy: Recursion is like a set of nested Russian dolls, where each doll contains a smaller one inside, and iteration is like walking around a track repeatedly until you finish.

Recursion:
  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 the problem into smaller parts

Step 2: Recursion calls factorial(3), which calls factorial(2)

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

Why: Keep breaking down until base case

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

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

Why: Reach base case where factorial(1) = 1

Step 4: Recursion returns 1 for factorial(1), then factorial(2) = 2 * 1 = 2

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

Why: Start combining results back up

Step 5: Recursion returns factorial(3) = 3 * 2 = 6

returning: factorial(3)=6

Why: Combine next level

Step 6: Recursion returns factorial(4) = 4 * 6 = 24

returning: factorial(4)=24

Why: Final result computed

Step 7: Iteration starts with result=1 and i=1, multiply result by i

result=1, i=1

Why: Initialize iteration

Step 8: Iteration multiply result=1 * 2=2, i=2

result=2, i=2

Why: Multiply step by step

Step 9: Iteration multiply result=2 * 3=6, i=3

result=6, i=3

Why: Continue multiplication

Step 10: Iteration multiply result=6 * 4=24, i=4

result=24, i=4

Why: Final multiplication

Result:

Recursion stack unwound: factorial(4) = 24
Iteration final result: 24

Annotated Code

DSA Typescript

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

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

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

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

stop recursion when n is 1 or less

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

call factorial for smaller n and multiply

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

multiply result by each number from 1 to n

Output

Recursion factorial of 4 = 24

Iteration factorial of 4 = 24

Complexity Analysis

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

Space: Recursion uses O(n) space for call stack; iteration uses O(1) constant space

vs Alternative: Iteration is more space efficient since recursion uses extra stack memory; recursion can be simpler to write and understand for problems naturally defined recursively

Edge Cases

n = 0

Both recursion and iteration return 1 as factorial(0) = 1

DSA Typescript

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

n = 1

Both return 1 immediately without further calls or loops

DSA Typescript

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

negative n

Both return 1 immediately (recursion hits base case since n <= 1; iteration loop doesn't run), though factorial is undefined for negatives

DSA Typescript

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

When to Use This Pattern

When a problem naturally breaks into smaller similar problems, recursion is a good fit; when you want to save memory and avoid call stack overhead, iteration is better.

Common Mistakes

Mistake: Not defining a proper base case in recursion causing infinite calls
Fix: Add a base case like 'if (n <= 1) return 1' to stop recursion

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

Summary

Recursion solves problems by calling itself with smaller inputs; iteration uses loops to repeat steps.

Use recursion when the problem is naturally recursive and easier to express that way; use iteration when memory efficiency and speed matter.

The key insight is recursion uses the call stack to remember work, while iteration keeps track with variables and loops.

Practice

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

easy

A. When the problem requires simple repeated loops

B. When you want to avoid function call overhead

C. When the problem can be divided into similar smaller problems

D. When memory usage must be minimal

Solution

1. Step 1: Understand recursion vs iteration use cases

   Recursion works well when a problem can be broken down into smaller, similar subproblems, like tree traversals or factorial calculation. Iteration is better for simple repeated tasks without nested subproblems, and it avoids function call overhead.

2. Final Answer:

   When the problem can be divided into similar smaller problems -> Option C

3. Quick Check:

   Recursion = divide and conquer [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 recursion with simple loops

2. Which of the following is the correct syntax to write a recursive function in TypeScript?

easy

A. function recurse(n: number): number { if (n <= 1) return 1; return n * recurse(n - 1); }

B. function recurse(n: number): number { while (n > 1) { n--; } return n; }

C. function recurse(n: number): number { for (let i = 0; i < n; i++) { return i; } }

D. function recurse(n: number): number { if (n == 0) return 0; else return n + 1; }

Solution

1. Step 1: Identify recursive call and base case

   function recurse(n: number): number { if (n <= 1) return 1; return n * recurse(n - 1); }: function recurse(n: number): number { if (n <= 1) return 1; return n * recurse(n - 1); } calls itself inside the function with a smaller argument (n-1) and has a base case (n <= 1) to stop recursion.

2. Final Answer:

   function recurse(n: number): number { if (n <= 1) return 1; return n * recurse(n - 1); } -> Option A

3. Quick Check:

   Recursive function must call itself with smaller input [OK]

Hint: Look for function calling itself with smaller input [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Using loops instead of recursive calls
• Returning inside a loop without recursion

3. What will be the output of the following TypeScript code?

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

medium

A. 10

B. 24

C. 16

D. Error

Solution

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

   factorial(4) calls factorial(3), which calls factorial(2), which calls factorial(1)=1. Then: factorial(2)=2*1=2, factorial(3)=3*2=6, factorial(4)=4*6=24. Output: 24.

2. Final Answer:

   24 -> Option B

3. Quick Check:

   4! = 24 [OK]

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

Common Mistakes:

• Confusing factorial with sum
• Forgetting base case returns 1
• Miscounting recursive calls

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

function sumToN(n: number): number {
  return n + sumToN(n - 1);
}

medium

A. Add a base case to stop recursion when n <= 0

B. Change return to console.log to print values

C. Replace recursion with a for loop

D. Remove the parameter n

Solution

1. Step 1: Identify and fix the missing base case

   The function calls itself without a stopping condition, causing infinite recursion and stack overflow. Add if (n <= 0) return 0; to stop recursion when n <= 0.

2. Final Answer:

   Add a base case to stop recursion when n <= 0 -> Option A

3. Quick Check:

   Base case prevents infinite recursion [OK]

Hint: Always add base case to recursive functions [OK]

Common Mistakes:

• Forgetting base case causes infinite recursion
• Trying to fix by removing parameters
• Confusing printing with returning

5. You need to process a large dataset with a depth of 10,000 levels. Which approach is better and why?

Options:
A) Use recursion because it is easier to write.
B) Use recursion with no base case.
C) Use iteration to avoid stack overflow errors.
D) Use iteration but with no loop control.

hard

A. Use recursion because it is easier to write.

B. Use recursion with no base case.

C. Use iteration but with no loop control.

D. Use iteration to avoid stack overflow errors.

Solution

1. Step 1: Analyze stack limits for deep recursion

   Recursion uses the call stack, which has limited size. Depth of 10,000 risks stack overflow. Iteration uses loops without adding to call stack, safely handling large depths.

2. Final Answer:

   Use iteration to avoid stack overflow errors. -> Option D

3. Quick Check:

   Deep tasks need iteration to prevent stack overflow [OK]

Hint: Deep recursion risks stack overflow; prefer iteration [OK]

Common Mistakes:

• Assuming recursion always better for readability
• Ignoring stack size limits
• Using recursion without base case