Recursion on Arrays and Strings in DSA Go

Mental Model

Recursion solves a big problem by breaking it into smaller, similar problems until it becomes simple enough to solve directly.

Analogy: Like peeling an onion layer by layer until you reach the core, recursion breaks down arrays or strings step by step until only one element or an empty string remains.

array: [1, 2, 3, 4, 5]
string: "hello"

Recursion call stack:
call 1 -> call 2 -> call 3 -> ... -> base case

Each call handles one element and passes the rest forward.

Dry Run Walkthrough

Input: array: [1, 2, 3], sum all elements using recursion

Goal: Find the total sum of all elements in the array using recursion

Step 1: call sum on [1, 2, 3]

[1, 2, 3]

Why: Start with the full array to sum all elements

Step 2: sum first element 1 + sum of rest [2, 3]

[2, 3]

Why: Break problem into first element plus sum of remaining elements

Step 3: sum first element 2 + sum of rest [3]

[3]

Why: Continue breaking down until only one element remains

Step 4: sum first element 3 + sum of rest []

[]

Why: Base case reached: empty array sums to 0

Step 5: return 0 for empty array

[]

Why: Base case returns 0 to stop recursion

Step 6: return 3 + 0 = 3

[3]

Why: Add last element to base case result

Step 7: return 2 + 3 = 5

[2, 3]

Why: Add current element to sum of rest

Step 8: return 1 + 5 = 6

[1, 2, 3]

Why: Add first element to sum of rest to get total

Result:

Final sum: 6

Annotated Code

DSA Go

package main

import "fmt"

// sumArray recursively sums elements of an integer array
func sumArray(arr []int) int {
    if len(arr) == 0 {
        return 0 // base case: empty array sums to 0
    }
    // sum first element plus sum of rest
    return arr[0] + sumArray(arr[1:])
}

func main() {
    arr := []int{1, 2, 3}
    result := sumArray(arr)
    fmt.Println("Sum of array:", result)
}

if len(arr) == 0 {

check base case: stop recursion when array is empty

return 0 // base case: empty array sums to 0

return 0 to end recursion

return arr[0] + sumArray(arr[1:])

add first element to recursive sum of remaining elements

Output

Sum of array: 6

Complexity Analysis

Time: O(n) because the function calls itself once per element in the array

Space: O(n) due to the recursion call stack growing with the number of elements

vs Alternative: Iterative approach uses O(1) space but recursion is simpler to write and understand for beginners

Edge Cases

empty array

returns 0 immediately without further calls

DSA Go

if len(arr) == 0 {

single element array

returns that element as sum directly

DSA Go

return arr[0] + sumArray(arr[1:])

When to Use This Pattern

When you see a problem asking to process arrays or strings step-by-step and combine results, think of recursion to break it down into smaller similar problems.

Common Mistakes

Mistake: Forgetting the base case causes infinite recursion and program crash
Fix: Always include a base case that stops recursion, like empty array check

Mistake: Not reducing the problem size in recursive call leads to infinite loop
Fix: Make sure each recursive call works on a smaller part, e.g., arr[1:] instead of arr

Summary

Recursion on arrays and strings breaks the problem into smaller parts until simple to solve.

Use recursion when you want to process elements one by one and combine results naturally.

The key is the base case and reducing problem size each call to avoid infinite loops.

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