How to reverse a Rust String in-place using recursion?

Question

When reversing a String using recursion, I found it difficult to proceed parts of the String to the next because a slice is the &str type not a String.

This doesn't run:

fn reverse_string(s: &mut String) {
    if s.is_empty() {
        return;
    }
    // how to pass a correct parameter?
    reverse_string(&mut s[1..]);
    s.push(s.chars().nth(0).unwrap());
    s.remove(0);
}

error[E0308]: mismatched types
 --> src/lib.rs:6:20
  |
6 |     reverse_string(&mut s[1..]);
  |                    ^^^^^^^^^^^ expected struct `String`, found `str`
  |
  = note: expected mutable reference `&mut String`
             found mutable reference `&mut str`

Answer 1

Rust strings are UTF-8, which means that

1. A codepoint doesn't have a fixed-length
2. There's no one definition of what unit should be swapped.

If you want to only swap the characters of an ASCII string, this works:

use std::mem;

fn reverse_string_ascii(s: &mut str) {
    if !s.is_ascii() {
        return;
    }

    // Safety: We have checked that the string is ASCII,
    // so it's fine to treat it as a slice of bytes.
    unsafe {
        fn rev(b: &mut [u8]) {
            match b {
                [] => {}
                [_] => {}
                [h, rest @ .., t] => {
                    mem::swap(h, t);
                    rev(rest)
                }
            }
        }

        rev(s.as_bytes_mut());
    }
}

fn main() {
    let mut s = String::from("hello");
    reverse_string_ascii(&mut s);
    println!("{}", s);
}

There's no real reason to use recursion here though, iteration is better:

let mut todo = s.as_bytes_mut();
loop {
    match todo {
        [] => break,
        [_] => break,
        [h, rest @ .., t] => {
            mem::swap(h, t);
            todo = rest;
        }
    }
}

See also:

• Why is capitalizing the first letter of a string so convoluted in Rust?
• Reversing a string in Rust

Answer 2

Slices of the String datatype are of the datatype &str, therefore your program does not compile and the compiler also states that he expected a String but got a str. You could either try to convert the datatype but then you might have to write your program differently.

I am not sure why you are trying to do it with recursion but I'm sure you have a reason for that ;)

I made a working demonstration of how I would naively do it without working with slices but only String and char:

fn rec_rev_str(mut s: String) -> String {
    if s.is_empty() {
        s
    } else {
        let removed_char = s.remove(0);
        let mut s = rec_rev_str(s);
        s.push(removed_char);
        s
    }
}

fn main() {
    let s = String::from("A test String :)");
    println!("{}", rec_rev_str(s));
}

Answer 3

I would write more effective version than suggested above. My version has O(n) complexity. It doesn't allocate if string is ASCII but still need it if string is unicode.

There are possibility for other improvements though, for example, you can rid allocation if all chars in string have same length in utf8 form (but don't forget about alignment doing this).

Also, I made function accept &mut str because it is better since it allows wider range of input (e.g. reverse only substring).

You can see how much things need to be considered when working with unicode in unsafe Rust in comments.

fn reverse_str(s: &mut str){
    
    fn reverse_slice<T: Copy>(slice: &mut [T]){
        let slice_len = slice.len();
        if slice_len < 2{
            return;
        }
        slice.swap(0, slice_len-1);
        reverse_slice(&mut slice[1..slice_len-1]);
    }
    
    if s.is_ascii(){
        // Simple case: can reverse inplace
        unsafe{
            // Safety: string is ASCII
            reverse_slice(s.as_bytes_mut());
        }
    }
    else{
        // complex case: we need to work with unicode
        // Need to allocate, unfortunately
        let mut chars: Vec<char> = s.chars().collect();
        reverse_slice(&mut chars);
        unsafe {
            // Safety: We write same chars -> we have same length
            // Safety: We write correct UTF8 symbol by symbol
            // Safety: There are not possible panics in this unsafe block
            let mut bytes = s.as_bytes_mut();
            for c in chars{
                let bytes_written = c.encode_utf8(bytes).len();
                bytes = &mut bytes[bytes_written..]
            }
        }
    }
}

fn main(){
    // ASCII
    let mut s = "Hello".to_string();
    reverse_str(&mut s);
    println!("{}", s);
    
    // Unicode
    let mut s = "Авокадо 126".to_string();
    reverse_str(&mut s);
    println!("{}", s);
    
    // Substring
    let mut s = "Hello world".to_string();
    reverse_str(&mut s[6..]);
    println!("{}", s);
}

Output:

olleH
621 одаковА
Hello dlrow

Also, LLVM successfully tail-optimizes this recursion: https://rust.godbolt.org/z/95sqfM