自然数列の和 -ループ・再帰・漸化式- : JavaScript

Tweet

Pocket

自然数列の和を求めるプログラムでループ処理と再帰処理の比較をする。

ループ

ループを使った処理をJavaScriptで書く。

// 自然数列の和　1 + 2 + 3 + 4 + 5 + ... + n
// ループを使った処理
var sum = function (k) {
    var n;
    var sum = 0;
    
    for (n = 1; n <= k; n++) {
        sum += n;
    }
    return sum;
}
sum(0); // 0
sum(1); // 1
sum(10); // 55

再帰

ループの代わりに再帰を使って求める。

• 再帰で呼び出す処理sum(n-1)は元の処理sum(n)に比べて簡単な処理である。
• 漸化式sum(n-1) + nを使う。

// 自然数列の和
var sum = function (n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }
    return sum(n-1) + n;
}
sum(0);  // 0
sum(1);  // 1
sum(10); // 55

即時実行とメモ化を利用したコード。

// 自然数列の和
var sum = (function () {
    var sequence = []; // メモ化のために結果の数列を配列に保存
    return function summation (n) {
        if (n == 0) {
            return sequence[0] = 0;
        } else if (n == 1) {
            return sequence[1] = 1;
        } else {
            if (sequence[n-1]) {
                sequence[n] = sequence[n-1] + n;
                return sequence[n];
            } else {
                sequence[n] = summation(n-1) + n;
                return sequence[n];
            }
        }
    }
}()) // 即時実行
sum(0); // 0
sum(1); // 1
sum(10); // 55