Recursion on Arrays and Strings in DSA Rust

Mental Model

Recursion solves a problem by breaking it into smaller versions of itself until it reaches the simplest case.

Analogy: Like peeling an onion layer by layer until you reach the core, recursion processes arrays or strings one element at a time until nothing is left.

array: [1, 2, 3, 4, 5]
indexes:  0  1  2  3  4

string: "hello"
indexes:  h  e  l  l  o
          0  1  2  3  4

Recursion starts at index 0 and moves forward ->

Dry Run Walkthrough

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

Goal: Calculate the sum of all elements by breaking the problem into smaller parts

Step 1: Start at index 0, call recursion for sum of elements from index 0

array: [1, 2, 3]
current index: 0

Why: We begin summing from the first element

Step 2: Recursion calls itself for sum starting at index 1

array: [1, 2, 3]
current index: 1

Why: We reduce the problem by moving to the next element

Step 3: Recursion calls itself for sum starting at index 2

array: [1, 2, 3]
current index: 2

Why: Keep breaking down until last element

Step 4: Recursion calls itself for sum starting at index 3 (beyond last index), base case reached

array: [1, 2, 3]
current index: 3 (end)

Why: Base case means no elements left, return 0

Step 5: Return 0 from base case, add element at index 2 (3) to 0 = 3

sum so far: 3

Why: Start adding back up the call stack

Step 6: Return sum 3 to previous call, add element at index 1 (2) to 3 = 5

sum so far: 5

Why: Combine current element with sum of rest

Step 7: Return sum 5 to first call, add element at index 0 (1) to 5 = 6

sum so far: 6

Why: Final sum includes all elements

Result:

Final sum = 6

Annotated Code

DSA Rust

fn recursive_sum(arr: &[i32], index: usize) -> i32 {
    if index == arr.len() {
        return 0; // base case: no elements left
    }
    // add current element to sum of rest
    arr[index] + recursive_sum(arr, index + 1)
}

fn main() {
    let arr = [1, 2, 3];
    let result = recursive_sum(&arr, 0);
    println!("Sum of array elements: {}", result);
}

if index == arr.len() {

check base case: no elements left to add

return 0; // base case: no elements left

stop recursion and return 0 when past last element

arr[index] + recursive_sum(arr, index + 1)

add current element to sum of remaining elements recursively

Output

Sum of array elements: 6

Complexity Analysis

Time: O(n) because the function visits each element once

Space: O(n) due to the recursion call stack growing with each element

vs Alternative: Iterative sum uses O(1) space but recursion is easier to understand for beginners

Edge Cases

empty array

returns 0 immediately as base case is met

DSA Rust

if index == arr.len() {

array with one element

returns that element as sum

DSA Rust

arr[index] + recursive_sum(arr, index + 1)

When to Use This Pattern

When you see a problem that can be broken down into smaller similar problems on arrays or strings, use recursion to simplify the solution by handling one element at a time.

Common Mistakes

Mistake: Forgetting the base case causing infinite recursion
Fix: Always include a base case that stops recursion when the index reaches the array length

Mistake: Not advancing the index in recursive call causing repeated calls on same element
Fix: Increment the index in the recursive call to move forward

Summary

Recursion on arrays and strings breaks the problem into smaller parts by processing one element and calling itself on the rest.

Use recursion when a problem naturally reduces to the same problem on a smaller array or substring.

The key insight is to define a base case and reduce the problem size by moving the index forward each call.

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