Recursion on Arrays and Strings in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Sum of Array Elements

What is the output of this Go code that recursively sums elements of an array?

DSA Go

package main
import "fmt"

func recursiveSum(arr []int, index int) int {
    if index == len(arr) {
        return 0
    }
    return arr[index] + recursiveSum(arr, index+1)
}

func main() {
    arr := []int{1, 2, 3, 4}
    fmt.Println(recursiveSum(arr, 0))
}

A Error: index out of range

B 24

C 0

D 10

💡 Hint

Think about how the function adds each element starting from index 0 until the end.

The function adds each element from index 0 to the end recursively. 1+2+3+4 = 10.

❓ Predict Output

intermediate

Output of Recursive String Reverse

What is the output of this Go code that recursively reverses a string?

DSA Go

package main
import "fmt"

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

func main() {
    fmt.Println(reverseString("go"))
}

A go

B oggo

C og

D Error: invalid string operation

💡 Hint

The function takes the first character and puts it at the end after reversing the rest.

The function reverses "go" to "og" by recursion.

🔧 Debug

advanced

Identify the Error in Recursive Palindrome Check

What error does this Go code produce when checking if a string is a palindrome recursively?

DSA Go

package main
import "fmt"

func isPalindrome(s string, start int, end int) bool {
    if start >= end {
        return true
    }
    if s[start] != s[end] {
        return false
    }
    return isPalindrome(s, start+1, end-1)
}

func main() {
    fmt.Println(isPalindrome("level", 0, len("level")-1))
}

A false

B panic: runtime error: index out of range

C true

D compile error: cannot compare byte and rune

💡 Hint

Check the end index passed to the function and how it is used for indexing.

The end index is set to len(s) which is out of range for indexing (max index is len(s)-1).

🧠 Conceptual

advanced

Number of Recursive Calls in Fibonacci Calculation

How many times is the recursive function called when calculating fibonacci(4) using this naive recursive code?

DSA Go

