Recursion vs Iteration When Each Wins in DSA C++ - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When is recursion preferred over iteration?

Choose the best scenario where recursion is generally preferred over iteration.

A When the problem requires simple repeated addition or counting loops.

B When the problem is naturally hierarchical or tree-structured, like traversing a file system.

C When memory usage must be minimal and stack overflow is a concern.

D When the problem involves processing large arrays with no nested structure.

💡 Hint

Think about problems that break down into smaller similar problems.

Recursion is preferred when the problem naturally fits a hierarchical structure, such as trees or graphs, because it simplifies code and matches the problem's nature.

❓ Predict Output

intermediate

Output of recursive vs iterative factorial

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

int factorial_recursive(int n) {
    if (n <= 1) return 1;
    return n * factorial_recursive(n - 1);
}

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

int main() {
    int n = 4;
    std::cout << factorial_recursive(n) << " " << factorial_iterative(n) << std::endl;
    return 0;
}

DSA C++

int factorial_recursive(int n) {
    if (n <= 1) return 1;
    return n * factorial_recursive(n - 1);
}

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

int main() {
    int n = 4;
    std::cout << factorial_recursive(n) << " " << factorial_iterative(n) << std::endl;
    return 0;
}

A 24 24

B 24 120

C 120 24

D 120 120

💡 Hint

Calculate 4! (4 factorial) both ways.

4! = 4 * 3 * 2 * 1 = 24. Both recursive and iterative functions compute this correctly.

❓ Predict Output

advanced

Stack overflow risk in recursion

What happens when running this C++ code?

void recurse(int n) {
    if (n == 0) return;
    recurse(n - 1);
}

int main() {
    recurse(1000000);
    std::cout << "Done" << std::endl;
    return 0;
}

DSA C++

void recurse(int n) {
    if (n == 0) return;
    recurse(n - 1);
}

int main() {
    recurse(1000000);
    std::cout << "Done" << std::endl;
    return 0;
}

A Causes a stack overflow runtime error.

B Prints 'Done' without errors.

C Infinite recursion causing program hang.

D Compilation error due to missing return.

💡 Hint

Consider the maximum recursion depth allowed by the system stack.

Recursing one million times exceeds typical stack size, causing a stack overflow runtime error.

🧠 Conceptual

advanced

When is iteration preferred over recursion?

Choose the best reason to prefer iteration instead of recursion.

A When the problem requires breaking down into smaller subproblems.

B When the problem is naturally hierarchical like tree traversal.

C When the problem involves deep recursion that risks stack overflow.

D When the problem is simple and requires no repeated steps.

💡 Hint

Think about memory and performance limits.

Iteration avoids the overhead and risk of stack overflow that deep recursion can cause, making it better for large or simple repeated tasks.

🚀 Application

expert

Choosing recursion or iteration for Fibonacci sequence

You want to compute the 30th Fibonacci number efficiently. Which approach is best?

A Recursive function that prints each Fibonacci number without returning.

B Simple recursive function without memoization.

C Recursive function with memoization (caching results).

D Iterative function using a loop and two variables.

💡 Hint

Consider time complexity and memory usage.

Simple recursion is slow (exponential time). Memoization helps but uses extra memory. Iteration is fast and uses minimal memory, best for computing a single Fibonacci number efficiently.

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