Recursion on Arrays and Strings in DSA Go - Build from Scratch

Recursion on Arrays and Strings

📖 Scenario: You are working on a simple program that uses recursion to process arrays and strings. Recursion means a function calls itself to solve smaller parts of the problem until it reaches a simple case.Imagine you want to find the sum of numbers in a list and also reverse a word using recursion.

🎯 Goal: Build a Go program that uses recursion to find the sum of an array of integers and to reverse a string.

📋 What You'll Learn

Create an integer array called numbers with the exact values: 2, 4, 6, 8, 10

Create a string variable called word with the exact value: "hello"

Write a recursive function called sumArray that takes the array and returns the sum of its elements

Write a recursive function called reverseString that takes the string and returns the reversed string

Print the sum of the array and the reversed string exactly as shown in the final output

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like searching, sorting, and processing nested data structures.

💼 Career

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

1

Create the data variables

Create an integer array called numbers with the exact values: 2, 4, 6, 8, 10. Also create a string variable called word with the exact value: "hello".

DSA Go

# Create the array called numbers and the string called word
# Your code here

Hint

Use numbers := []int{2, 4, 6, 8, 10} to create the array and word := "hello" for the string.

2

Add recursive function to sum the array

Write a recursive function called sumArray that takes a slice of integers called arr and returns the sum of its elements as an int. Use the base case when the slice is empty to return 0.

DSA Go

package main

import "fmt"

func main() {
    numbers := []int{2, 4, 6, 8, 10}
    word := "hello"
}

// Write the recursive function sumArray here
# Your code here

Hint

Check if the slice length is 0, then return 0. Otherwise, return the first element plus the sum of the rest.

3

Add recursive function to reverse the string

Write a recursive function called reverseString that takes a string called s and returns the reversed string. Use the base case when the string is empty to return an empty string.

DSA Go

package main

import "fmt"

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

// Write the recursive function reverseString here
# Your code here

func main() {
    numbers := []int{2, 4, 6, 8, 10}
    word := "hello"
}

Hint

Check if the string length is 0, then return empty string. Otherwise, call reverseString on the substring from index 1 and add the first character at the end.

4

Print the results

In the main function, print the sum of the numbers array by calling sumArray(numbers). Then print the reversed word by calling reverseString(word). Use fmt.Println to print each result on its own line.

DSA Go

package main

import "fmt"

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

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

func main() {
    numbers := []int{2, 4, 6, 8, 10}
    word := "hello"

    // Print the sum of numbers and the reversed word
    # Your code here
}

Hint

Use fmt.Println(sumArray(numbers)) and fmt.Println(reverseString(word)) to print the results.

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