Pattern to convert a recursive fn to work as iter?

Hello everyone

Please consider a simple recursive function below to generate permutations of single characters in a string such as "ABCD" (which generates 4!=24 permutations).
This fn works fine but as avid Rust learner I would like to make it into Iterator so I can use next() method and Rust for loops and all other wonderful Rust iterator features.

My Question:
what is the most Rust idiomatic (and performant) way to convert this recursive fn to work ar Rust Iterator?

I understand that Rust 1.72 stable does not have a "Yield" functionality.
So perhaps there is another way to do it in Rust 1.72 ?

PS I am aware the itertools crate has the "permutations" functionality already.
I am asking this question in order to help me learn Rust.

thank you very much

// gen_str2(p, "ABCD");
fn gen_str2(perm: String, word: &str) {
    if word.len() == 0 {
        println!("result:{perm}");
    } else {
        for i in 0..word.len() {
            let mut perm2 = perm.clone();
            perm2.push(word.chars().nth(i).unwrap());
            gen_str2(perm2, format!("{}{}", &word[0..i], &word[i + 1..]).as_str());
        }
    }
}

fn main() {
    let p = String::new();
    gen_str2(p, "ABCD");
}

The usual high-level idea behind converting recursion to iteration is to make the stack explicit. Instead of using the call stack of recursive calls, you make a Vec and push onto/pop from it.

2 Likes

First, you can turn it into a bad iterator.

fn main() {
    for s in gen_str3(String::new(), "ABCD") {
        println!("{s}");
    }
}

fn gen_str3(perm: String, word: &str) -> impl Iterator<Item = String> {
    let mut perms = Vec::new();
    if word.is_empty() {
        perms.push(perm);
    } else {
        for (i, c) in word.char_indices() {
            let perm2 = format!("{perm}{c}");
            let word2 = format!("{}{}", &word[0..i], &word[i + c.len_utf8()..]);
            perms.extend(gen_str3(perm2, &word2));
        }
    }
    perms.into_iter()
}

This will let you test your iterator against something you know is correct. I've also changed this to use char_indices so that it's correct for multi-byte characters.

Then you need to recreate the stack. This means saving all values that are present whenever you make the recursive call. If I did this completely, I would have to include the for loop iterator in the stack and recreate the for loop logic, and you may need to do that for more complex recursive functions, but I've taken a shortcut and kept the for loop for simplicity. The downside of this is if you cancel the iterator early, a few strings will be created and never used. (playground)

fn gen_str4(perm: String, word: &str) -> impl Iterator<Item = String> {
    let mut stack = vec![(perm, word.to_string())];

    // This closure returns Some(None) when no value is ready yet, but the iterator should
    // continue. It returns Some(Some(_)) when a value is ready. And it returns None when
    // the iterator is done.
    std::iter::from_fn(move || -> Option<Option<String>> {
        // When the stack is empty, end the iterator
        let (perm, word) = stack.pop()?;
        // All characters are used up, return the permutation
        if word.is_empty() {
            return Some(Some(perm));
        }
        // Make bigger perms and add them to the stack
        // Reverse to match the recursive version
        for (i, c) in word.char_indices().rev() {
            let perm2 = format!("{perm}{c}");
            let word2 = format!("{}{}", &word[0..i], &word[i + c.len_utf8()..]);
            stack.push((perm2, word2));
        }
        Some(None)
    })
    // Flatten to convert the item type from Option<String> to String
    .flatten()
}
4 Likes

Also, the pattern of writing sequential code and transforming it into an iterator is accomplished by generators. Unfortunately however Rust doesn't support stable generators yet. Moreover generators don't really like recursion, you would have to Box the recursive calls, effectively replacing the call stack with a linked list.

3 Likes

Couldn't you just for x in recurse() { yield x }?

Yeah, I made the generator version and it works fine (playground)

fn gen_str5(perm: String, word: &str) -> impl Iterator<Item = String> + '_ {
    let gen = move || {
        if word.is_empty() {
            yield perm;
        } else {
            for (i, c) in word.char_indices() {
                let perm2 = format!("{perm}{c}");
                let word2 = format!("{}{}", &word[0..i], &word[i + c.len_utf8()..]);
                for perm in gen_str3(perm2, &word2) {
                    yield perm;
                }
            }
        }
    };
    std::iter::from_generator(gen)
}

Edit: actually never mind, I used the wrong function. I see what you mean. I don't know how boxing helps though.

Edit2: Okay, turns out this generator has multiple issues. I see what boxing does now.

1 Like

wonderful responses.

I am intrigued: why did you call the first iterator gen_str3 as a "Bad" iterator?

thank you

It creates all the values before even the first item is returned. This means it has all N! values in memory at once, whereas the other ones have at most N^2 values in memory at once.

1 Like

Here's the correct generator version for the future (playground)

fn gen_str5(perm: String, word: String) -> impl Iterator<Item = String> {
    let gen = move || {
        if word.is_empty() {
            yield perm;
        } else {
            let mut i = 0;
            while i < word.len() {
                let c = word[i..].chars().next().unwrap();
                let perm2 = format!("{perm}{c}");
                let word2 = format!("{}{}", &word[0..i], &word[i + c.len_utf8()..]);
                for perm in gen_str5(perm2, word2) {
                    yield perm;
                }
                i += c.len_utf8();
            }
        }
    };
    Box::new(std::iter::from_generator(gen)) as Box<dyn Iterator<Item = String>>
}

It needs to take String and use a while loop since you can't hold references across a yield, and it needs to be boxed because it's recursive. But other than that, it's pretty solid and matches the recursive version.

1 Like

Because it's useless: it generates all elements eagerly, meanwhile the whole point of the iterator abstraction is to avoid doing that. So if you generate everything upfront anyway in a dynamic array, then there's no point to hide it behind an iterator, so that's bad style.

1 Like

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.