Recursion on Arrays and Strings in DSA Go - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is recursion in the context of arrays and strings?

Recursion is a way where a function calls itself to solve smaller parts of a problem, like checking each element of an array or each character of a string step-by-step until it reaches the end.

beginner

How does a base case work in recursion on arrays or strings?

The base case stops the recursion. For arrays or strings, it usually means when the index reaches the length (end) or when the string is empty, so the function stops calling itself.

intermediate

Explain how to reverse a string using recursion.

To reverse a string recursively, take the first character, call the function on the rest of the string, then add the first character at the end. Repeat until the string is empty.

beginner

What is the role of the recursive call in processing arrays?

The recursive call processes the smaller part of the array, usually by moving the index forward by one, so each call handles one element until the whole array is processed.

intermediate

Why is it important to reduce the problem size in each recursive call?

Reducing the problem size ensures the recursion moves toward the base case and eventually stops, preventing infinite loops and stack overflow errors.

What is the base case when recursively printing all elements of an array?

A When the first element is zero

B When the array is empty

C When the index is equal to the array length

D When the array has only one element

The base case is reached when the index reaches the length of the array, meaning all elements have been processed.

In recursion on strings, what does the function usually do after processing the first character?

A Calls itself with the rest of the string

B Returns immediately

C Processes the last character next

D Skips the next character

The function calls itself with the remaining substring after the first character to process the string step-by-step.

Which of these is NOT a good base case for recursion on arrays?

A Index is zero

B Array is empty

C Index is negative

D Index equals array length

Index zero is usually the start, not a stopping condition, so it is not a good base case.

What happens if a recursive function on arrays does not reduce the index?

A It will reverse the array

B It will finish quickly

C It will skip elements

D It will run forever or crash

Without reducing the index, the base case is never reached, causing infinite recursion and possible crash.

How can recursion help in checking if a string is a palindrome?

A By sorting the string

B By comparing first and last characters and calling itself on the middle substring

C By counting characters only once

D By reversing the string iteratively

Recursion compares the first and last characters and then checks the substring inside recursively.

Describe how recursion works on an array to print all its elements.

Think about stopping condition and moving forward in the array.

Explain the steps to reverse a string using recursion.

Focus on how the string is broken down and rebuilt.

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