Recursion on Arrays and Strings in DSA Rust - Execution Trace

Concept Flow - Recursion on Arrays and Strings

Start with full array/string

↓

Check base case: empty or one element?

Yes→Return base result

No↓

Process one element or split

↓

Recursive call on smaller array/string

↓

Combine current result with recursive call result

↓

Return combined result

Recursion breaks the array or string into smaller parts, solves the smallest part, then combines results back up.

Execution Sample

DSA Rust

fn sum_array(arr: &[i32]) -> i32 {
    if arr.is_empty() {
        0
    } else {
        arr[0] + sum_array(&arr[1..])
    }
}

This function sums all elements of an integer array using recursion by adding the first element to the sum of the rest.

Execution Table

Step	Operation	Array Slice	Action	Return Value	Visual State
1	Call sum_array	[1, 2, 3]	Check if empty: No	-	[1, 2, 3]
2	Recursive call	[2, 3]	Check if empty: No	-	[2, 3]
3	Recursive call	[3]	Check if empty: No	-	[3]
4	Recursive call	[]	Check if empty: Yes, return 0	0	[]
5	Return from step 4	[3]	Add arr[0]=3 + 0	3	[3]
6	Return from step 3	[2, 3]	Add arr[0]=2 + 3	5	[2, 3]
7	Return from step 2	[1, 2, 3]	Add arr[0]=1 + 5	6	[1, 2, 3]
8	Final return	[1, 2, 3]	Return total sum	6	[1, 2, 3]

💡 Recursion ends when array slice is empty, returning 0 as base case.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7	Final
arr	[1, 2, 3]	[1, 2, 3]	[2, 3]	[3]	[]	[3]	[2, 3]	[1, 2, 3]	[1, 2, 3]
return_value	-	-	-	-	0	3	5	6	6

Key Moments - 3 Insights

Why does the recursion stop when the array slice is empty?

Because the base case in step 4 checks if the array slice is empty and returns 0, stopping further recursive calls as shown in execution_table row 4.

How does the function combine results from recursive calls?

At each return step (rows 5-7), the function adds the first element of the current slice to the result returned by the recursive call on the smaller slice.

Why do we pass &arr[1..] in the recursive call?

Passing &arr[1..] creates a smaller slice excluding the first element, allowing recursion to process the rest of the array step by step, as seen in the array slices in execution_table.

Visual Quiz - 3 Questions

Look at the execution table, what is the return value at step 6?

A 3

B 6

C 5

D 0

💡 Hint

Check the 'Return Value' column at step 6 in the execution_table.

At which step does the base case trigger and stop recursion?

A Step 4

B Step 5

C Step 3

D Step 7

💡 Hint

Look for the step where the array slice is empty and the function returns 0.

If the input array was empty from the start, what would be the return value immediately?

A 1

B 0

C Error

D Undefined

💡 Hint

Refer to the base case in the code and execution_table step 4.

Concept Snapshot

Recursion on Arrays and Strings:
- Base case: empty or single element slice
- Recursive call on smaller slice (e.g., arr[1..])
- Combine current element with recursive result
- Stops when slice is empty
- Useful for sums, searches, reversals

Full Transcript

Recursion on arrays and strings works by breaking the problem into smaller parts. The function checks if the array or string slice is empty, which is the base case to stop recursion. If not empty, it processes the first element and calls itself on the rest of the slice. The results combine as the recursion unwinds. For example, summing an array adds the first element to the sum of the rest. This process repeats until the slice is empty, returning zero. The execution table shows each recursive call with the current slice and return values. Variable tracking shows how the array slice and return values change step by step. Key moments clarify why the base case stops recursion, how results combine, and why the slice shrinks each call. The quiz tests understanding of return values and base case timing. This method is a simple way to handle arrays and strings recursively.

Practice

1. What does recursion on arrays typically involve when processing elements?

easy

A. Using loops to iterate over the array elements

B. Calling the same function with a smaller part of the array until a base case is reached

C. Sorting the array before processing

D. Creating a new array for each element

Solution

1. Step 1: Understand recursion on arrays

   Recursion on arrays means the function calls itself with a smaller portion of the array each time.

2. Step 2: Identify the base case

   The recursion stops when the array is empty or has one element (base case).

3. Final Answer:

   Calling the same function with a smaller part of the array until a base case is reached -> Option B

4. Quick Check:

   Recursion = smaller input calls [OK]

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

Common Mistakes:

• Confusing recursion with loops
• Not defining a base case
• Trying to process the whole array at once

2. Which of the following is the correct Rust function signature for a recursive function that takes a slice of integers?

easy

