rust fib
fn fib(x: i32) -> i32 { match x { 0 => 0, 1 => 1, _ => fib(x -1) + fib(x -2), } } fn main() { for a in 0..=10 { println!("fib {} is: {}", a, fib(a)) } } fib 0 is: 0 fib 1 is: 1 fib 2 is: 1 fib 3 is: 2 fib 4 is: 3 fib 5 is: 5 fib 6 is: 8 fib 7 is: 13 fib 8 is: 21 fib 9 is: 34 fib 10 is: 55 use std::collections::HashMap; fn memoized_fib(n: u64, memo: &mut HashMap<u64, u64>) -> u64 { if memo.contains_key(&n) { return *memo.get(&n).unwrap(); } let result = match n { 0 => 0, 1 => 1, _ => memoized_fib(n - 1, memo) + memoized_fib(n - 2, memo), }; memo.insert(n, result); result } fn main() { let mut memo: HashMap<u64, u64> = HashMap::new(); for x in 0..=20 { println!("fib ({}): {}", x, memoized_fib(x, &mut memo)); } } fib (0): 0 fib (1): 1 fib (2): 1 fib (3): 2 fib (4): 3 fib (5): 5 fib (6): 8 fib (7): 13 fib (8): 21 fib (9): 34 fib (10): 55 fib (11): 89 fib (12): 144 fib (13): 233 fib (14): 377 fib (15): 610 fib (16): 987 fib (17): 1597 fib (18): 2584 fib (19): 4181 fib (20): 6765