Recursion vs Iteration When Each Wins in DSA C - Complexity Comparison

Time Complexity: Recursion vs Iteration When Each Wins

O(n)

Understanding Time Complexity

We want to understand how recursion and iteration compare in time cost for solving problems.

Which method grows faster in work as input size increases?

Scenario Under Consideration

Analyze the time complexity of these two ways to sum numbers from 1 to n.

// Recursive sum
int sum_recursive(int n) {
    if (n == 0) return 0;
    return n + sum_recursive(n - 1);
}

// Iterative sum
int sum_iterative(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++) {
        total += i;
    }
    return total;
}
    

Both calculate the sum from 1 to n but use different approaches.

Identify Repeating Operations

Look at what repeats in each method.

• Primary operation: Adding numbers from 1 to n.
• How many times: Both do this n times; recursion calls itself n times, iteration loops n times.

How Execution Grows With Input

As n grows, both methods do more additions.

Input Size (n)	Approx. Operations
10	10 additions
100	100 additions
1000	1000 additions

Pattern observation: The work grows directly with n; doubling n doubles the work.

Final Time Complexity

Time Complexity: O(n)

This means the time to complete grows in a straight line with input size.

Common Mistake

[X] Wrong: "Recursion is always slower and less efficient than iteration."

[OK] Correct: Both can have the same time complexity; recursion can be clearer or better for some problems, and iteration can sometimes use less memory.

Interview Connect

Understanding when recursion or iteration is better helps you choose the right tool and explain your reasoning clearly in interviews.

Self-Check

"What if the recursive function used memoization to save results? How would that affect time complexity?"

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