Recursion Base Case and Recursive Case in DSA Go - Build from Scratch

Recursion Base Case and Recursive Case

📖 Scenario: Imagine you want to count down from a number to zero, like counting steps while walking down stairs.

🎯 Goal: You will build a simple recursive function in Go that counts down from a given number to zero, showing how recursion stops with a base case and continues with a recursive case.

📋 What You'll Learn

Create a function called countDown that takes an integer n.

Use a base case to stop recursion when n is less than 0.

Use a recursive case to call countDown with n-1.

Print the current value of n before the recursive call.

Call countDown with the starting number 3 in main.

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like navigating folders, solving puzzles, and processing tree structures.

💼 Career

Understanding recursion helps in coding interviews and solving complex problems efficiently in software development.

1

Create the main function with a call to countDown

Write a main function that calls countDown with the number 3.

DSA Go

package main

func main() {
    // Call countDown with 3
    // Your code here
}

Hint

The main function is the program's starting point. Call countDown(3) inside it.

2

Define the countDown function with a base case

Define a function called countDown that takes an integer n. Add a base case that returns immediately if n is less than 0.

DSA Go

package main

func main() {
    countDown(3)
}

// Define countDown function here
// Your code here

Hint

The base case stops the recursion. Use if n < 0 { return }.

3

Add printing and recursive call in countDown

Inside countDown, print the value of n using fmt.Println(n). Then call countDown recursively with n-1.

DSA Go

package main

import "fmt"

func main() {
    countDown(3)
}

func countDown(n int) {
    if n < 0 {
        return
    }
    // Print n
    // Call countDown with n-1
    // Your code here
}

Hint

Print n before calling countDown(n - 1) to count down step by step.

4

Run the program and print the countdown

Run the program and print the countdown from 3 to 0 using the countDown function.

DSA Go

package main

import "fmt"

func main() {
    countDown(3)
}

func countDown(n int) {
    if n < 0 {
        return
    }
    fmt.Println(n)
    countDown(n - 1)
}

// Run the program to see output
// Your code here

Hint

Run the program. It should print numbers 3, 2, 1, 0 each on a new line.

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