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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive vs Iterative Factorial

What is the output of the following C code snippet that calculates factorial using recursion and iteration?

DSA C

#include <stdio.h>

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 = 5;
    printf("Recursive: %d\n", factorial_recursive(n));
    printf("Iterative: %d\n", factorial_iterative(n));
    return 0;
}

A

Recursive: 120
Iterative: 24

B

Recursive: 120
Iterative: 120

C

Recursive: 24
Iterative: 120

D

Recursive: 0
Iterative: 0

💡 Hint

Recall that factorial of 5 is 5*4*3*2*1 = 120.

Both recursive and iterative functions correctly compute factorial of 5 as 120.

🧠 Conceptual

intermediate

When is recursion preferred over iteration?

Which scenario best explains when recursion is preferred over iteration?

A When the problem can be divided into similar subproblems and has a clear base case.

B When the problem requires simple repeated addition or multiplication.

C When memory usage must be minimized and stack overflow avoided.

D When the problem involves only linear traversal of data.

💡 Hint

Think about problems like tree traversals or divide and conquer.

Recursion is best when a problem breaks down into smaller similar problems with a base case, like tree traversals or quicksort.

❓ Predict Output

advanced

Stack Overflow Risk in Recursion

What happens when the following recursive function is called with a large input like 100000?

DSA C

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

int main() {
    recurse(100000);
    return 0;
}

A Program runs infinitely without stopping.

B Program prints numbers from 100000 down to 0.

C Program causes a stack overflow error and crashes.

D Program runs successfully without errors.

💡 Hint

Consider how deep the recursion goes and stack size limits.

Deep recursion like 100000 calls exceeds typical stack size, causing stack overflow and crash.

🧠 Conceptual

advanced

Iteration advantage over recursion

Why is iteration often preferred over recursion in some cases?

A Iteration uses less memory and avoids stack overflow risks.

B Iteration is always faster than recursion in all problems.

C Iteration can solve problems that recursion cannot.

D Iteration automatically handles base cases better than recursion.

💡 Hint

Think about memory usage and function call overhead.

Iteration uses a single loop and less memory, avoiding stack overflow and overhead of recursive calls.

🚀 Application

expert

Choosing recursion or iteration for tree traversal

Given a binary tree, which approach is generally better for inorder traversal and why?

A Recursion, because iteration cannot visit nodes in order.

B Iteration, because recursion cannot be used for tree traversal.

C Iteration, because recursion always causes stack overflow in trees.

D Recursion, because it naturally follows the tree structure and is easier to implement.

💡 Hint

Think about how recursion matches the hierarchical nature of trees.

Recursion fits tree traversal naturally by visiting left subtree, node, then right subtree with simple code.

Practice

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

easy

A. When you want to avoid function calls

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

C. When memory usage must be minimal

D. When the problem requires simple repeated loops

Solution

1. Step 1: Understand recursion use case

   Recursion works well when a problem breaks down into smaller similar problems, like factorial or tree traversal.

2. Step 2: Compare with iteration use cases

   Iteration is better for simple repeated loops without breaking problems into smaller parts.

3. Final Answer:

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

4. Quick Check:

   Recursion = divide and conquer [OK]

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

Common Mistakes:

• Thinking recursion is always better for memory
• Confusing iteration as better for divide-and-conquer
• Ignoring function call overhead in recursion

2. Which of the following is the correct syntax for 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 recursive call with base condition

   Recursive functions must have a condition to stop calling themselves to avoid infinite recursion.

2. Step 2: Check options for base condition

   void func() { if(condition) func(); } calls itself only if a condition is true, which is correct recursive syntax.

3. Final Answer:

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

4. Quick Check:

   Recursive call inside condition = void func() { if(condition) func(); } [OK]

Hint: Recursive calls need a stopping condition [OK]

Common Mistakes:

• Missing base condition causing infinite recursion
• Using loops instead of conditional recursion
• Confusing infinite loops with recursion

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

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

int main() {
  printf("%d", factorial(4));
  return 0;
}

medium

A. 24

B. 10

C. 120

D. Error: infinite recursion

Solution

1. Step 1: Trace factorial(4) calls

   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

   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 recursion multiplies down to 1 [OK]

Common Mistakes:

• Confusing factorial(4) with sum 1+2+3+4
• Forgetting base case returns 1
• Assuming infinite recursion error

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

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

medium

A. Return type should be void

B. Missing base case

C. Recursive call uses same argument causing infinite recursion

D. Function should use iteration instead

Solution

1. Step 1: Check base case correctness

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

2. Step 2: Analyze recursive call argument

   The recursive call uses sum(n) instead of sum(n-1), so it calls itself with the same argument endlessly causing infinite recursion.

3. Final Answer:

   Recursive call uses same argument causing infinite recursion -> Option C

4. Quick Check:

   Recursive argument must change to avoid infinite calls [OK]

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

Common Mistakes:

• Ignoring argument change in recursive call
• Thinking base case alone stops recursion
• Confusing return type with recursion correctness

5. You need to process a large dataset with limited memory. Which approach is better and why?

// Approach 1: Recursive traversal
void process(int n) {
  if (n == 0) return;
  process(n-1);
  printf("%d ", n);
}

// Approach 2: Iterative traversal
void process_iter(int n) {
  for (int i = 1; i <= n; i++) {
    printf("%d ", i);
  }
}

hard

A. Recursive is better because it uses less memory

B. Both are equally good for memory

C. Neither works for large datasets

D. Iterative is better because recursion uses stack memory for calls

Solution

1. Step 1: Analyze memory usage of recursion

   Recursive calls add stack frames for each call, increasing memory usage proportional to n.

2. Step 2: Analyze iteration memory usage

   Iteration uses a fixed amount of memory for loop variables, so it uses less memory overall.

3. Final Answer:

   Iterative is better because recursion uses stack memory for calls -> Option D

4. Quick Check:

   Iteration uses less memory than recursion [OK]

Hint: Iteration avoids stack overhead of recursion [OK]

Common Mistakes:

• Assuming recursion always uses less memory
• Ignoring stack overflow risk in recursion
• Thinking iteration uses more memory due to loops