Recursion Concept and Call Stack Visualization in DSA Go - Build from Scratch

Recursion Concept and Call Stack Visualization

📖 Scenario: Imagine you want to find the factorial of a number, which means multiplying that number by every smaller number down to 1. This is like stacking boxes: to get the total height, you add the height of the top box to the height of all boxes below it. Recursion helps us solve this by calling the same process again and again with smaller numbers.

🎯 Goal: You will build a simple recursive function in Go to calculate the factorial of a number. You will see how the function calls itself and how the answers build up step by step.

📋 What You'll Learn

Create a recursive function called factorial that takes an integer n and returns an integer.

Use a base case where if n is 1, the function returns 1.

In the recursive case, the function should return n * factorial(n-1).

Call the factorial function with the value 5 and store the result in a variable called result.

Print the value of result.

💡 Why This Matters

🌍 Real World

Recursion is used in many places like calculating combinations, navigating file systems, and solving puzzles like mazes.

💼 Career

Understanding recursion helps in writing clean code for complex problems and is often asked in coding interviews.

1

Create the factorial function with base case

Write a function called factorial that takes an integer n and returns an integer. Inside the function, if n equals 1, return 1.

DSA Go

// Define the factorial function with base case
// Your code here

Hint

Start by writing the function header and the base case that stops the recursion.

2

Add the recursive case to factorial function

Inside the factorial function, after the base case, add the recursive case that returns n * factorial(n - 1).

DSA Go

package main

import "fmt"

func factorial(n int) int {
    if n == 1 {
        return 1
    }
    // Add recursive case here
    return 0
}

func main() {

}

Hint

Multiply n by the result of calling factorial with n - 1.

3

Call factorial function with 5 and store result

In the main function, call factorial with the value 5 and store the result in a variable called result.

DSA Go

package main

import "fmt"

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

func main() {
    // Call factorial(5) and store in result
    // Your code here
}

Hint

Use result := factorial(5) inside main.

4

Print the factorial result

Add a print statement in the main function to display the value of result.

DSA Go

package main

import "fmt"

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

func main() {
    result := factorial(5)
    // Print the result
    // Your code here
}

Hint

Use fmt.Println(result) to print the factorial.

Practice

1. What happens when a recursive function calls itself without a stopping condition?

easy

A. It converts into a normal loop automatically

B. It immediately returns without doing anything

C. It runs only once and stops

D. It causes an infinite loop and eventually a stack overflow error

Solution

1. Step 1: Understand recursion without base case

   Without a stopping condition, the function keeps calling itself endlessly.

2. Step 2: Effect on call stack

   Each call adds a new frame to the call stack, which grows until memory runs out causing stack overflow.

3. Final Answer:

   It causes an infinite loop and eventually a stack overflow error -> Option D

4. Quick Check:

   Missing base case = infinite recursion [OK]

Hint: Always check for a base case to stop recursion [OK]

Common Mistakes:

• Thinking recursion stops automatically
• Confusing recursion with loops
• Ignoring stack overflow possibility

2. Which of the following is the correct syntax to define a recursive function in Go that calculates factorial of n?

easy

A. func factorial(n int) int { if n == 0 { return 1 } 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 { if n == 0 { return 0 } return n * factorial(n-1) }

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

Solution

1. Step 1: Check function signature and return type

   Factorial returns an int, so function must return int type.

2. Step 2: Verify base case and recursive call

   Base case is n == 0 returning 1; recursive call multiplies n by factorial(n-1).

3. Final Answer:

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

4. Quick Check:

   Correct base case and return type = func factorial(n int) int { if n == 0 { return 1 } return n * factorial(n-1) } [OK]

Hint: Base case returns 1 for factorial(0) [OK]

Common Mistakes:

• Missing return type in function signature
• Returning 0 instead of 1 in base case
• Not returning value from function

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

func printCount(n int) {
    if n == 0 {
        return
    }
    fmt.Print(n, " ")
    printCount(n-1)
}

func main() {
    printCount(3)
}

medium

A. 3 2 1

B. 1 2 3

C. 3 2 1 0

D. 0 1 2 3

Solution

1. Step 1: Trace recursive calls and prints

   printCount(3) prints 3, then calls printCount(2), which prints 2, then calls printCount(1), which prints 1, then calls printCount(0) which returns.

2. Step 2: Confirm output sequence

   Output is printed before recursive call, so order is 3 2 1 with spaces.

3. Final Answer:

   3 2 1 -> Option A

4. Quick Check:

   Print before recursion = descending order [OK]

Hint: Print before recursion prints descending order [OK]

Common Mistakes:

• Assuming print happens after recursion
• Including 0 in output
• Confusing order of prints

4. Identify the error in this recursive Go function that calculates sum of numbers from 1 to n:

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

medium

A. Function does not return any value

B. Missing base case for n == 0

C. Recursive call uses sum(n) instead of sum(n-1), causing infinite recursion

D. Base case returns wrong value

Solution

1. Step 1: Analyze recursive call parameter

   The function calls sum(n) again without decreasing n, causing infinite recursion.

2. Step 2: Correct recursive call

   It should call sum(n-1) to reduce n and reach base case.

3. Final Answer:

   Recursive call uses sum(n) instead of sum(n-1), causing infinite recursion -> Option C

4. Quick Check:

   Recursive call must reduce n [OK]

Hint: Recursive call parameter must change to approach base case [OK]

Common Mistakes:

• Calling sum(n) again without decrement
• Wrong base case value
• Not returning result from recursion

5. Given the recursive function below, what will be the output when calling mystery(4)? Explain the call stack behavior.

func mystery(n int) int {
    if n <= 1 {
        return n
    }
    return mystery(n-1) + mystery(n-2)
}

func main() {
    fmt.Println(mystery(4))
}

hard

A. 5

B. 3

C. 7

D. 6

Solution

1. Step 1: Recognize the function as Fibonacci calculation

   The function returns n if n <= 1, else sum of mystery(n-1) and mystery(n-2), matching Fibonacci logic.

2. Step 2: Calculate mystery(4) step-by-step

   mystery(4) = mystery(3) + mystery(2) mystery(3) = mystery(2) + mystery(1) = (mystery(1)+mystery(0)) + 1 = (1+0)+1=2 mystery(2) = mystery(1) + mystery(0) = 1 + 0 = 1 Sum: 2 + 1 = 3 Wait, re-check carefully: mystery(0)=0, mystery(1)=1 mystery(2)=1+0=1 mystery(3)=1+1=2 mystery(4)=2+1=3 But options show 3 and 5, so re-check Fibonacci sequence: 0,1,1,2,3,5... Actually mystery(4) = 3

3. Final Answer:

   3 -> Option B

4. Quick Check:

   Fibonacci(4) = 3 [OK]

Hint: Recognize Fibonacci pattern in recursion [OK]

Common Mistakes:

• Miscounting Fibonacci numbers
• Confusing base cases
• Ignoring call stack repeated calls