Recursion vs Iteration When Each Wins in DSA C - Key Differences

Recall & Review

beginner

What is recursion in programming?

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case it can solve directly.

beginner

What is iteration in programming?

Iteration means repeating a set of instructions using loops like for or while until a condition is met.

intermediate

When is recursion better than iteration?

Recursion is better when the problem is naturally divided into similar smaller problems, like tree traversals or factorial calculation, making the code simpler and easier to understand.

intermediate

When is iteration better than recursion?

Iteration is better when performance and memory use are important because it uses less memory and avoids the overhead of function calls, such as in simple loops or large data processing.

intermediate

What is a risk of using recursion in C?

Using recursion in C can cause stack overflow if the recursion is too deep because each function call uses memory on the call stack.

Which method uses function calls to solve smaller parts of a problem?

A Both

B Iteration

C Neither

D Recursion

Recursion solves problems by calling the same function with smaller inputs.

Which method generally uses less memory in C?

A Recursion

B Both use the same

C Iteration

D Depends on compiler

Iteration uses loops and does not add function calls to the stack, so it uses less memory.

Which is a natural fit for problems like tree traversal?

A Iteration

B Recursion

C Neither

D Both equally

Recursion matches the structure of trees, making traversal easier to write.

What can happen if recursion is too deep in C?

A Stack overflow

B Faster execution

C Memory leak

D No effect

Too many recursive calls can exhaust the call stack, causing a stack overflow.

Which method is usually easier to debug for simple repeated tasks?

A Iteration

B Recursion

C Both are equally easy

D Neither

Iteration uses loops which are straightforward and easier to follow for simple tasks.

Explain when you would choose recursion over iteration and why.

Think about problems that look like smaller copies of themselves.

Describe the risks and limitations of using recursion in C.

Consider what happens when too many functions call themselves.

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