Rustで再帰関数 (2)

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

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

今回はユークリッドの互除法。

use proconio::input;

fn input(use_default_values: bool) -> (u64, u64) {
    if use_default_values {
        let m = 51;
        let n = 15;
        return (m, n);
    } else {
        println!("Input n and a:");
        input! {
            m: u64,
            n: u64,
        }
        return (m, n);
    }
}

fn gcd(m: u64, n: u64) -> u64 {
    match n {
        // ベースケース
        0 => m,
        // 再帰呼び出し
        _ => gcd(n, m % n),
    }
}

/// ユークリッドの互除法によって最大公約数を求める
pub fn code_4_4(use_default_values: bool) -> u64 {
    // 入力
    let (m, n) = input(use_default_values);
    gcd(m, n)
}

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

    #[test]
    fn code_4_4_works() {
        assert_eq!(code_4_4(true), 3);
    }
}

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