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

Concept Flow - Recursion vs Iteration When Each Wins

Start Problem

↓

Choose Approach

↓

Recursion

[Divide into [Use loops to↓

Combine results

↓

Final Result

↩[Divide into [Use loops to

Shows the choice between recursion and iteration, how recursion divides problems and combines results, while iteration uses loops to repeat steps until done.

Execution Sample

DSA Java

int factorialRec(int n) {
  if (n <= 1) return 1;
  return n * factorialRec(n - 1);
}

int factorialIter(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 Iteration	Current n or i	Partial Result	Action	Visual State
1	Call factorialRec(3)	Stack: factorialRec(3)	3	-	Check if n <= 1 (No)	Stack grows: 3
2	Call factorialRec(2)	Stack: factorialRec(3) -> factorialRec(2)	2	-	Check if n <= 1 (No)	Stack grows: 3 -> 2
3	Call factorialRec(1)	Stack: factorialRec(3) -> factorialRec(2) -> factorialRec(1)	1	-	n <= 1, return 1	Stack grows: 3 -> 2 -> 1
4	Return from factorialRec(1)	Stack: factorialRec(3) -> factorialRec(2)	1	1	Return 1	Stack shrinks: 3 -> 2
5	Return from factorialRec(2)	Stack: factorialRec(3)	2	2 * 1 = 2	Return 2	Stack shrinks: 3
6	Return from factorialRec(3)	Stack: empty	3	3 * 2 = 6	Return 6	Stack empty
7	Start factorialIter(3)	Loop i=2 to 3	i=2	result=1	Multiply result by i	result=2
8	Loop iteration	Loop i=2 to 3	i=3	result=2	Multiply result by i	result=6
9	End factorialIter	Loop ends	-	result=6	Return result	Final result=6
10	Stop	-	-	-	All done	No more calls or loops

💡 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 4	After Step 5	After Step 6	After Step 7	After Step 8	Final
n (recursion)	3	3	2	1	1	2	3	-	-	-
Call Stack	empty	3	3->2	3->2->1	3->2	3	empty	-	-	-
i (iteration)	-	-	-	-	-	-	-	2	3	-
result (iteration)	1	1	1	1	1	1	1	2	6	6

Key Moments - 3 Insights

Why does recursion need a base case like n <= 1?

Without the base case, recursion would call itself forever. In the execution_table rows 1-3, the base case stops further calls and starts returning results.

Why does iteration use a loop instead of calling itself?

Iteration repeats steps using a loop variable (i). In execution_table rows 7-9, the loop updates i and result until the condition fails, avoiding extra memory use from call stacks.

What happens to the call stack during recursion?

The call stack grows with each recursive call (rows 1-3) and shrinks as calls return (rows 4-6), tracking active function calls.

Visual Quiz - 3 Questions

Look at the execution_table at step 3, what is the value of n and what action happens?

A n=1, base case reached, return 1

B n=2, recursive call continues

C n=3, first call starts

D n=0, invalid input

💡 Hint

Check step 3 in execution_table under 'Current n or i' and 'Action' columns.

At which step does the iteration loop finish?

A Step 7

B Step 8

C Step 9

D Step 10

💡 Hint

Look for 'Loop ends' in the 'Operation' column in execution_table.

If n was 5 instead of 3, how would the call stack change in recursion?

A It would grow deeper with more calls before returning

B It would be shorter with fewer calls

C It would stay the same size

D It would not use a call stack

💡 Hint

Refer to variable_tracker 'Call Stack' row and how it grows with n in recursion.

Concept Snapshot

Recursion divides problems into smaller calls until a base case stops it.
Iteration uses loops to repeat steps until a condition fails.
Recursion uses more memory due to call stack; iteration is usually more memory efficient.
Use recursion when problem fits natural divide-and-conquer.
Use iteration for simple repeated steps or when memory is limited.

Full Transcript

This lesson compares recursion and iteration by tracing factorial calculation both ways. Recursion calls itself with smaller n until base case n <= 1, then returns results back up the call stack. Iteration uses a for loop multiplying result by i from 2 to n. The execution table shows each recursive call and return, and each loop iteration. The variable tracker shows how n, call stack, i, and result change step by step. Key moments explain why recursion needs a base case, how iteration repeats with loops, and how the call stack grows and shrinks. The visual quiz tests understanding of recursion base case, loop end, and call stack depth. The snapshot summarizes when to use recursion or iteration based on problem nature and memory use.

Practice

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

easy

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

B. When you want to avoid function call overhead

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 can be broken down into smaller similar problems, like tree traversals or factorial calculation.

2. Step 2: Compare with iteration scenarios

   Iteration is better for simple repeated loops or when minimizing overhead and memory is critical.

3. Final Answer:

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

4. Quick Check:

   Recursion fits divide-and-conquer problems = A [OK]

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

Common Mistakes:

• Thinking iteration is always better for all problems
• Ignoring function call overhead in recursion
• Confusing recursion with simple loops

2. Which of the following is the correct syntax to write a recursive method in Java?

easy

A. public void recurse() { recurse(); }

B. public void recurse() { while(true) recurse(); }

C. public void recurse() { if(condition) recurse(); }

D. public void recurse() { for(int i=0; i<10; i++) recurse(); }

Solution

1. Step 1: Identify valid recursive call

   A recursive method must have a base condition to stop calling itself, so it uses if(condition) before recursion.

2. Step 2: Check options for base condition

   public void recurse() { if(condition) recurse(); } uses if(condition) recurse(); which is correct. Others cause infinite recursion or misuse loops.

3. Final Answer:

   public void recurse() { if(condition) recurse(); } -> Option C

4. Quick Check:

   Base condition needed for recursion = D [OK]

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

Common Mistakes:

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

3. What will be the output of the following Java code?

public class Test {
  static int count = 0;
  public static void recurse(int n) {
    if (n == 0) return;
    count++;
    recurse(n - 1);
  }
  public static void main(String[] args) {
    recurse(3);
    System.out.println(count);
  }
}

medium

A. 4

B. 3

C. 0

D. StackOverflowError

Solution

1. Step 1: Trace recursive calls

   recurse(3) calls recurse(2), then recurse(1), then recurse(0) which returns without incrementing count.

2. Step 2: Count increments

   count increments at n=3, 2, 1, so total increments = 3.

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Count increments per call except base = 3 [OK]

Hint: Count increments before recursive call, base stops at zero [OK]

Common Mistakes:

• Counting base case call as increment
• Expecting stack overflow due to small input
• Miscounting recursive calls

4. Identify the error in this iterative factorial method and fix it:

public static int factorial(int n) {
  int result = 1;
  for (int i = 1; i <= n; i++) {
    result = result * i;
  }
  return result;
}

// Called with factorial(-3)

medium

A. Missing return statement

B. Infinite loop due to wrong loop condition

C. No error, returns 1 for negative input

D. Should check for negative input to avoid incorrect result

Solution

1. Step 1: Analyze loop behavior with negative input

   For n = -3, loop condition i <= n is false at start (1 <= -3), so loop never runs and returns 1 incorrectly.

2. Step 2: Add input validation

   Factorial is undefined for negative numbers, so method should check and handle negative input before loop.

3. Final Answer:

   Should check for negative input to avoid incorrect result -> Option D

4. Quick Check:

   Validate input before iteration = A [OK]

Hint: Always validate inputs before loops in iterative methods [OK]

Common Mistakes:

• Ignoring negative inputs in factorial
• Assuming loop runs for negative n
• Missing input validation

5. You need to process a large dataset with unknown depth of nested structures. Which approach is better and why?

Options:
A) Use recursion for simplicity but risk stack overflow.
B) Use iteration with explicit stack to handle unknown depth safely.
C) Use recursion with no base case to ensure all data is processed.
D) Use iteration with fixed loop count assuming max depth known.

hard

A. Use iteration with explicit stack to handle unknown depth safely.

B. Use recursion for simplicity but risk stack overflow.

C. Use recursion with no base case to ensure all data is processed.

D. Use iteration with fixed loop count assuming max depth known.

Solution

1. Step 1: Understand problem constraints

   Unknown depth means recursion might cause stack overflow if too deep.

2. Step 2: Compare recursion and iteration

   Iteration with an explicit stack simulates recursion safely and avoids overflow.

3. Step 3: Evaluate incorrect options

   Use recursion with no base case to ensure all data is processed. is wrong due to no base case causing infinite recursion. Use iteration with fixed loop count assuming max depth known. assumes fixed depth which is unsafe.

4. Final Answer:

   Use iteration with explicit stack to handle unknown depth safely. -> Option A

5. Quick Check:

   Iteration + explicit stack avoids recursion limits = B [OK]

Hint: Use explicit stack iteration for unknown or deep recursion [OK]

Common Mistakes:

• Ignoring stack overflow risk in recursion
• Assuming fixed depth for iteration
• Missing base case in recursion