Recursion Base Case and Recursive Case in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the base case in recursion?

The base case is the condition that stops the recursion. It prevents infinite calls by returning a simple, direct answer.

beginner

What is the recursive case in recursion?

The recursive case is where the function calls itself with a smaller or simpler input, moving toward the base case.

intermediate

Why do we need both base case and recursive case in a recursive function?

The base case stops the recursion to avoid infinite loops, and the recursive case breaks the problem into smaller parts to solve it step by step.

beginner

Look at this Go code snippet:

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

What is the base case here?

The base case is if n == 0 { return 1 }. It stops recursion when n reaches 0.

beginner

In the same factorial function, what is the recursive case?

The recursive case is return n * factorial(n-1). It calls the function itself with a smaller number.

What happens if a recursive function has no base case?

A It runs forever and causes a stack overflow

B It returns immediately

C It runs only once

D It throws a syntax error

Without a base case, the function keeps calling itself endlessly, causing a stack overflow error.

In recursion, the base case is used to:

A Create a loop

B Call the function again

C Stop the recursion

D Increase the input size

The base case stops the recursion by providing a simple answer without further calls.

Which part of recursion breaks the problem into smaller parts?

A Base case

B Recursive case

C Loop

D Condition

The recursive case calls the function itself with smaller inputs to solve the problem step by step.

In the factorial example, what is the result of factorial(0)?

A 0

B Error

C Undefined

D 1

The base case returns 1 when n is 0, so factorial(0) is 1.

What is the main risk if the recursive case does not move toward the base case?

A Infinite recursion

B Faster execution

C No output

D Syntax error

If the recursive case does not reduce the problem size, the base case is never reached, causing infinite recursion.

Explain in your own words what the base case and recursive case are in recursion.

Think about how recursion stops and how it continues.

Describe how the factorial function uses base case and recursive case to calculate the result.

Focus on what happens when n is zero and when n is greater than zero.

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