JavaScriptの再帰を使って部分和（累積和）の配列を作成する方法

はじめに

次のような数値の配列を考えてみましょう。

const arr = [10, 5, 6, 12, 7, 1];

この配列に対して、先頭から1つずつ要素を減らしながら各部分配列の合計を求めると、以下のようになります。

[10, 5, 6, 12, 7, 1] = 10 + 5 + 6 + 12 + 7 + 1 = 41;
[5, 6, 12, 7, 1] = 5 + 6 + 12 + 7 + 1 = 31;
[6, 12, 7, 1] = 6 + 12 + 7 + 1 = 26;
[12, 7, 1] = 12 + 7 + 1 = 20;
[7, 1] = 7 + 1 = 8;
[1] = 1 = 1;

したがって、最終的な出力は次のような配列になります。

[ 41, 31, 26, 20, 8, 1 ]

今回の課題は、元の配列を受け取り、各位置から末尾までの要素の合計（部分和）を格納した新しい配列を返す関数を作成することです。

手法1：map()とreduce()を組み合わせる

このアプローチの考え方はシンプルです。配列の各要素に対して1つの値を返す必要があるため、まさにその用途に適したArray.prototype.map()メソッドを使用します。

さらに、map()のコールバック内で現在のインデックスと比較しながらreduce()で必要な範囲の合計を計算して返せば、目的の処理を実現できます。

実際のコードは以下の通りです。

const arr = [10, 5, 6, 12, 7, 1];
const partSum = arr.map((item, index) => {
    return arr.reduce((acc, val, ind) => {
       return ind >= index ? acc+val : acc;
    }, 0);
});
console.log(partSum);

手法2：再帰関数を使用する

続いて紹介するのは、2つの再帰関数を組み合わせたアプローチです。

• sumRecursively(arr, start)：配列arrのstartインデックスから末尾までの要素の合計を再帰的に計算して返します。

• partSumRecursively()：必要な合計値を再帰的に結果配列へ連結していき、配列の末尾に到達した時点で完成した配列を返します。

コード例

const arr = [10, 5, 6, 12, 7, 1];
const sumRecursively = (arr, start = 0, res = 0) => {
    if(start < arr.length){
       return sumRecursively(arr, start+1, res+arr[start]);
    };
    return res;
};
const partSumRecursively = (arr, partSum = [], start = 0, end = arr.length-1) => {
    if(start <= end){
       return partSumRecursively(arr, partSum.concat(sumRecursively(arr, start)), ++start, end);
    };
    return partSum;
};
console.log(partSumRecursively(arr));

実行結果

どちらの手法でも、コンソールには同じ出力が表示されます。

[ 41, 31, 26, 20, 8, 1 ]

どちらの手法を選ぶべきか？

map()とreduce()を組み合わせた手法はコードが簡潔で読みやすいのが魅力です。一方、再帰を使った手法は処理の流れが明示的で、ロジックを段階的に追いやすくなっています。

ただし、どちらの実装も各要素ごとに配列を走査し直すため、計算量はO(n²)になる点に注意が必要です。大規模な配列を扱う場合は、末尾の合計から逆順に累積していくことでO(n)で計算できる実装への置き換えも検討するとよいでしょう。