Recursion on Arrays and Strings in DSA Go - Execution Trace

Concept Flow - Recursion on Arrays and Strings

Start with full array/string

↓

Check base case: empty array/string?

Yes→Return base result

No↓

Process first element

↓

Call recursion on rest of array/string

↓

Combine first element with recursive result

↓

Return combined result

Recursion breaks the array or string into smaller parts, processes one element, then calls itself on the rest until it reaches the base case.

Execution Sample

DSA Go

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

This code sums all elements of an integer array recursively by adding the first element to the sum of the rest.

Execution Table

Step	Operation	Array State	Recursive Call Argument	Return Value	Visual State
1	Call sumArray([1,2,3])	[1,2,3]	[1,2,3]	?	sumArray called with [1,2,3]
2	Check base case (len=3)	[1,2,3]	[1,2,3]	No	Not base case, proceed
3	Process first element	[1,2,3]	[1,2,3]	1 + sumArray([2,3])	First element 1 taken
4	Call sumArray([2,3])	[2,3]	[2,3]	?	sumArray called with [2,3]
5	Check base case (len=2)	[2,3]	[2,3]	No	Not base case, proceed
6	Process first element	[2,3]	[2,3]	2 + sumArray([3])	First element 2 taken
7	Call sumArray([3])	[3]	[3]	?	sumArray called with [3]
8	Check base case (len=1)	[3]	[3]	No	Not base case, proceed
9	Process first element	[3]	[3]	3 + sumArray([])	First element 3 taken
10	Call sumArray([])	[]	[]	?	sumArray called with empty array
11	Check base case (len=0)	[]	[]	Yes	Base case reached, return 0
12	Return 0	[]	[]	0	Returning 0
13	Return 3 + 0	[3]	[3]	3	Returning 3
14	Return 2 + 3	[2,3]	[2,3]	5	Returning 5
15	Return 1 + 5	[1,2,3]	[1,2,3]	6	Returning 6
16	Final result	[1,2,3]	[1,2,3]	6	Sum of array is 6

💡 Recursion stops when the array is empty (base case), returning 0.

Variable Tracker

Variable	Start	After Step 4	After Step 7	After Step 10	Final
arr	[1,2,3]	[2,3]	[3]	[]	[]
Return Value	?	?	?	0	6

Key Moments - 3 Insights

Why does the recursion stop when the array is empty?

Because the base case in step 11 checks if the array length is zero and returns 0, stopping further recursive calls.

How is the sum built back up after reaching the base case?

After step 11 returns 0, each previous call adds its first element to the returned value (steps 13, 14, 15), building the total sum.

Why do we call sumArray with arr[1:] instead of arr?

Calling with arr[1:] (the rest of the array) reduces the problem size each time, moving towards the base case as shown in steps 4, 7, and 10.

Visual Quiz - 3 Questions

Look at the execution_table at step 10, what is the argument passed to sumArray?

A [] (empty array)

B [3]

C [2,3]

D [1,2,3]

💡 Hint

Check the 'Recursive Call Argument' column at step 10.

At which step does the recursion reach the base case?

A Step 9

B Step 11

C Step 13

D Step 15

💡 Hint

Look for the step where 'Check base case' is 'Yes' in the execution_table.

If the array was [4,5], what would be the return value at step 15?

A 6

B 0

C 9

D 4

💡 Hint

Sum of 4 + 5 is 9, check how return values build up in the execution_table.

Concept Snapshot

Recursion on Arrays and Strings:
- Base case: empty array/string
- Process first element
- Recursively call on rest
- Combine result and return
- Stops when base case reached
- Builds result back up step-by-step

Full Transcript

Recursion on arrays and strings works by breaking the problem into smaller parts. We check if the array or string is empty, which is the base case. If yes, we return 0. If not, we process the first element and call the same function on the rest. This continues until the base case is reached. Then, the results combine as the recursive calls return, building the final answer step-by-step. For example, summing an array adds the first element to the sum of the rest recursively until the array is empty.

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