Recursion Base Case and Recursive Case in DSA Go - Execution Trace

Concept Flow - Recursion Base Case and Recursive Case

Start Recursive Function

↓

Check Base Case?

↓

Return Base Value

↓

Process Returned Value

↓

Return Result

The function checks if it reached the simplest case (base case). If yes, it returns a value. Otherwise, it calls itself with a smaller problem and processes the result.

Execution Sample

DSA Go

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

Calculates factorial of n using recursion with base case n==0.

Execution Table

Step	Call Stack	Current n	Condition (n==0?)	Action	Return Value	Visual Call Stack
1	factorial(3)	3	False	Call factorial(2)		factorial(3)
2	factorial(3) -> factorial(2)	2	False	Call factorial(1)		factorial(3) └─ factorial(2)
3	factorial(3) -> factorial(2) -> factorial(1)	1	False	Call factorial(0)		factorial(3) └─ factorial(2) └─ factorial(1)
4	factorial(3) -> factorial(2) -> factorial(1) -> factorial(0)	0	True	Return 1	1	factorial(3) └─ factorial(2) └─ factorial(1) └─ factorial(0)
5	factorial(3) -> factorial(2) -> factorial(1)	1	False	Return 1 * 1 = 1	1	factorial(3) └─ factorial(2) └─ factorial(1)
6	factorial(3) -> factorial(2)	2	False	Return 2 * 1 = 2	2	factorial(3) └─ factorial(2)
7	factorial(3)	3	False	Return 3 * 2 = 6	6	factorial(3)
8				End recursion	6

💡 Recursion ends when base case n==0 is reached and all calls return their results.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
n	3	3	2	1	0	1	2	3	3
Return Value					1	1	2	6	6
Call Stack Depth	1	2	3	4	4	3	2	1	0

Key Moments - 3 Insights

Why does the recursion stop when n == 0?

Because the base case condition n == 0 returns a value without making further recursive calls, as shown in step 4 of the execution_table.

What happens after the base case returns a value?

Each previous call uses that returned value to compute its own result and returns it, as seen from steps 5 to 7 in the execution_table.

Why do we multiply n by factorial(n-1) in the recursive case?

Because factorial(n) is defined as n times factorial of (n-1), so each recursive call reduces the problem size until base case, shown in the action column of steps 1-7.

Visual Quiz - 3 Questions

Look at the execution_table at step 4, what is the return value when n == 0?

A n

B 1

C 0

D Undefined

💡 Hint

Check the 'Return Value' column at step 4 in the execution_table.

At which step does the recursion start to return back up the call stack?

A Step 4

B Step 2

C Step 6

D Step 8

💡 Hint

Look for the first step where the 'Action' is 'Return' and a value is given.

If we change the base case to n == 1, how would the return value at step 4 change?

A Return value would be n

B Return value would be 0

C No return value at step 4

D Return value would be 1

💡 Hint

Consider that step 4 currently returns when n == 0; changing base case shifts when returns happen.

Concept Snapshot

Recursion has two parts:
- Base Case: stops recursion by returning a value (e.g., if n == 0 return 1)
- Recursive Case: calls itself with smaller input (e.g., factorial(n-1))
Each call waits for the next to return before computing its result.
Without base case, recursion never ends.

Full Transcript

This visualization shows how recursion works using factorial as example. The function calls itself with smaller n until it reaches the base case n == 0, where it returns 1. Then each call returns its computed value back up the call stack, multiplying n by factorial(n-1). The call stack grows deeper with each call and shrinks as returns happen. The base case is essential to stop infinite recursion. The execution table tracks each call, condition check, and return value step-by-step.

Practice

1. What is the purpose of the base case in a recursive function?

easy

A. To print the result of the recursion

B. To call the function again with a smaller input

C. To increase the input size for the next call

D. To stop the recursion and prevent infinite calls

Solution

1. Step 1: Understand recursion basics

   A recursive function calls itself repeatedly until a stopping condition is met.

2. Step 2: Identify the role of base case

   The base case stops further recursive calls to avoid infinite loops.

3. Final Answer:

   To stop the recursion and prevent infinite calls -> Option D

4. Quick Check:

   Base case = stop recursion [OK]

Hint: Base case always stops recursion to avoid infinite loops [OK]

Common Mistakes:

• Confusing base case with recursive case
• Thinking base case calls function again
• Ignoring base case leads to infinite recursion

2. Which of the following is the correct syntax for a base case in Go recursion to stop when n is zero?

easy

A. if n == 0 { return 0 }

B. if n = 0 { return 0 }

C. if n != 0 { return 0 }

D. if n > 0 { return 0 }

Solution

1. Step 1: Check Go syntax for condition

   In Go, equality check uses '==' not '=' which is assignment.

2. Step 2: Identify correct base case condition

   Base case stops recursion when n equals zero, so 'if n == 0 { return 0 }' is correct.

3. Final Answer:

   if n == 0 { return 0 } -> Option A

4. Quick Check:

   Use '==' for comparison in base case [OK]

Hint: Use '==' for comparison in base case conditions [OK]

Common Mistakes:

• Using '=' instead of '==' for comparison
• Wrong condition logic for base case
• Returning wrong value in base case

3. What will be the output of this Go recursive function when called with factorial(3)?

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

medium

A. 6

B. 3

C. 0

D. 1

Solution

1. Step 1: Trace recursive calls for factorial(3)

   factorial(3) = 3 * factorial(2) factorial(2) = 2 * factorial(1) factorial(1) = 1 * factorial(0) factorial(0) = 1 (base case)

2. Step 2: Calculate return values step-by-step

   factorial(1) = 1 * 1 = 1 factorial(2) = 2 * 1 = 2 factorial(3) = 3 * 2 = 6

3. Final Answer:

   6 -> Option A

4. Quick Check:

   3! = 6 [OK]

Hint: Multiply n by factorial(n-1) until n=0 [OK]

Common Mistakes:

• Forgetting base case returns 1
• Multiplying incorrectly in recursive step
• Confusing factorial with addition

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

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

medium

A. Base case condition is incorrect

B. Function should return n * sum(n-1)

C. Recursive call does not reduce n, causing infinite recursion

D. Return statement should be outside the if block

Solution

1. Step 1: Analyze recursive call argument

   The function calls sum(n) again without reducing n, so it never reaches base case.

2. Step 2: Identify infinite recursion cause

   Recursive call must use sum(n-1) to reduce n and eventually stop at base case.

3. Final Answer:

   Recursive call does not reduce n, causing infinite recursion -> Option C

4. Quick Check:

   Recursive argument must decrease to reach base case [OK]

Hint: Recursive calls must reduce input to reach base case [OK]

Common Mistakes:

• Calling recursion with same argument
• Wrong base case value
• Misplacing return statement

5. Given this recursive Go function to reverse a string, what is the output of reverse("go")?

func reverse(s string) string {
    if len(s) == 0 {
        return ""
    }
    return reverse(s[1:]) + string(s[0])
}

hard

A. "go"

B. "og"

C. ""

D. Runtime error

Solution

1. Step 1: Trace recursive calls for reverse("go")

   reverse("go") calls reverse("o") + "g" reverse("o") calls reverse("") + "o" reverse("") returns "" (base case)

2. Step 2: Combine return values step-by-step

   reverse("") = "" reverse("o") = "" + "o" = "o" reverse("go") = "o" + "g" = "og"

3. Final Answer:

   "og" -> Option B

4. Quick Check:

   String reversed = "og" [OK]

Hint: Reverse substring then add first char at end [OK]

Common Mistakes:

• Confusing substring slicing
• Forgetting base case returns empty string
• Concatenating in wrong order