Recursion on Arrays and Strings in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Recursive Sum of Array Elements

What is the output of the following Rust code that recursively sums elements of an array?

DSA Rust

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

fn main() {
    let numbers = [1, 2, 3, 4];
    let result = recursive_sum(&numbers, 0);
    println!("{}", result);
}

A Compilation error

B 24

C 0

D 10

💡 Hint

Think about how the function adds each element starting from index 0 until the end.

The function recursively adds each element starting from index 0. The sum is 1+2+3+4 = 10.

❓ Predict Output

intermediate

Output of Recursive String Reverse

What is the output of this Rust code that recursively reverses a string slice?

DSA Rust

fn reverse_string(s: &str) -> String {
    if s.is_empty() {
        String::new()
    } else {
        let (first, rest) = s.split_at(1);
        format!("{}{}", reverse_string(rest), first)
    }
}

fn main() {
    let text = "rust";
    let reversed = reverse_string(text);
    println!("{}", reversed);
}

A tusr

B Compilation error

C tsur

D rust

💡 Hint

The function moves the first character to the end recursively.

The function takes the first character and appends it after reversing the rest, resulting in the reversed string.

🔧 Debug

advanced

Identify the Runtime Error in Recursive Array Search

What runtime error will occur when running this Rust code that searches for a value recursively in an array?

DSA Rust

fn recursive_search(arr: &[i32], target: i32, index: usize) -> bool {
    if arr[index] == target {
        true
    } else {
        recursive_search(arr, target, index + 1)
    }
}

fn main() {
    let data = [5, 3, 7];
    let found = recursive_search(&data, 9, 0);
    println!("{}", found);
}

A Index out of bounds panic

B Stack overflow error

C Compilation error due to missing return

D No error, prints true

💡 Hint

Consider what happens when the index goes beyond the array length.

The function does not check if index is within bounds before accessing arr[index], causing panic when index exceeds array length.

🧠 Conceptual

advanced

Number of Recursive Calls in String Palindrome Check

Given a recursive function that checks if a string is a palindrome by comparing first and last characters and recursing on the substring, how many recursive calls are made for the string "level"?

DSA Rust

fn is_palindrome(s: &str) -> bool {
    if s.len() <= 1 {
        true
    } else if s.chars().next() != s.chars().rev().next() {
        false
    } else {
        is_palindrome(&s[1..s.len()-1])
    }
}

fn main() {
    let word = "level";
    let result = is_palindrome(word);
    println!("{}", result);
}

A 3

B 2

C 4

D 5

💡 Hint

Count how many times the function calls itself before reaching the base case.

The function calls itself 3 times: on "level", then "eve", then "v" (base case).

🚀 Application

expert

Output of Recursive Flattening of Nested Integer Vectors

What is the output of this Rust code that recursively flattens a nested vector of integers into a single vector?

DSA Rust

enum NestedInt {
    Int(i32),
    List(Vec<NestedInt>),
}

fn flatten(nested: &NestedInt, result: &mut Vec<i32>) {
    match nested {
        NestedInt::Int(ref value) => result.push(*value),
        NestedInt::List(ref list) => {
            for item in list {
                flatten(item, result);
            }
        }
    }
}

fn main() {
    let nested = NestedInt::List(vec![
        NestedInt::Int(1),
        NestedInt::List(vec![NestedInt::Int(2), NestedInt::Int(3)]),
        NestedInt::Int(4),
    ]);
    let mut flat = Vec::new();
    flatten(&nested, &mut flat);
    println!("{:?}", flat);
}

A [4, 3, 2, 1]

B [1, 2, 3, 4]

C [1, [2, 3], 4]

D Compilation error due to enum usage

💡 Hint

The function visits each integer in order and adds it to the result vector.

The function recursively visits each integer in the nested structure and appends it to the result vector in order.

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