Recursion vs Iteration When Each Wins in DSA Go - Build Both Approaches

Recursion vs Iteration: When Each Wins

📖 Scenario: Imagine you are helping a friend organize a list of tasks. Some tasks are simple and can be done step-by-step (iteration). Others are like nested tasks, where one task contains smaller tasks inside it (recursion).Understanding when to use step-by-step loops or when to use nested calls helps you solve problems efficiently.

🎯 Goal: You will create a simple program in Go that shows how to calculate the factorial of a number using both recursion and iteration. You will see how each method works and when each is useful.

📋 What You'll Learn

Create a variable to hold the number to calculate factorial for

Create a variable to hold the result of factorial using iteration

Create a recursive function to calculate factorial

Print both results to compare

💡 Why This Matters

🌍 Real World

Factorials are used in math, statistics, and computer science to count combinations and arrangements.

💼 Career

Understanding recursion and iteration helps in writing efficient code and solving complex problems in software development.

1

Set up the number to calculate factorial

Create a variable called number and set it to 5.

DSA Go

# Create a variable called number and set it to 5
// Your code here

Hint

Use number := 5 to create and set the variable.

2

Calculate factorial using iteration

Create a variable called factorialIter and set it to 1. Use a for loop with variable i from 1 to number to multiply factorialIter by i in each step.

DSA Go

package main

func main() {
    number := 5
    // Create factorialIter and calculate factorial using iteration
    // Your code here
}

Hint

Start with factorialIter := 1. Use a for loop from 1 to number and multiply.

3

Create a recursive function to calculate factorial

Create a function called factorialRec that takes an int parameter n and returns an int. If n is 0 or 1, return 1. Otherwise, return n * factorialRec(n-1). Then create a variable called factorialRecResult and set it to factorialRec(number).

DSA Go

package main

import "fmt"

func main() {
    number := 5
    factorialIter := 1
    for i := 1; i <= number; i++ {
        factorialIter *= i
    }
    // Create factorialRec function and calculate factorialRecResult
    // Your code here
}

Hint

Define factorialRec with base case for 0 or 1 returning 1, else recursive call. Then call it in main.

4

Print both factorial results

Use fmt.Println to print "Factorial using iteration:" followed by factorialIter. Then print "Factorial using recursion:" followed by factorialRecResult.

DSA Go

package main

import "fmt"

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

func main() {
    number := 5
    factorialIter := 1
    for i := 1; i <= number; i++ {
        factorialIter *= i
    }
    factorialRecResult := factorialRec(number)
    // Print both factorial results
    // Your code here
}

Hint

Use fmt.Println twice to print the labels and results.

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