Rustでメモ化再帰実装

概要

標準ライブラリのstd::collections::HashMapを使用して結果をメモしていく。
基本的には他言語と変わらないが参照を渡していくことを忘れない様にする。

use std::collections::HashMap;

fn fib(n: u64, memo: &mut HashMap<u64, u64>) -> u64 {
    if n == 0 || n == 1 {
        return n;
    }
    if memo.contains_key(&n) {
        return memo[&n];
    }
    let result = fib(n - 1, memo) + fib(n - 2, memo);
    memo.insert(n, result);
    result
}

fn main() {
    let mut buffer = String::new();
    std::io::stdin().read_line(&mut buffer).unwrap();
    let n = buffer.trim().parse::<u64>().unwrap();

    let mut memo = HashMap::new();
    println!("{}", fib(n, &mut memo));
}