Recursion Concept and Call Stack Visualization in DSA Go - Execution Trace

Concept Flow - Recursion Concept and Call Stack Visualization

Start Function Call

↓

Check Base Case?

Yes→Return Base Value

No↓

Call Function Recursively

↓

Wait for Recursive Result

↓

Process Result

↓

Return Result

↓

End Function Call

Shows how a recursive function calls itself until a base case is met, then returns values back up the call stack.

Execution Sample

DSA Go

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

Calculates factorial of n by calling itself with n-1 until n is 0.

Execution Table

Step	Operation	Current n	Call Stack	Return Value	Visual Call Stack
1	Call factorial(3)	3	factorial(3)		factorial(3)
2	Check base case n==0?	3	factorial(3)		factorial(3)
3	Call factorial(2)	2	factorial(3) -> factorial(2)		factorial(3) factorial(2)
4	Check base case n==0?	2	factorial(3) -> factorial(2)		factorial(3) factorial(2)
5	Call factorial(1)	1	factorial(3) -> factorial(2) -> factorial(1)		factorial(3) factorial(2) factorial(1)
6	Check base case n==0?	1	factorial(3) -> factorial(2) -> factorial(1)		factorial(3) factorial(2) factorial(1)
7	Call factorial(0)	0	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)		factorial(3) factorial(2) factorial(1) factorial(0)
8	Check base case n==0?	0	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)	1	factorial(3) factorial(2) factorial(1) factorial(0)
9	Return 1 to factorial(1)	1	factorial(3) -> factorial(2) -> factorial(1)	1	factorial(3) factorial(2) factorial(1)
10	Calculate 1 * 1	1	factorial(3) -> factorial(2) -> factorial(1)	1	factorial(3) factorial(2) factorial(1)
11	Return 1 to factorial(2)	2	factorial(3) -> factorial(2)	1	factorial(3) factorial(2)
12	Calculate 2 * 1	2	factorial(3) -> factorial(2)	2	factorial(3) factorial(2)
13	Return 2 to factorial(3)	3	factorial(3)	2	factorial(3)
14	Calculate 3 * 2	3	factorial(3)	6	factorial(3)
15	Return 6 to main			6

💡 Recursion ends when base case n==0 is reached and returns 1, then results return back up the call stack.

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
n	3	2	1	0	1	2	3	6
Call Stack	factorial(3)	factorial(3)->factorial(2)	factorial(3)->factorial(2)->factorial(1)	factorial(3)->factorial(2)->factorial(1)->factorial(0)	factorial(3)->factorial(2)->factorial(1)	factorial(3)->factorial(2)	factorial(3)
Return Value				1	1	1	2	6

Key Moments - 3 Insights

Why does the function keep calling itself instead of stopping immediately?

Because the base case (n == 0) is not met yet, so the function calls itself with a smaller n (see steps 1-7 in execution_table).

How does the function know when to stop calling itself?

When n equals 0, the base case is reached and the function returns 1 without further recursive calls (see step 8).

How are the return values combined back up the call stack?

Each call waits for the recursive call to return, then multiplies n by the returned value before returning itself (see steps 9-15).

Visual Quiz - 3 Questions

Look at the execution_table at step 7, what is the call stack state?

A factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)

B factorial(3) -> factorial(2) -> factorial(1)

C factorial(3) -> factorial(2)

D factorial(3)

💡 Hint

Check the 'Call Stack' column at step 7 in the execution_table.

At which step does the base case return value 1 first appear?

A Step 6

B Step 10

C Step 8

D Step 12

💡 Hint

Look for the first 'Return Value' of 1 in the execution_table.

If the initial call was factorial(2) instead of factorial(3), how many calls would be on the stack at the deepest point?

A 2

B 3

C 4

D 1

💡 Hint

Count how many calls are stacked for factorial(3) at the deepest point and subtract one for factorial(2).

Concept Snapshot

Recursion calls the same function with smaller inputs until a base case stops it.
Each call waits for the next to return a value.
The call stack grows with each call and shrinks as returns happen.
Base case is essential to avoid infinite recursion.
Return values combine as calls return back up the stack.

Full Transcript

Recursion is a process where a function calls itself with smaller inputs until it reaches a base case. In the factorial example, factorial(3) calls factorial(2), which calls factorial(1), which calls factorial(0). When factorial(0) returns 1, each previous call multiplies its n by the returned value and returns that result. The call stack grows as calls are made and shrinks as they return. This visualization shows each step, the call stack state, and how return values propagate back up.

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