Recursion Base Case and Recursive Case in DSA Go

Mental Model

Recursion solves a problem by calling itself with smaller parts until it reaches a simple case it can answer directly.

Analogy: Imagine folding a big paper until it becomes small enough to hold easily; the base case is when the paper is small enough to stop folding.

problem(n) -> problem(n-1) -> problem(n-2) -> ... -> base_case
↑                         ↑
recursive calls            stopping point

Dry Run Walkthrough

Input: Calculate factorial of 3 using recursion

Goal: Find 3! = 3 x 2 x 1 by breaking it down recursively

Step 1: Call factorial(3), not base case, so call factorial(2)

factorial(3) -> factorial(2) ↑

Why: We reduce the problem to a smaller one to solve it step by step

Step 2: Call factorial(2), not base case, so call factorial(1)

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

Why: Keep breaking down until we reach the simplest case

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

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

Why: Base case stops recursion and provides a direct answer

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

factorial(3) -> factorial(2) = 2

Why: Combine smaller answers to build the bigger answer

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

factorial(3) = 6

Why: Final answer is built by combining all smaller results

Result:

factorial(3) = 6

Annotated Code

DSA Go

package main

import "fmt"

// factorial calculates n! recursively
func factorial(n int) int {
    if n == 1 { // base case: factorial(1) = 1
        return 1
    }
    // recursive case: n * factorial(n-1)
    return n * factorial(n-1)
}

func main() {
    result := factorial(3)
    fmt.Printf("factorial(3) = %d\n", result)
}

if n == 1 { // base case: factorial(1) = 1

stop recursion when n is 1, return 1 directly

return n * factorial(n-1)

call factorial with smaller n and multiply result by current n

Output

factorial(3) = 6

Complexity Analysis

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

Space: O(n) due to the call stack holding n recursive calls before unwinding

vs Alternative: Iterative approach uses a loop and constant space, recursion is simpler but uses more memory

Edge Cases

n = 1 (smallest input)

Returns 1 immediately without further calls

DSA Go

if n == 1 { // base case: factorial(1) = 1

n = 0 (not handled in code)

No base case for 0, would cause infinite recursion or error

DSA Go

if n == 1 { // base case: factorial(1) = 1

When to Use This Pattern

When a problem can be broken into smaller similar problems and has a simple stopping point, use recursion with base and recursive cases.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and stack overflow
Fix: Always include a base case that stops recursion

Mistake: Base case returns wrong value, leading to incorrect results
Fix: Ensure base case returns the correct simple answer

Summary

Recursion solves problems by calling itself with smaller inputs until a base case stops it.

Use recursion when a problem naturally breaks down into smaller similar problems.

The base case is the key to stopping recursion and preventing infinite loops.

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