Rustで再帰関数 (1)

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

今回は 1 から n までの総和を計算。

use proconio::input;

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

/// 1 から n までの総和を計算する再帰関数
pub fn code_4_1(n: u64) -> u64 {
    match n {
        0 => 0,
        _ => n + code_4_1(n - 1),
    }
}

/// 1 から n までの総和を計算する再帰関数
pub fn code_4_2(n: u64) -> u64 {
    // 再帰関数を呼び出したことを報告する
    println!("code_4_2({}) を呼び出しました", n);

    match n {
        0 => 0,
        _ => {
            // 再帰的に答えを求めて出力する
            let result = n + code_4_2(n - 1);
            println!("{} までの和 = {}", n, result);
            result
        }
    }
}

/// 再帰呼び出しが止まらない再帰関数
pub fn code_4_3(n: u64) -> u64 {
    match n {
        0 => 0,
        _ => n + code_4_3(n + 1),
    }
}

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

    #[test]
    fn code_4_1_works() {
        assert_eq!(code_4_1(10), 55);
    }
}

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