Reputation: 109

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

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`

Upvotes: 0

Answers (3)

Angelicos Phosphoros

Reputation: 3057

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

Upvotes: 1

MEisebitt

Reputation: 142

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));
}

Upvotes: 1

Shepmaster

Reputation: 431069

Rust strings are UTF-8, which means that

A codepoint doesn't have a fixed-length
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;
        }
    }
}

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

Answers (3)

Related Questions