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

Mental Model

Recursion solves problems by breaking them into smaller copies of itself, 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 another friend to climb the next, passing the task down until the top; iteration is like climbing step by step yourself in a loop.

Recursion stack:
main -> func(3) -> func(2) -> func(1) -> base case

Iteration loop:
start -> step 1 -> step 2 -> step 3 -> end

Dry Run Walkthrough

Input: Calculate factorial of 4 using recursion and iteration

Goal: Show how recursion and iteration compute factorial and when each is clearer or efficient

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

Stack: factorial(4) -> factorial(3) ↑

Why: Break problem into smaller factorial(3)

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

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

Why: Keep breaking down until base case

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

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

Why: Reach smallest problem

Step 4: Recursion hits base case factorial(1) = 1, returns 1

Stack unwinding: factorial(1) returns 1

Why: Base case stops recursion

Step 5: factorial(2) returns 2 * 1 = 2

Stack unwinding: factorial(2) returns 2

Why: Combine results going back up

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

Stack unwinding: factorial(3) returns 6

Why: Combine results going back up

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

Stack unwinding: factorial(4) returns 24

Why: Final result computed

Step 8: Iteration starts with result=1, i=1

result=1, i=1

Why: Initialize iteration

Step 9: Multiply result by i=1 -> result=1, increment i=2

result=1, i=2

Why: First step of loop

Step 10: Multiply result by i=2 -> result=2, increment i=3

result=2, i=3

Why: Second step of loop

Step 11: Multiply result by i=3 -> result=6, increment i=4

result=6, i=4

Why: Third step of loop

Step 12: Multiply result by i=4 -> result=24, increment i=5

result=24, i=5

Why: Final multiplication

Step 13: Loop ends as i > 4, return result=24

result=24

Why: Iteration complete

Result:

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

Annotated Code

DSA C

#include <stdio.h>

// Recursive factorial function
int factorial_recursive(int n) {
    if (n <= 1) {
        return 1; // base case
    }
    return n * factorial_recursive(n - 1); // recursive call
}

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

int main() {
    int num = 4;
    int rec_result = factorial_recursive(num);
    int iter_result = factorial_iterative(num);
    printf("Recursion factorial(%d) = %d\n", num, rec_result);
    printf("Iteration factorial(%d) = %d\n", num, iter_result);
    return 0;
}

if (n <= 1) { return 1; }

stop recursion at base case to avoid infinite calls

return n * factorial_recursive(n - 1);

recursive call reduces problem size by 1

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

loop multiplies result by each number from 1 to n

Output

Recursion factorial(4) = 24

Iteration factorial(4) = 24

Complexity Analysis

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

Space: O(n) for recursion due to call stack, O(1) for iteration using fixed variables

vs Alternative: Iteration uses less memory and is faster for large n; recursion is clearer for problems naturally defined by self-calls

Edge Cases

n = 0

Both return 1 as factorial of 0 is 1

DSA C

if (n <= 1) { return 1; }

n = 1

Both return 1 immediately

DSA C

if (n <= 1) { return 1; }

large n (e.g., 10000)

Recursion may cause stack overflow; iteration handles it safely

DSA C

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

When to Use This Pattern

When a problem naturally breaks into smaller subproblems, recursion is a good fit; when performance and memory are critical, iteration is preferred.

Common Mistakes

Mistake: Missing base case in recursion causing infinite calls
Fix: Add a clear base case like if (n <= 1) return 1;

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 problem is naturally recursive and input size is small; use iteration for large inputs or when memory is limited.

The key insight is recursion uses the call stack to remember work, while iteration uses fixed memory and loops.

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