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

Concept Flow - Recursion vs Iteration When Each Wins

Start Problem

↓

Choose Approach

↓

Recursion

↓

Function calls

↓

Stack builds

↓

Base case?

↓

Return result

↓

Result

The flow shows choosing between recursion and iteration, how recursion uses function calls and stack, iteration uses loops and variables, both end when base condition or loop condition fails, then return result.

Execution Sample

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;
}

Calculates factorial of n using recursion and iteration.

Execution Table

Step	Operation	Call Stack / Loop Variable	Action	Result / Stack State
1	Call factorial_recursive(3)	Stack: factorial_recursive(3)	Check if n <= 1 (3 <= 1?)	No, proceed to recursive call
2	Call factorial_recursive(2)	Stack: factorial_recursive(3) -> factorial_recursive(2)	Check if n <= 1 (2 <= 1?)	No, proceed to recursive call
3	Call factorial_recursive(1)	Stack: factorial_recursive(3) -> factorial_recursive(2) -> factorial_recursive(1)	Check if n <= 1 (1 <= 1?)	Yes, return 1
4	Return from factorial_recursive(1)	Stack: factorial_recursive(3) -> factorial_recursive(2)	Return 1	Stack unwinds
5	Return from factorial_recursive(2)	Stack: factorial_recursive(3)	Return 2 * 1 = 2	Stack unwinds
6	Return from factorial_recursive(3)	Stack: empty	Return 3 * 2 = 6	Stack unwinds, final result 6
7	Start factorial_iterative(3)	i=2, result=1	Multiply result by i (1 * 2)	result=2
8	Loop iteration	i=3, result=2	Multiply result by i (2 * 3)	result=6
9	Loop ends	i=4 (condition i<=3 false)	Exit loop	Final result=6

💡 Recursion ends when base case n<=1 is true; iteration ends when loop condition i<=n is false.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	After Step 8	After Step 9
n (recursive)	3	3	2	1	1	2	3	-	-	-
Call Stack	empty	factorial_recursive(3)	factorial_recursive(3)->factorial_recursive(2)	factorial_recursive(3)->factorial_recursive(2)->factorial_recursive(1)	factorial_recursive(3)->factorial_recursive(2)	factorial_recursive(3)	empty	-	-	-
i (iterative)	-	-	-	-	-	-	-	2	3	4
result (iterative)	-	-	-	-	-	-	-	1	2	6

Key Moments - 3 Insights

Why does recursion use a call stack while iteration uses variables?

Recursion calls itself repeatedly, each call waiting for the next to finish, so the system keeps track of each call in a stack (see steps 1-6). Iteration uses a loop with variables updated in place without extra calls (see steps 7-9).

When does recursion stop calling itself?

Recursion stops when the base case condition is true (n <= 1), as shown in step 3 where factorial_recursive(1) returns 1.

Why does iteration stop when i > n?

The loop condition i <= n controls iteration. When i becomes 4 (step 9), the condition fails and the loop exits.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what happens?

A The base case is true and recursion returns 1

B The loop starts with i=1

C The recursion calls factorial_recursive(4)

D The iteration multiplies result by 3

💡 Hint

Check the 'Action' and 'Result / Stack State' columns at step 3 in execution_table

At which step does the iteration loop end?

A Step 7

B Step 8

C Step 9

D Step 6

💡 Hint

Look for the step where the loop condition becomes false in execution_table

If n was 5, how would the call stack change compared to step 2?

A It would have more recursive calls before base case

B It would have fewer recursive calls

C It would be empty immediately

D It would not change

💡 Hint

Check variable_tracker for how n changes and how many calls are made before base case

Concept Snapshot

Recursion calls the same function repeatedly until a base case stops it.
Iteration uses loops to repeat actions until a condition fails.
Recursion uses a call stack to remember each call.
Iteration updates variables in place without extra calls.
Use recursion for problems naturally divided into subproblems.
Use iteration for simple repeated tasks with less memory overhead.

Full Transcript

This lesson compares recursion and iteration by tracing factorial calculation both ways. Recursion calls itself with decreasing n until n <= 1, building a call stack that unwinds to produce the result. Iteration uses a loop multiplying result by i from 2 to n. The execution table shows each recursive call and return, and each loop iteration. Variables like n, i, and result change step by step. Key moments explain why recursion needs a stack and stops at base case, and why iteration stops when loop condition fails. The quiz tests understanding of these steps. The snapshot summarizes when to use recursion or iteration.

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