Recursion vs Iteration When Each Wins in DSA Go - 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

The flow shows choosing between recursion and iteration to solve a problem, then applying the chosen method step-by-step until the final result.

Execution Sample

DSA Go

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

func factorialIter(n int) int {
  result := 1
  for i := 2; i <= n; i++ {
    result *= i
  }
  return result
}

This code calculates factorial of n using recursion and iteration.

Execution Table

Step	Operation	Call Stack / Loop Variable	Action	Result / Partial Result	Visual State
1	Call factorialRec(3)	Stack: factorialRec(3)	Check if n <= 1 (3 <= 1?)	False	Stack: [3]
2	Call factorialRec(2)	Stack: factorialRec(3) -> factorialRec(2)	Check if n <= 1 (2 <= 1?)	False	Stack: [3,2]
3	Call factorialRec(1)	Stack: factorialRec(3) -> factorialRec(2) -> factorialRec(1)	Check if n <= 1 (1 <= 1?)	True	Stack: [3,2,1]
4	Return 1 from factorialRec(1)	Stack unwind	Return 1	1	Stack: [3,2]
5	Return 2 * 1 from factorialRec(2)	Stack unwind	Calculate 2 * 1	2	Stack: [3]
6	Return 3 * 2 from factorialRec(3)	Stack unwind	Calculate 3 * 2	6	Stack: []
7	Call factorialIter(3)	Loop i=2	Initialize result=1	result=1	result=1
8	Loop i=2	Loop i=2	result = 1 * 2	result=2	result=2
9	Loop i=3	Loop i=3	result = 2 * 3	result=6	result=6
10	Loop ends i=4 > 3	Loop ends	Return result	6	result=6
11	End	-	-	-	-

💡 Recursion ends when base case n <= 1 is true; iteration ends when loop variable exceeds 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	After Step 9	After Step 10	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	4 (exit)	-	-
result (iteration)	1	1	1	1	1	1	1	2	6	6	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. The execution_table rows 1-3 show recursion calls until n=1, then it stops and returns values back.

Why does iteration use a loop variable i starting from 2?

Because factorial multiplies numbers from 1 to n, starting from 2 avoids multiplying by 1 unnecessarily. The execution_table rows 7-9 show i increasing and result updating.

How does the call stack change during recursion?

The call stack grows with each recursive call (rows 1-3) and shrinks as functions return (rows 4-6), shown in the Call Stack column.

Visual Quiz - 3 Questions

Look at the execution_table at Step 3, what is the call stack?

A factorialRec(3) -> factorialRec(2) -> factorialRec(1)

B factorialRec(3) -> factorialRec(1)

C factorialRec(1)

D empty

💡 Hint

Check the 'Call Stack / Loop Variable' column at Step 3 in execution_table.

At which step does the iteration loop end?

A Step 8

B Step 9

C Step 10

D Step 6

💡 Hint

Look at the 'Operation' and 'Loop Variable' columns in execution_table for iteration steps.

If the base case in recursion was missing, what would happen?

A Recursion would stop immediately

B Recursion would run forever causing a stack overflow

C Iteration would run instead

D Result would be zero

💡 Hint

Refer to key_moments about the importance of the base case and execution_table recursion steps.

Concept Snapshot

Recursion vs Iteration When Each Wins:
- Recursion solves problems by calling itself with smaller inputs.
- Iteration uses loops to repeat steps until a condition is met.
- Use recursion when problem naturally divides into similar subproblems.
- Use iteration for simple repeated steps with less memory overhead.
- Recursion needs a base case to stop; iteration needs a loop condition.
- Both can solve factorial; recursion uses call stack, iteration uses variables.

Full Transcript

This lesson compares recursion and iteration by tracing factorial calculation in Go. Recursion calls itself with smaller n until base case n <= 1, then returns results back up the call stack. Iteration uses a loop variable i from 2 to n, multiplying result each time. The execution table shows each step, call stack changes, and variable updates. Key moments explain why recursion needs a base case and how the call stack grows and shrinks. Visual quiz questions test understanding of call stack, loop end, and base case importance. The concept snapshot summarizes when to use recursion or iteration and their key differences.

Practice

1. Which situation 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 calls

C. When you need to use less memory

D. When the problem has a fixed number of steps

Solution

