fib_struct.rs

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

struct CachedFib<T> {
    memory: HashMap<T, T>,
}

impl<T> CachedFib<T>
where
    T: Copy + Hash + Integer,
{
    fn new() -> Self {
        CachedFib {
            memory: HashMap::new(),
        }
    }

    fn fib(&mut self, n: T) -> T {
        if !self.memory.contains_key(&n) {
            let val = if n <= One::one() {
                n
            } else {
                self.fib(n - One::one()) + self.fib(n - One::one() - One::one())
            };
            self.memory.insert(n, val);
            return val;
        }
        *self.memory.get(&n).unwrap()
    }
}

fn main() {
    let mut cached_fib = CachedFib::new();
    for i in 0..187 as u128 {
        println!("fib({}): {}", i, cached_fib.fib(i));
    }
}