Recursion on Arrays and Strings in DSA Rust - Build from Scratch

Recursion on Arrays and Strings

📖 Scenario: You are working on a simple program that uses recursion to process arrays and strings. Recursion means a function calls itself to solve smaller parts of a problem until it reaches a simple case.Imagine you have a list of numbers and a word. You want to find the sum of the numbers using recursion and also reverse the word using recursion.

🎯 Goal: Build a Rust program that uses recursion to sum all numbers in an array and reverse a string.

📋 What You'll Learn

Create an array of integers called numbers with the values [1, 2, 3, 4, 5].

Create a string called word with the value "hello".

Write a recursive function sum_array that takes a slice of integers and returns the sum of all elements.

Write a recursive function reverse_string that takes a string slice and returns a new String with characters in reverse order.

Print the sum of the array and the reversed string.

💡 Why This Matters

🌍 Real World

Recursion is used in many real-world problems like searching, sorting, and processing nested data structures such as file systems or JSON data.

💼 Career

Understanding recursion helps in writing clean and efficient code for algorithms and data processing tasks common in software development roles.

1

Create the data structures

Create an array called numbers with the values [1, 2, 3, 4, 5] and a string called word with the value "hello".

DSA Rust

// Your code here

Hint

Use let to create variables. Arrays use square brackets []. Strings can be string slices with double quotes.

2

Write the recursive sum function

Write a recursive function called sum_array that takes a slice of integers arr: &[i32] and returns an i32. It should return 0 if the slice is empty. Otherwise, return the first element plus the sum of the rest of the slice.

DSA Rust

fn main() {
    let numbers = [1, 2, 3, 4, 5];
    let word = "hello";
}

// Your code here

Hint

Check if the slice is empty with arr.is_empty(). Use arr[0] for the first element and &arr[1..] for the rest.

3

Write the recursive string reverse function

Write a recursive function called reverse_string that takes a string slice s: &str and returns a String. If the string is empty, return an empty String. Otherwise, return the last character plus the reverse of the rest of the string (all except the last character).

DSA Rust

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

// Your code here

fn main() {
    let numbers = [1, 2, 3, 4, 5];
    let word = "hello";
}

Hint

Use s.chars().last().unwrap() to get the last character. Use s.len() and last_char.len_utf8() to get the rest of the string slice.

4

Print the results

In the main function, print the sum of numbers by calling sum_array(&numbers) and print the reversed word by calling reverse_string(word). Use println! to display the results.

DSA Rust

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

fn reverse_string(s: &str) -> String {
    if s.is_empty() {
        String::new()
    } else {
        let last_char = s.chars().last().unwrap();
        let rest = &s[..s.len() - last_char.len_utf8()];
        format!("{}{}", last_char, reverse_string(rest))
    }
}

fn main() {
    let numbers = [1, 2, 3, 4, 5];
    let word = "hello";

    // Your code here
}

Hint

Use println!("Sum of numbers: {}", sum_array(&numbers)) and println!("Reversed word: {}", reverse_string(word)).

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