fib_dynamic.rs

fn fib(n: u64) -> u64 {
    match n {
        0 => 1,
        1 => 1,
        _ => fib(n - 1) + fib(n - 2)
    }
}

fn fib_fast(n: u64) -> u64 {
    let mut seen = vec![None; 1 + n as usize];
    fn fib_with_seen(n: u64, seen: &mut Vec<Option<u64>>) -> u64 {
        match seen[n as usize] {
            Some(x) => x,
            None => {
                let x = match n {
                    0 => 1,
                    1 => 1,
                    _ => fib_with_seen(n - 1, seen) + fib_with_seen(n - 2, seen)
                };
                seen[n as usize] = Some(x);
                x
            }
        }
    }
    fib_with_seen(n, &mut seen)
}

fn main() {
    for i in 35..40 { // SLOW!!!
        println!("fib({}) = {}", i, fib(i));
    }
    for i in 35..93 { // > 92 causes integer overflow
        println!("fib_fast({}) = {}", i, fib_fast(i));
    }
}