fib_fn.rs

use num::{Integer, One};
use std::collections::HashMap;
use std::hash::Hash;

fn fib<T>(n: T) -> T
where
    T: std::fmt::Debug + Copy + Hash + Integer,
{
    fn fib_memory<T>(n: T, memory: &mut HashMap<T, T>) -> T
    where
        T: std::fmt::Debug + Copy + Hash + Integer,
    {
        if !memory.contains_key(&n) {
            let val = if n <= One::one() {
                n
            } else {
                fib_memory(n - One::one(), memory) + fib_memory(n - One::one() - One::one(), memory)
            };
            memory.insert(n, val);
        }
        *memory.get(&n).unwrap()
    }

    fib_memory(n, &mut HashMap::new())
}

fn main() {
    for i in 0..187 as u128 {
        println!("fib({}): {}", i, fib(i));
    }
}