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

Mental Model

Recursion solves problems by breaking them into smaller copies of the same problem, while iteration repeats steps using loops. Each works best depending on problem size and clarity.

Analogy: Imagine climbing stairs: recursion is like asking a friend to climb one step and then call you again for the next, while iteration is you climbing step by step yourself in a loop.

Recursion:
main() -> func() -> func() -> func() -> base case
Iteration:
start -> loop -> loop -> loop -> 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: Call factorial(4) recursively

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

Why: Recursion breaks problem into smaller factorial calls until base case 0

Step 2: Reach base case factorial(0) = 1 and start returning

factorial(0)=1 -> factorial(1)=1 -> factorial(2)=2 -> factorial(3)=6 -> factorial(4)=24

Why: Base case stops recursion and results multiply back up

Step 3: Calculate factorial(4) iteratively using a loop

result=1; multiply by 1,2,3,4 sequentially -> result=24

Why: Iteration uses a loop to multiply numbers from 1 to 4 directly

Result:

Recursion call stack:
factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)=1
Return values multiply back: 1 -> 1 -> 2 -> 6 -> 24
Iteration steps:
result=1 -> 1*1=1 -> 1*2=2 -> 2*3=6 -> 6*4=24
Final factorial(4) = 24

Annotated Code

DSA C++

#include <iostream>
using namespace std;

// Recursive factorial function
int factorial_recursive(int n) {
    if (n == 0) return 1; // base case stops recursion
    return n * factorial_recursive(n - 1); // multiply current n by factorial of n-1
}

// Iterative factorial function
int factorial_iterative(int n) {
    int result = 1;
    for (int i = 1; i <= n; i++) {
        result *= i; // multiply result by i each loop
    }
    return result;
}

int main() {
    int n = 4;
    cout << "Recursive factorial(" << n << ") = " << factorial_recursive(n) << endl;
    cout << "Iterative factorial(" << n << ") = " << factorial_iterative(n) << endl;
    return 0;
}

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

stop recursion when problem is smallest (base case)

return n * factorial_recursive(n - 1); // multiply current n by factorial of n-1

break problem into smaller subproblem and combine results

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

repeat multiplication step by step using loop

Output

Recursive factorial(4) = 24

Iterative factorial(4) = 24

Complexity Analysis

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

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

vs Alternative: Iteration is more space efficient; recursion is clearer for problems naturally defined by smaller subproblems

Edge Cases

n = 0 (base case)

Recursion returns 1 immediately; iteration returns 1 after loop runs zero times

DSA C++

if (n == 0) return 1;

n = 1 (smallest positive)

Both recursion and iteration return 1 correctly

DSA C++

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

When to Use This Pattern

When a problem can be broken into smaller similar problems, recursion is natural; when you want to save memory and avoid overhead, iteration is better.

Common Mistakes

Mistake: Forgetting the 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 uses loops to repeat steps.

Use recursion when problem naturally breaks down into smaller similar problems; use iteration for better memory efficiency.

The key insight is recursion uses call stack to remember states, iteration uses loops to repeat steps without extra memory.

Practice

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

easy

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

B. When you need to process a large list without stack overflow risk

C. When you want to avoid function call overhead

D. When the problem requires simple repeated loops

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 similar smaller subproblems -> Option A

4. Quick Check:

   Recursion fits divide-and-conquer problems [OK]

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

Common Mistakes:

• Thinking iteration is always better
• Ignoring stack overflow risk in recursion
• Confusing recursion with simple loops

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

easy

A. void func() { if(condition) func(); }

B. void func() { func(); }

C. void func() { while(true) func(); }

D. void func() { for(int i=0; i<10; i++) func(); }

Solution

1. Step 1: Identify base case in recursion

   Recursive functions must have a condition to stop calling themselves, usually an if statement.

2. Step 2: Check options for base case usage

   void func() { if(condition) func(); } uses if(condition) to control recursion, preventing infinite calls. Others cause infinite recursion or loops.

3. Final Answer:

   void func() { if(condition) func(); } -> Option A

4. Quick Check:

   Recursion needs a stopping condition [OK]

Hint: Recursive functions must have a stopping condition [OK]

Common Mistakes:

• Writing recursion without base case
• Using loops inside recursion incorrectly
• Confusing infinite loops with recursion

3. What is the output of the following C++ code?

int factorial(int n) {
  if (n == 0) return 1;
  return n * factorial(n - 1);
}

int main() {
  std::cout << factorial(4);
  return 0;
}

medium

A. Error: infinite recursion

B. 10

C. 120

D. 24

Solution

1. Step 1: Trace factorial calls

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

2. Step 2: Calculate return values

   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 D

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial n! = n*(n-1)! with base case 0! = 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Missing base case causing infinite recursion
• Incorrect multiplication order

4. Identify the error in this recursive function to compute the sum of numbers from 1 to n:

int sum(int n) {
  if (n == 1) return 1;
  return n + sum(n);
}

medium

A. Missing base case

B. Recursive call does not reduce n, causing infinite recursion

C. Should use a loop instead of recursion

D. Function should return void

Solution

1. Step 1: Check base case correctness

   The base case is correct: if n == 1, return 1.

2. Step 2: Analyze recursive call argument

   The recursive call is sum(n), which does not reduce n, so it calls itself infinitely without progress.

3. Final Answer:

   Recursive call does not reduce n, causing infinite recursion -> Option B

4. Quick Check:

   Recursive calls must reduce problem size [OK]

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

Common Mistakes:

• Not reducing argument in recursion
• Confusing base case with recursive step
• Assuming recursion always works without checks

5. You want to process a large dataset with millions of elements. Which approach is better and why?

A recursive function that processes one element and calls itself for the rest,
or an iterative loop that processes elements one by one?

hard

A. Recursive approach, because it uses less memory

B. Recursive approach, because it is easier to write

C. Iterative approach, because recursion risks stack overflow with large data

D. Both are equally good for large datasets

Solution

1. Step 1: Understand recursion limits

   Recursion uses the call stack for each call, which is limited and can overflow with millions of calls.

2. Step 2: Compare iteration benefits

   Iteration uses a single loop and constant stack space, making it safer and more efficient for large datasets.

3. Final Answer:

   Iterative approach, because recursion risks stack overflow with large data -> Option C

4. Quick Check:

   Iteration avoids stack overflow in large data [OK]

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

Common Mistakes:

• Assuming recursion is always simpler
• Ignoring stack size limits
• Thinking recursion uses less memory