How would you improve this?

Hi,
I've seen something similar but decided to write my own: this is a bit of helper function / enum to replace recursion with thunks
Play: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=f275b8bf4e9b4531ee9795433490f125

enum Recursive<R> {
    Value(R),
    Continuation(Box<dyn FnMut(R) -> R>, Box<dyn FnMut() -> Recursive<R>>),
}

fn extract<R>(r: Recursive<R>) -> R {
    let mut cons: Vec<Box<dyn FnMut(R) -> R>> = vec![];
    let mut next = r;
    let mut value;
    loop {
        let n = match next {
            Recursive::Value(v) => {
                value = v;
                break;
            }
            Recursive::Continuation(fv, mut fc) => {
                cons.push(fv);
                let f = fc.as_mut();
                f()
            }
        };
        next = n;
    }
    loop {
        if cons.is_empty() {
            return value;
        }
        let mut last = cons.remove(cons.len() - 1);
        value = last(value);
    }
}

// example usage:
fn fibo_rec(n: usize) -> Recursive<usize> {
    if n == 2 || n == 1 {
        Recursive::Value(1)
    } else {
        let c1 = Box::new(move |i| i + extract(fibo_rec(n - 2)));
        let c2 = Box::new(move || fibo_rec(n - 1));
        Recursive::Continuation(c1, c2)
    }
}
// use: println!("{}", extract(fibo_rec(40)));

You can replace FnMut with FnOnce, and use iterators to clean up your code a bit, playground

1 Like

This is great! Thanks!