TCO #rustlang #recursion

tco.rs

// Recursion: TCO (Tail Call Optimization)
// Computerphile: https://www.youtube.com/watch?v=_JtPhF8MshA

fn fib(n: usize) -> usize {
    fib_go(n, 0, 1)
}

fn fib_go(n: usize, a: usize, b: usize) -> usize {
    match (n, a, b) {
        (0, v, _) => return v,
        (1, _, v) => return v,
        (n, x, y) => fib_go(n - 1, y, x + y)
    }
}

fn main() {
    let n = 11;
    println!("fib({}) = {}", n, fib(n)); // 89
}