Rustで末尾再帰のトランポリン化

recursive_trampoline.rs

enum RetVal {
    Num(u128),
    Recursive(Box<dyn Fn() -> RetVal>),
}

fn trampoline(r: RetVal) -> u128 {
    let mut r = r;
    loop {
        match &r {
            RetVal::Recursive(func) => {
                r = func();
            }
            RetVal::Num(n) => {
                return *n;
            }
        }
    }
}

fn main() {
    println!("{}", trampoline(sigma(100000, 1)));
    trampoline(fibonacci(50, 1, 1));
}

fn sigma(n: u128, ans: u128) -> RetVal {
    if n <= 1 {
        return RetVal::Num(ans);
    }
    return RetVal::Recursive(Box::new(move || sigma(n - 1, ans + n)));
}

fn fibonacci(n: u64, acc: u128, acc2: u128) -> RetVal {
    print!("{} ", acc);
    if n == 1 {
        return RetVal::Num(acc);
    }
    return RetVal::Recursive(Box::new(move || (fibonacci(n - 1, acc2, acc + acc2))));
}