Rustで再帰関数 (3)

『アルゴリズムとデータ構造』を Rust で実装してみるシリーズ。4章の再帰と分割統治法。

前回 → https://quantized-cube.com/rust-recursive-02

今回はフィボナッチ数列。

use proconio::input;

fn input(use_default_values: bool) -> usize {
    if use_default_values {
        let n = 49;
        return n;
    } else {
        println!("Input n:");
        input! {
            n: usize,
        }
        return n;
    }
}

/// フィボナッチ数列を求める再帰関数
pub fn code_4_5(n: u64) -> u64 {
    match n {
        // ベースケース
        0 => 0,
        1 => 1,
        // 再帰呼び出し
        _ => code_4_5(n - 1) + code_4_5(n - 2),
    }
}

/// フィボナッチ数列を求める再帰関数の
/// 再帰呼び出しの様子
pub fn code_4_6(n: u64) -> u64 {
    println!("code_4_6({}) を呼び出しました", n);

    match n {
        // ベースケース
        0 => 0,
        1 => 1,
        // 再帰的に答えを求めて出力する
        _ => {
            let result = code_4_6(n - 1) + code_4_6(n - 2);
            println!("{} 項目 = {}", n, result);
            result
        }
    }
}

/// フィボナッチ数列を for 文による反復で求める
pub fn code_4_7() {
    let mut f: Vec<u64> = vec![0; 50];
    f[1] = 1;
    for n in 2..50 {
        f[n] = f[n - 1] + f[n - 2];
        println!("{} 項目 = {}", n, f[n]); // f[49] = 7778742049
    }
}

fn fibo(n: usize, memo: &mut Vec<i64>) -> i64 {
    // ベースケース
    if n == 0 {
        return 0;
    } else if n == 1 {
        return 1;
    }

    // メモをチェック (すでに計算済みならば答えをリターンする)
    if memo[n] != -1 {
        return memo[n];
    }

    // 答えをメモ化しながら，再帰呼び出し
    memo[n] = fibo(n - 1, memo) + fibo(n - 2, memo);
    return memo[n];
}

/// フィボナッチ数列を求める再帰関数をメモ化
pub fn code_4_8(use_default_values: bool) -> i64 {
    // 入力
    let n = input(use_default_values);

    // fibo(n) の答えをメモ化する配列
    // メモ化用配列を -1 で初期化する
    let memo: &mut Vec<i64> = &mut vec![-1; n + 1];

    // fibo(49) をよびだす
    fibo(49, memo);

    // memo[0], ..., memo[49] に答えが格納されている
    for n in 2..50 {
        println!("{} 項目 = {}", n, memo[n]);
    }
    memo[n]
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn code_4_5_works() {
        assert_eq!(code_4_5(6), 8);
    }

    #[test]
    fn code_4_6_works() {
        assert_eq!(code_4_6(6), 8);
    }

    #[test]
    fn code_4_8_works() {
        assert_eq!(code_4_8(true), 7778742049);
    }
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust