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

Concept Flow - Recursion vs Iteration When Each Wins

Start Problem

↓

Recursion

↓

Divide problem

↓

into smaller

↓

subproblems

↓

Base case?

↓

Return result

↓

Problem Solved

This flow shows how to decide between recursion and iteration: recursion breaks problems into smaller parts with base cases, iteration repeats steps with loops until a condition ends.

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 State	Return / Result	Visual State
1	Call factorial_recursive(3)	Stack: [factorial_recursive(3)]	Pending	Stack grows: 3
2	Call factorial_recursive(2)	Stack: [factorial_recursive(3), factorial_recursive(2)]	Pending	Stack grows: 3 -> 2
3	Call factorial_recursive(1)	Stack: [factorial_recursive(3), factorial_recursive(2), factorial_recursive(1)]	Returns 1	Base case reached
4	Return from factorial_recursive(1)	Stack: [factorial_recursive(3), factorial_recursive(2)]	1	Stack shrinks: 3 -> 2
5	Calculate 2 * 1	Stack: [factorial_recursive(3), factorial_recursive(2)]	2	Result computed at level 2
6	Return from factorial_recursive(2)	Stack: [factorial_recursive(3)]	2	Stack shrinks: 3
7	Calculate 3 * 2	Stack: [factorial_recursive(3)]	6	Result computed at level 3
8	Return from factorial_recursive(3)	Stack: []	6	Stack empty, done
9	Start factorial_iterative(3)	Loop i=2 to 3, result=1	Pending	result=1
10	Multiply result by i=2	Loop i=3, result=1*2=2	Pending	result=2
11	Multiply result by i=3	Loop ends after i=3, result=2*3=6	Pending	result=6
12	Return result	Loop finished	6	Done

💡 Recursion ends when base case n<=1 is reached; iteration ends when loop i > n.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 5	After Step 7	After Step 9	After Step 10	After Step 11	Final
n (recursive)	3	3	2	1	2	3	-	-	-	-
Call Stack Depth	0	1	2	3	2	1	0	0	0	0
result (iterative)	1	-	-	-	-	-	1	2	6	6
i (iterative)	-	-	-	-	-	-	2	3	3	-

Key Moments - 3 Insights

Why does recursion need a base case?

The base case stops recursion from calling itself forever. In the execution_table rows 3 and 4, when n=1, recursion returns 1 instead of calling again, preventing infinite calls.

Why does iteration use a loop condition instead of a base case?

Iteration repeats steps while a condition is true. In rows 9 to 11, the loop runs while i <= n, stopping when i becomes 4, unlike recursion which uses a base case to stop.

How does the call stack change during recursion?

Each recursive call adds a new frame to the stack (rows 1-3). When base case returns, stack frames are removed one by one (rows 4-8), showing how recursion unwinds.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what happens?

A The loop starts for iteration

B The base case is reached and returns 1

C The stack is empty

D The result is multiplied by 3

💡 Hint

Check Step 3 in execution_table where factorial_recursive(1) returns 1 as base case

At which step does the iterative loop finish?

A Step 9

B Step 10

C Step 11

D Step 12

💡 Hint

Look at Step 11 where loop ends after i=3 with result=6

If the input n was 1, how would the recursion call stack change?

A It would have 1 call and return immediately

B It would loop infinitely

C It would have 3 calls

D It would skip the base case

💡 Hint

Refer to variable_tracker for n and call stack depth; base case triggers immediate return

Concept Snapshot

Recursion breaks problems into smaller parts and uses a base case to stop.
Iteration uses loops to repeat steps until a condition ends.
Use recursion when problem naturally divides (e.g., trees).
Use iteration for simple repeated steps (e.g., factorial).
Recursion uses more memory (call stack), iteration is usually faster.
Choose based on clarity and performance needs.

Full Transcript

This lesson compares recursion and iteration by tracing factorial calculation both ways. Recursion calls itself with smaller inputs until a base case stops it, shown by the call stack growing and shrinking. Iteration uses a loop to multiply numbers until the loop ends. The execution table tracks each step, showing how recursion builds and unwinds the stack, while iteration updates variables in a loop. Key moments explain why recursion needs a base case and how iteration uses loop conditions. The visual quiz tests understanding of these steps. Recursion is good for problems naturally split into smaller parts, iteration for simple repeated actions. Recursion uses more memory due to call stack, iteration is often faster and simpler.

Practice

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

easy

A. When the problem can be divided into similar smaller subproblems

B. When you need to process a large list without stack overflow risk

C. When you want to avoid function call overhead

D. When the problem requires simple repeated loops

Solution

1. Step 1: Understand recursion use case

   Recursion works well when a problem can be broken down into smaller versions of itself, like tree traversals or factorial calculation.

2. Step 2: Compare with iteration scenarios

   Iteration is better for simple repeated tasks without nested subproblems, so recursion is preferred for divide-and-conquer problems.

3. Final Answer:

   When the problem can be divided into similar smaller subproblems -> Option A

4. Quick Check:

   Recursion fits divide-and-conquer problems [OK]

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

Common Mistakes:

• Thinking iteration is always better
• Ignoring stack overflow risk in recursion
• Confusing recursion with simple loops

2. Which of the following is the correct syntax to write 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 base case in recursion

   Recursive functions must have a condition to stop calling themselves, usually an if statement.

2. Step 2: Check options for base case usage

   void func() { if(condition) func(); } uses if(condition) to control recursion, preventing infinite calls. Others cause infinite recursion or loops.

3. Final Answer:

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

4. Quick Check:

   Recursion needs a stopping condition [OK]

Hint: Recursive functions must have a stopping condition [OK]

Common Mistakes:

• Writing recursion without base case
• Using loops inside recursion incorrectly
• Confusing infinite loops with recursion

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

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

int main() {
  std::cout << factorial(4);
  return 0;
}

medium

A. Error: infinite recursion

B. 10

C. 120

D. 24

Solution

1. Step 1: Trace factorial calls

   factorial(4) calls factorial(3), factorial(2), factorial(1), factorial(0). factorial(0) 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 D

4. Quick Check:

   4! = 24 [OK]

Hint: Factorial n! = n*(n-1)! with base case 0! = 1 [OK]

Common Mistakes:

• Confusing factorial with sum
• Missing base case causing infinite recursion
• Incorrect multiplication order

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

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

medium

A. Missing base case

B. Recursive call does not reduce n, causing infinite recursion

C. Should use a loop instead of recursion

D. Function should return void

Solution

1. Step 1: Check base case correctness

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

2. Step 2: Analyze recursive call argument

   The recursive call is sum(n), which does not reduce n, so it calls itself infinitely without progress.

3. Final Answer:

   Recursive call does not reduce n, causing infinite recursion -> Option B

4. Quick Check:

   Recursive calls must reduce problem size [OK]

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

Common Mistakes:

• Not reducing argument in recursion
• Confusing base case with recursive step
• Assuming recursion always works without checks

5. You want to process a large dataset with millions of elements. Which approach is better and why?

A recursive function that processes one element and calls itself for the rest,
or an iterative loop that processes elements one by one?

hard

A. Recursive approach, because it uses less memory

B. Recursive approach, because it is easier to write

C. Iterative approach, because recursion risks stack overflow with large data

D. Both are equally good for large datasets

Solution

1. Step 1: Understand recursion limits

   Recursion uses the call stack for each call, which is limited and can overflow with millions of calls.

2. Step 2: Compare iteration benefits

   Iteration uses a single loop and constant stack space, making it safer and more efficient for large datasets.

3. Final Answer:

   Iterative approach, because recursion risks stack overflow with large data -> Option C

4. Quick Check:

   Iteration avoids stack overflow in large data [OK]

Hint: Use iteration for large data to avoid stack overflow [OK]

Common Mistakes:

• Assuming recursion is always simpler
• Ignoring stack size limits
• Thinking recursion uses less memory