A. fn recurse(arr: &mut [i32]) -> i32

B. fn recurse(arr: Vec<i32>) -> i32

C. fn recurse(arr: i32) -> &[i32]

D. fn recurse(arr: &[i32]) -> i32

Solution

1. Step 1: Understand Rust slice parameter

   A recursive function processing an array usually takes a slice reference like &[i32] to avoid ownership issues.

2. Step 2: Check return type

   Returning i32 is common if the function calculates a value like sum or count.

3. Final Answer:

   fn recurse(arr: &[i32]) -> i32 -> Option D

4. Quick Check:

   Slice input with reference = fn recurse(arr: &[i32]) -> i32 [OK]

Hint: Use &[i32] for read-only array slices in recursion [OK]

Common Mistakes:

• Using Vec<i32> causes ownership moves
• Returning a reference to local data
• Using mutable slice when not needed

3. What is the output of this Rust recursive function when called with arr = &[1, 2, 3]?

fn sum(arr: &[i32]) -> i32 {
    if arr.is_empty() {
        0
    } else {
        arr[0] + sum(&arr[1..])
    }
}

println!("{}", sum(arr));

medium

A. 0

B. 3

C. 6

D. Compilation error

Solution

1. Step 1: Trace recursive calls

   sum(&[1,2,3]) = 1 + sum(&[2,3]) sum(&[2,3]) = 2 + sum(&[3]) sum(&[3]) = 3 + sum(&[]) sum(&[]) = 0 (base case)

2. Step 2: Calculate total sum

   sum = 1 + 2 + 3 + 0 = 6

3. Final Answer:

   6 -> Option C

4. Quick Check:

   1+2+3 = 6 [OK]

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

Common Mistakes:

• Forgetting base case returns 0
• Adding wrong slice range
• Confusing output with length

4. Identify the error in this recursive Rust function that tries to count occurrences of a number in an array:

fn count_occurrences(arr: &[i32], target: i32) -> i32 {
    if arr.len() == 0 {
        0
    } else if arr[0] == target {
        1 + count_occurrences(&arr[1..], target)
    } else {
        count_occurrences(arr, target)
    }
}

medium

A. Infinite recursion because the else branch calls with the same array slice

B. Missing base case for empty array

C. Incorrect comparison operator in if condition

D. Function should return bool instead of i32

Solution

1. Step 1: Analyze recursive calls

   In the else branch, the function calls itself with the same array slice, causing infinite recursion.

2. Step 2: Identify fix

   The else branch should call with &arr[1..] to move forward and avoid infinite loop.

3. Final Answer:

   Infinite recursion because the else branch calls with the same array slice -> Option A

4. Quick Check:

   Same slice call causes infinite recursion [OK]

Hint: Always reduce array size in recursive calls to avoid infinite loops [OK]

Common Mistakes:

• Not reducing slice in else branch
• Confusing base case condition
• Returning wrong type

5. Given a string slice s: &str, which recursive Rust function correctly reverses the string?

hard

A. fn reverse(s: &str) -> String {
if s.len() == 0 {
String::new()
} else {
format!("{}{}", reverse(&s[1..]), &s[0..1])
}
}

B. fn reverse(s: &str) -> String {
if s.len() == 1 {
s.to_string()
} else {
format!("{}{}", &s[0..1], reverse(&s[1..]))
}
}

C. fn reverse(s: &str) -> String {
if s.is_empty() {
String::new()
} else {
format!("{}{}", &s[0..1], reverse(&s[1..]))
}
}

D. }
}
))]..1[s&(esrever ,]1..0[s& ,"}{}{"(!tamrof
{ esle }
)(wen::gnirtS
{ )(ytpme_si.s fi
{ gnirtS >- )rts& :s(esrever nf

Solution

1. Step 1: Understand string slicing and recursion

   To reverse, recursively reverse substring from index 1 onward, then append first character.

2. Step 2: Check base case and concatenation order

   Base case is empty string returning empty String. Concatenate reversed tail + first char.

3. Step 3: Compare options

   fn reverse(s: &str) -> String { if s.len() == 0 { String::new() } else { format!("{}{}", reverse(&s[1..]), &s[0..1]) } } matches correct base case and concatenation order.

4. Final Answer:

   fn reverse(s: &str) -> String { if s.len() == 0 { String::new() } else { format!("{}{}", reverse(&s[1..]), &s[0..1]) } } -> Option A

5. Quick Check:

   Reverse tail + first char = correct recursion [OK]

Hint: Reverse substring then add first char at end for string reversal [OK]

Common Mistakes:

• Appending first char before recursive call
• Wrong base case condition
• Using incorrect string slices