Recursion vs Iteration When Each Wins in DSA Go - Compare & Choose

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive vs Iterative Factorial

What is the output of the following Go code that calculates factorial using recursion and iteration?

DSA Go

package main
import "fmt"

func factorialRecursive(n int) int {
    if n == 0 {
        return 1
    }
    return n * factorialRecursive(n-1)
}

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

func main() {
    fmt.Println(factorialRecursive(5))
    fmt.Println(factorialIterative(5))
}

A

120
24

B

24
24

C

24
120

D

120
120

💡 Hint

Factorial of 5 is 5*4*3*2*1.

Both recursive and iterative functions correctly compute factorial of 5 as 120.

🧠 Conceptual

intermediate

When is recursion preferred over iteration?

Which scenario best explains when recursion is preferred over iteration?

A When memory usage must be minimal

B When you want to avoid function call overhead

C When the problem naturally fits a divide-and-conquer approach like tree traversal

D When the problem requires simple loops without nested calls

💡 Hint

Think about problems that break down into smaller similar problems.

Recursion is ideal for problems like tree traversal where the problem divides into similar subproblems.

❓ Predict Output

advanced

Stack Overflow Risk in Recursion

What happens when the following recursive function is called with a large input like 100000?

DSA Go

package main
import "fmt"

func countDown(n int) {
    if n == 0 {
        fmt.Println("Done")
        return
    }
    countDown(n - 1)
}

func main() {
    countDown(100000)
}

A Causes a stack overflow runtime error

B Prints "Done" without error

C Prints numbers from 100000 down to 0

D Infinite loop without termination

💡 Hint

Consider how deep recursion affects memory.

Deep recursion can exhaust the call stack causing a runtime stack overflow error.

🧠 Conceptual

advanced

Iteration Advantages Over Recursion

Which advantage is true for iteration compared to recursion?

A Iteration uses less memory because it avoids function call overhead

B Iteration is easier to implement for problems like tree traversal

C Iteration always runs faster than recursion

D Iteration can solve problems that recursion cannot

💡 Hint

Think about how function calls use memory.

Iteration uses a single loop and avoids the overhead of multiple function calls, saving memory.

🚀 Application

expert

Choosing Between Recursion and Iteration for Fibonacci

Given the task to compute the 40th Fibonacci number, which approach is best and why?

A Use simple recursion without memoization because it's straightforward

B Use iteration because it is efficient and avoids stack overflow

C Use recursion with no base case to simplify code

D Use recursion with deep nesting to test stack limits

💡 Hint

Consider performance and memory for large inputs.

Simple recursion for Fibonacci is very slow and causes many repeated calls. Iteration computes efficiently without stack issues.

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