Recursion Concept and Call Stack Visualization in DSA Go

Mental Model

Recursion is when a function calls itself to solve smaller parts of a problem until it reaches a simple case.

Analogy: Imagine a set of nested boxes where each box contains a smaller box inside it until the smallest box is empty. You open each box one by one and then close them in reverse order.

func call 1 -> func call 2 -> func call 3 -> base case reached
↑ call stack grows with each call
call stack unwinds after base case

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 using recursive calls

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

call stack: factorial(3) -> factorial(2)
waiting for factorial(2) result

Why: We break the problem into smaller part factorial(2)

Step 2: Call factorial(2), which calls factorial(1)

call stack: factorial(3) -> factorial(2) -> factorial(1)
waiting for factorial(1) result

Why: We keep breaking down until base case factorial(1)

Step 3: Call factorial(1), base case reached, return 1

call stack: factorial(3) -> factorial(2)
returned 1 from factorial(1)

Why: Base case stops recursion and starts returning values

Step 4: Return factorial(2) = 2 x 1 = 2

call stack: factorial(3)
returned 2 from factorial(2)

Why: Combine returned value with current number

Step 5: Return factorial(3) = 3 x 2 = 6

call stack empty
final result 6 returned

Why: Final result computed and recursion ends

Result:

call stack empty
final result: 6

Annotated Code

DSA Go

package main
import "fmt"

func factorial(n int) int {
    if n == 1 { // base case stops recursion
        return 1
    }
    return n * factorial(n-1) // recursive call with smaller input
}

func main() {
    result := factorial(3) // start recursion with 3
    fmt.Println(result) // print final result
}

if n == 1 { return 1 }

stop recursion at base case

return n * factorial(n-1)

recursive call with smaller input and combine result

Output

6

Complexity Analysis

Time: O(n) because the function calls itself n times until the base case

Space: O(n) due to call stack holding n function calls at most

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand for problems like factorial

Edge Cases

n = 1 (base case)

Returns 1 immediately without further calls

DSA Go

if n == 1 { return 1 }

n = 0 or negative (not handled)

Function will recurse infinitely or produce incorrect result

DSA Go

No guard for n <= 0 in code

When to Use This Pattern

When a problem can be broken into smaller similar problems and has a clear stopping point, use recursion to simplify the solution.

Common Mistakes

Mistake: Missing base case causing infinite recursion
Fix: Add a base case condition that stops recursion

Mistake: Calling recursive function with same argument causing no progress
Fix: Call recursive function with smaller or simpler argument to approach base case

Summary

Recursion solves problems by calling the same function with smaller inputs until a simple case is reached.

Use recursion when a problem naturally breaks down into smaller similar problems with a clear stopping condition.

The key insight is that each recursive call waits for the smaller problem to solve before combining results.

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