1. Step 1: Understand recursion use case

   Recursion works well when a problem can be broken down into smaller similar problems, like factorial or tree traversal.

2. Step 2: Compare with iteration

   Iteration is better for fixed steps or simple loops, but recursion shines in divide-and-conquer problems.

3. Final Answer:

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

4. Quick Check:

   Recursion = divide and conquer [OK]

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

Common Mistakes:

• Thinking recursion always uses less memory
• Believing iteration is always faster
• Confusing fixed steps with recursive breakdown

2. Which of the following is the correct syntax for a recursive function in Go?

easy

A. func factorial(n int) int { if n == 0 { return 0 } return n * factorial(n-1) }

B. func factorial(n int) { if n == 0 { return 1 } return n * factorial(n-1) }

C. func factorial(n int) int { for n > 0 { return n * factorial(n-1) } return 1 }

D. func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) }

Solution

1. Step 1: Check function signature and return type

   func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } correctly defines factorial with int input and int return type.

2. Step 2: Verify base case and recursive call

   func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } returns 1 when n is 0 and calls factorial(n-1) correctly.

3. Final Answer:

   func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } -> Option D

4. Quick Check:

   Correct recursion syntax = func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } [OK]

Hint: Look for correct return type and base case in recursion [OK]

Common Mistakes:

• Missing return type in function signature
• Incorrect base case return value
• Using loop inside recursive function incorrectly

3. What is the output of the following Go code?

import "fmt"

func sum(n int) int {
    if n == 0 {
        return 0
    }
    return n + sum(n-1)
}

func main() {
    fmt.Println(sum(3))
}

medium

A. Error

B. 6

C. 0

D. 3

Solution

1. Step 1: Trace recursive calls for sum(3)

   sum(3) = 3 + sum(2), sum(2) = 2 + sum(1), sum(1) = 1 + sum(0), sum(0) = 0.

2. Step 2: Calculate total sum

   sum(3) = 3 + 2 + 1 + 0 = 6.

3. Final Answer:

   6 -> Option B

4. Quick Check:

   Sum 1 to 3 = 6 [OK]

Hint: Add numbers down to zero recursively [OK]

Common Mistakes:

• Forgetting base case returns 0
• Adding instead of subtracting in recursion
• Expecting output 3 instead of sum

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

func factorial(n int) int {
    result := 1
    for i := 1; i <= n; i++ {
        result = result + i
    }
    return result
}

medium

A. Initialize result to 0 instead of 1

B. Change loop to decrement i

C. Change '+' to '*' in result update

D. Add base case for n == 0

Solution

1. Step 1: Analyze the loop operation

   The loop adds i to result instead of multiplying, so it calculates sum not factorial.

2. Step 2: Fix the operation to multiplication

   Change 'result = result + i' to 'result = result * i' to compute factorial correctly.

3. Final Answer:

   Change '+' to '*' in result update -> Option C

4. Quick Check:

   Factorial uses multiplication, not addition [OK]

Hint: Factorial multiplies all numbers, not adds [OK]

Common Mistakes:

• Using addition instead of multiplication
• Not initializing result to 1
• Looping backwards unnecessarily

5. You want to process a large tree structure with unknown depth. Which approach is better and why?

Options:
A) Use iteration with an explicit stack to avoid stack overflow.
B) Use recursion for simplicity but risk stack overflow.
C) Use recursion with tail call optimization to save memory.
D) Use iteration with multiple nested loops for clarity.

hard

A. Use iteration with an explicit stack to avoid stack overflow.

B. Use recursion for simplicity but risk stack overflow.

C. Use recursion with tail call optimization to save memory.

D. Use iteration with multiple nested loops for clarity.

Solution

1. Step 1: Understand recursion limits on large unknown depth

   Recursion can cause stack overflow if the tree is very deep because each call uses stack memory.

2. Step 2: Use iteration with explicit stack to control memory

   Iteration with a manual stack simulates recursion but avoids system stack overflow, making it safer for large trees.

3. Final Answer:

   Use iteration with an explicit stack to avoid stack overflow. -> Option A

4. Quick Check:

   Iteration + explicit stack = safe deep tree traversal [OK]

Hint: Use iteration with stack to handle deep recursion safely [OK]

Common Mistakes:

• Assuming recursion always safe for deep trees
• Believing Go supports tail call optimization
• Using nested loops for unknown depth structures