memoization in rust

fibo_memo.rs

// https://users.rust-lang.org/t/memoization-in-rust/3558/2

use std::collections::HashMap;

fn fibo(n: usize, memo: &mut HashMap<usize, usize>) -> usize {
  // can't use a match here as we'd need to be exhuastive
  if n == 0 || n == 1 {
    // early return, don't proceed with the function if we've matched this condition
    return n
  }

  // check if we've computed this value already
  if let Some(val) = memo.get(&n) {
    return *val
  }

  // we didn't find the answer in the memo, recurse to calculate the answer
  let ans = fibo(n-1, memo) + fibo(n-2, memo);

  // record answer
  memo.insert(n, ans);
  ans
}

fn main() {
  let mut memo: HashMap<usize, usize> = HashMap::new();

  for i in 60..=63 {
    println!("fibo({}) = {}", i, fibo(i, &mut memo));
  }

}