func fibonacci(n int) int {
    if n <= 1 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

A 9

B 7

C 5

D 15

💡 Hint

Draw the call tree for fibonacci(4) and count all calls including repeated ones.

The call tree has 9 calls total for fibonacci(4).

🚀 Application

expert

Output of Recursive Flattening of Nested Integer Slices

What is the output of this Go code that recursively flattens nested slices of integers?

DSA Go

package main
import "fmt"

func flatten(input interface{}) []int {
    result := []int{}
    switch v := input.(type) {
    case int:
        result = append(result, v)
    case []interface{}:
        for _, item := range v {
            result = append(result, flatten(item)...)
        }
    }
    return result
}

func main() {
    nested := []interface{}{1, []interface{}{2, 3}, 4, []interface{}{[]interface{}{5}, 6}}
    fmt.Println(flatten(nested))
}

A [1 2 3 4 5 6]

B [1 [2 3] 4 [5] 6]

C [1 2 3 4 6 5]

D panic: interface conversion: interface {} is int, not []interface {}

💡 Hint

The function recursively checks if the item is int or slice and appends accordingly.

The function collects all integers in order from nested slices into a flat slice.

Practice

1. What does a recursive function do when processing an array?

easy

A. It only processes the first element and stops

B. It loops through the array without calling itself

C. It creates a new array each time without recursion

D. It calls itself with a smaller part of the array until a base case is reached

Solution

1. Step 1: Understand recursion on arrays

   A recursive function processes an array by calling itself with a smaller portion, usually by reducing the size or moving the index.

2. Step 2: Identify the base case

   The recursion stops when the array is empty or the index reaches the end, preventing infinite calls.

3. Final Answer:

   It calls itself with a smaller part of the array until a base case is reached -> Option D

4. Quick Check:

   Recursion = smaller calls until base case [OK]

Hint: Recursion breaks problem into smaller parts until simple case [OK]

Common Mistakes:

• Thinking recursion loops without reducing problem size
• Ignoring the base case leading to infinite recursion
• Confusing recursion with iteration

2. Which of the following is the correct syntax to define a recursive function in Go that processes a string?

easy

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

B. func recurse(s string) string { for i := 0; i < len(s); i++ { return s[i] } }

C. func recurse(s string) { if len(s) == 0 { return } else { recurse(s) } }

D. func recurse(s string) string { return s + recurse(s) }

Solution

1. Step 1: Check function signature and base case

   func recurse(s string) string { if len(s) == 0 { return "" } return string(s[0]) + recurse(s[1:]) } defines a function with a base case checking if string length is zero, returning empty string.

2. Step 2: Confirm recursive call reduces problem size

   func recurse(s string) string { if len(s) == 0 { return "" } return string(s[0]) + recurse(s[1:]) } calls itself with substring s[1:], reducing string size each call, correctly building result.

3. Final Answer:

   func recurse(s string) string { if len(s) == 0 { return "" } return string(s[0]) + recurse(s[1:]) } -> Option A

4. Quick Check:

   Base case + smaller input = correct recursion [OK]

Hint: Base case + smaller input slice = correct recursion syntax [OK]

Common Mistakes:

• Missing base case causing infinite recursion
• Not reducing string size in recursive call
• Incorrect return types or missing return

3. What is the output of the following Go code?

package main
import "fmt"

func sum(arr []int) int {
    if len(arr) == 0 {
        return 0
    }
    return arr[0] + sum(arr[1:])
}

func main() {
    result := sum([]int{1, 2, 3, 4})
    fmt.Println(result)
}

medium

A. 10

B. 1234

C. 0

D. Error

Solution

1. Step 1: Understand the recursive sum function

   The function sums the first element and calls itself with the rest of the array until empty.

2. Step 2: Calculate sum step-by-step

   sum([1,2,3,4]) = 1 + sum([2,3,4]) = 1 + 2 + sum([3,4]) = 1 + 2 + 3 + sum([4]) = 1 + 2 + 3 + 4 + sum([]) = 10

3. Final Answer:

   10 -> Option A

4. Quick Check:

   Sum of 1+2+3+4 = 10 [OK]

Hint: Sum adds first element + recursive sum of rest [OK]

Common Mistakes:

• Confusing concatenation with addition
• Forgetting base case returns 0
• Misreading slice syntax arr[1:]

4. Identify the error in this recursive Go function that reverses a string:

package main
import "fmt"

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

func main() {
    fmt.Println(reverse(123))
}

medium

A. Missing base case in recursion

B. Passing an integer instead of a string to reverse

C. Incorrect string concatenation order

D. Infinite recursion due to no slice reduction

Solution

1. Step 1: Check function call in main

   The function reverse expects a string, but main calls reverse(123), an integer, causing a type error.

2. Step 2: Confirm recursion and base case are correct

   The function has a proper base case and reduces string size correctly, so no recursion error.

3. Final Answer:

   Passing an integer instead of a string to reverse -> Option B

4. Quick Check:

   Type mismatch in function argument [OK]

Hint: Check argument types match function parameters [OK]

Common Mistakes:

• Ignoring type mismatch errors
• Assuming recursion error without checking call
• Confusing string indexing with integer

5. Given a recursive function that removes all vowels from a string, which approach correctly applies recursion on strings in Go?

hard

A. Replace vowels with empty string using built-in functions only

B. Loop through string and remove vowels without recursion

C. Check first character; if vowel, skip and recurse on rest; else include and recurse

D. Call recursion without reducing string size causing infinite loop

Solution

1. Step 1: Understand recursive vowel removal

   The function should check the first character, decide to keep or skip it, then recurse on the rest of the string.

2. Step 2: Confirm recursion reduces problem size and builds result

   By slicing the string smaller each call and concatenating results, recursion correctly removes vowels.

3. Final Answer:

   Check first character; if vowel, skip and recurse on rest; else include and recurse -> Option C

4. Quick Check:

   Recursion with condition + smaller input = correct approach [OK]

Hint: Use condition + smaller substring in recursion [OK]

Common Mistakes:

• Not reducing string size causing infinite recursion
• Using loops instead of recursion
• Ignoring condition to skip vowels