Recursion Concept and Call Stack Visualization in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to make the function call itself recursively.

DSA Go

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

Drag options to blanks, or click blank then click option'

An-1

Bn+1

C0

D1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 causes infinite recursion.

Using 0 or 1 directly breaks the recursive pattern.

The recursive call must reduce the problem size by 1 each time, so we use n-1.

2fill in blank

medium

Complete the code to correctly calculate the sum of numbers from 1 to n using recursion.

DSA Go

func sumToN(n int) int {
    if n == 0 {
        return 0
    }
    return n + sumToN([1])
}

Drag options to blanks, or click blank then click option'

A1

Bn+1

C0

Dn-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 causes infinite recursion.

Returning 1 instead of 0 in base case changes the sum.

The function calls itself with n-1 to add all numbers down to 0.

3fill in blank

hard

Fix the error in the recursive Fibonacci function to avoid infinite recursion.

DSA Go

func fibonacci(n int) int {
    if n == 0 {
        return 0
    } else if n == 1 {
        return 1
    }
    return fibonacci([1]) + fibonacci(n-2)
}

Drag options to blanks, or click blank then click option'

An+1

Bn-1

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 causes infinite recursion.

Using 1 or 0 directly breaks the Fibonacci sequence.

The function must call fibonacci with n-1 and n-2 to correctly compute Fibonacci numbers.

4fill in blank

hard

Fill both blanks to create a recursive function that counts down from n to 1.

DSA Go

func countdown(n int) {
    if n == 0 {
        return
    }
    fmt.Println(n)
    countdown([1])
    fmt.Println([2])
}

Drag options to blanks, or click blank then click option'

An-1

Bn+1

Cn

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using n+1 causes infinite recursion.

Printing n-1 instead of n after recursion changes output.

The function calls itself with n-1 to count down, and prints n after the recursive call to show the call stack unwinding.

5fill in blank

hard

Fill all three blanks to create a recursive function that reverses a string.

DSA Go

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

Drag options to blanks, or click blank then click option'

A[1:]

B[0]

C[:1]

D[-1]

Attempts:

3 left

💡 Hint

Common Mistakes

Using [:1] in recursive call instead of [1:] causes infinite recursion.

Using [-1] is invalid in Go and causes error.

The function calls itself with the substring from index 1 onward (s[1:]), then adds the first character (s[0]) at the end.

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