Recursion vs Iteration When Each Wins in DSA Go - Trade-offs & Analysis

Mental Model

Recursion solves problems by breaking them into smaller copies of themselves, while iteration repeats steps using loops. Each works best depending on problem size and clarity.

Analogy: Imagine climbing stairs: recursion is like asking a friend to climb one step and then call another friend to climb the next, while iteration is you climbing step by step yourself in a loop.

Recursion:
main() -> func() -> func() -> func() -> base case

Iteration:
start -> loop -> loop -> loop -> end

Dry Run Walkthrough

Input: Calculate factorial of 4 using recursion and iteration

Goal: Show how recursion and iteration compute factorial and when each is better

Step 1: Recursion calls factorial(4), which calls factorial(3)

factorial(4) -> factorial(3) ↑

Why: Break problem into smaller subproblems

Step 2: Recursion calls factorial(3), which calls factorial(2)

factorial(4) -> factorial(3) -> factorial(2) ↑

Why: Keep breaking down until base case

Step 3: Recursion calls factorial(2), which calls factorial(1)

factorial(4) -> factorial(3) -> factorial(2) -> factorial(1) ↑

Why: Reach base case where factorial(1) = 1

Step 4: Recursion returns 1 for factorial(1), then factorial(2) = 2 * 1 = 2

returning up: factorial(2) = 2

Why: Combine results going back up

Step 5: Recursion returns factorial(3) = 3 * 2 = 6

returning up: factorial(3) = 6

Why: Combine results going back up

Step 6: Recursion returns factorial(4) = 4 * 6 = 24

returning up: factorial(4) = 24

Why: Final result computed

Step 7: Iteration initializes result=1 and multiplies by 1,2,3,4 in loop

result=1 -> 1*1=1 -> 1*2=2 -> 2*3=6 -> 6*4=24

Why: Calculate factorial by repeated multiplication

Result:

factorial(4) = 24

Annotated Code

DSA Go

package main

import "fmt"

// Recursive factorial function
func factorialRec(n int) int {
	if n <= 1 {
		return 1 // base case
	}
	return n * factorialRec(n-1) // recursive call
}

// Iterative factorial function
func factorialIter(n int) int {
	result := 1
	for i := 1; i <= n; i++ {
		result *= i // multiply result by i
	}
	return result
}

func main() {
	n := 4
	fmt.Printf("Recursive factorial of %d: %d\n", n, factorialRec(n))
	fmt.Printf("Iterative factorial of %d: %d\n", n, factorialIter(n))
}

if n <= 1 { return 1 }

stop recursion at base case to avoid infinite calls

return n * factorialRec(n-1)

break problem into smaller subproblem and combine result

for i := 1; i <= n; i++ { result *= i }

repeat multiplication step by step to build factorial

Output

Recursive factorial of 4: 24

Iterative factorial of 4: 24

Complexity Analysis

Time: O(n) because both recursion and iteration multiply n numbers once

Space: O(n) for recursion due to call stack, O(1) for iteration as it uses constant space

vs Alternative: Iteration uses less memory and avoids call stack overhead, recursion is simpler to write but can cause stack overflow for large n

Edge Cases

n = 0

Both return 1 as factorial of 0 is 1

DSA Go

if n <= 1 { return 1 }

n = 1

Both return 1 immediately

DSA Go

if n <= 1 { return 1 }

large n (e.g., 10000)

Recursion may cause stack overflow, iteration handles it safely

DSA Go

for i := 1; i <= n; i++ { result *= i }

When to Use This Pattern

When a problem naturally breaks into smaller similar problems, recursion is a good fit; when performance and memory are critical, iteration is preferred.

Common Mistakes

Mistake: Forgetting the base case in recursion causing infinite calls
Fix: Always include a clear base case to stop recursion

Mistake: Using recursion for very large inputs causing stack overflow
Fix: Use iteration or tail recursion optimization if supported

Summary

Recursion solves problems by calling itself with smaller inputs; iteration uses loops to repeat steps.

Use recursion when problem fits naturally into smaller subproblems and clarity is important; use iteration when memory and speed matter.

The key insight is recursion uses the call stack to remember work, iteration uses looping to repeat work without extra memory.

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