dynamic_fibonacci.rs

use std::io;
use std::io::Write;

fn main() {
    // create a vector to hold the fibonacci values and prefill with 0, 1
    println!("Enter -1 to exit");
    let mut fill_on_the_fly = vec![0, 1];
    loop {
        let n = get_isize("Enter a number: ");
        if n == -1 {
            break;
        }
        println!(
            "fibonacci of {} is {}",
            n,
            fibonacci_on_the_fly(&mut fill_on_the_fly, n)
        );
    }
}

fn fibonacci(n: isize) -> isize {
    // base cases
    if n == 0 {
        0
    } else if n == 1 {
        1
    } else {
        fibonacci(n - 1) + fibonacci(n - 2)
    }
}

fn fibonacci_on_the_fly(values: &mut Vec<isize>, n: isize) -> isize {
    // check the length of the vector to see if values[n] has been filled in
    if values.len() as isize <= n {
        // if not, recursively call the function to calculate
        let next = fibonacci_on_the_fly(values, n - 1) + fibonacci_on_the_fly(values, n - 2);
        values.push(next);
    }
    // return the value
    values[n as usize]
}

fn get_isize(prompt: &str) -> isize {
    print!("{}", prompt);
    io::stdout().flush().unwrap();
    let mut input = String::new();
    io::stdin()
        .read_line(&mut input)
        .expect("Failed to read line");
    input.trim().parse().expect("Please type a number!")
}