use std::io::{stdin, stdout, Write};

struct CachedFib(Vec<u64>);

impl CachedFib {
    fn fib(&mut self, n: usize) -> u64 {
        self.0.reserve(n);
        if self.0.len() <= n {
            let result = match n {
                0 | 1 => 1,
                _ => self.fib(n - 1) + self.fib(n - 2),
            };
            self.0.push(result);
            result
        } else {
            self.0[n]
        }
    }
}

fn main() {
    let mut fib = CachedFib(vec![1, 1]);
    loop {
        print!("Enter a positive integer: ");
        stdout().flush().expect("could not flush buffer");

        let mut input = String::new();
        let read = stdin().read_line(&mut input).expect("failed to read line");
        // EOF
        if read == 0 || input.trim() == "quit" {
            break;
        }

        let num: usize = match input.trim().parse() {
            Ok(num) => num,
            Err(e) => {
                println!("error parsing integer: {}", e);
                continue;
            }
        };

        println!("fibonacci of {} is {}", num, fib.fib(num));
    }
}