配列の合計（再帰）｜コードで実践

配列の合計（再帰）

このレッスンで分かること

配列を 先頭 + 残り に分けるアイデアは、ソート 探索 木の走査 でも繰り返し出てくる超重要パターンだ

素朴な再帰版 (arr.slice(1) を毎回作る) の計算量は O(n^2) です

配列の合計を計算する最も自然な方法は for ループです

配列の合計とは

sumArray(arr) を再帰で書く。配列を「先頭 + 残り」に分解する 分割の発想 を学ぶ。

配列の合計を計算する最も自然な方法は for ループです。しかし、ここでは敢えて 再帰 で書いてみます。配列を「先頭 1 要素 + 残り」に分けて、残りの合計 を 再帰 で求める、という発想を使います。これは 分割統治法 (divide and conquer) の入り口です。

配列を 先頭 + 残り に分けるアイデアは、ソート 探索 木の走査 でも繰り返し出てくる超重要パターンだ。

数学的な定義

配列 arr の合計を sum(arr) と書くと、次のように再帰的に定義できます。

sum([]) = 0 (空配列の合計は 0)
sum([x1, x2, ..., xn]) = x1 + sum([x2, ..., xn])

空配列が 基底ケース、それ以外は 先頭 + 残りの合計 です。

Python の実装

Python では スライス (arr[1:]) を使うと、簡潔に書けます。

Python

def sumArray(arr):
    if len(arr) == 0:
        return 0
    return arr[0] + sumArray(arr[1:])

len(arr) == 0 が 基底ケース、arr[0] + sumArray(arr[1:]) が 再帰ケース です。arr[1:] は「配列の 2 番目以降」を意味します。

再帰の展開を Mermaid で見る

sumArray([1, 2, 3]) がどう展開されるか、Mermaid で描いてみます。

diagram (will load when visible)

図のポイント (テキスト併記)

空配列 まで降りて 0 を返し、そこから順に値を足しながら戻っていきます

空配列 まで降りて 0 を返し、そこから順に値を足しながら戻っていきます。6 = 1 + 2 + 3 が最終結果です。

JavaScript / Java での書き方

JavaScript

function sumArray(arr) {
  if (arr.length === 0) return 0;
  return arr[0] + sumArray(arr.slice(1));
}

JavaScript では arr.slice(1) で「2 番目以降の配列」を作れます。Python の arr[1:] と同じ意味です。

Java

public class Solution {
    public static int sumArray(int[] arr) {
        return helper(arr, 0);
    }
    private static int helper(int[] arr, int i) {
        if (i >= arr.length) return 0;
        return arr[i] + helper(arr, i + 1);
    }
}

Java では配列の スライス がやや面倒なので、index を引数に渡す形がよく使われます。これは別解として覚えておくと便利です。

計算量とパフォーマンス

素朴な再帰版 (arr.slice(1) を毎回作る) の計算量は O(n^2) です。配列のコピーを n 回作るためです。一方、index を渡す形なら O(n) で済みます。

arr.slice(1) のような 部分配列の作成 は隠れたコスト。プロダクションコードでは index 渡し 版を選ぶ。

本レッスンでは、シンプルさを優先して スライス 版を使います。計算量の話は、配列のサイズが大きくなったときに重要になる、と覚えておいてください。

よくある間違い

if not arr: return 0 (Python) はオシャレだが、len(arr) == 0 の方が初心者には読みやすい。
arr[0] + sumArray(arr) と書くと 配列が小さくならず 無限再帰になる。必ず arr[1:] (スライス) を使う。
戻り値の型に注意。Java で空配列の合計を null にしてはダメ。0 を返す。

やってみよう

下の coding 課題で、sumArray(arr) を再帰で実装してください。テストでは [] から [1, 2, 3, 4, 5] までの配列で、正しい合計が返るかを確認します。for / while / reduce / sum() 組み込みは使わず、必ず再帰で書いてください。

配列を 先頭 + 残り で考える発想は、関数型プログラミング の head / tail パターンに直結している。Haskell Erlang OCaml などでは、これが当たり前の書き方だ。

Index 渡し版の補足

Java で示したように、index を引数に渡す形は、配列のコピーを作らないので O(n) で動きます。Python でも同じ書き方ができます。

Python

def sumArray_helper(arr, i):
    if i >= len(arr):
        return 0
    return arr[i] + sumArray_helper(arr, i + 1)

def sumArray(arr):
    return sumArray_helper(arr, 0)

ヘルパー関数 を 1 つ追加して、index で進めていく形です。本レッスンの正解としてはどちらでも OK ですが、O(n) で書きたいときはこの index 渡し 版を選んでください。Java 版ではこれが採用されています。

再帰と関数型プログラミングのつながり

配列を分解して再帰 するパターンは、関数型プログラミング の中核です。map filter reduce といった高階関数も、内部では再帰で実装されることが多いです。再帰 を理解すると、高階関数 がやっていることもよく分かるようになります。本レッスンの sumArray は、reduce で書くと arr.reduce((acc, x) => acc + x, 0) という 1 行になります。同じことを 再帰 でやっている、と理解できれば一歩前進です。

よくある質問

Q. 再帰とループはどっちを使うべき？

A. ツリー構造や分割統治（merge sort, BST 走査）は再帰が自然で読みやすくなります。シンプルな反復処理はループが速くスタックも消費しません。再帰深さが配列長に比例する場合、スタックオーバーフローのリスクがあるため気をつけてください。

Q. 再帰のベースケースを忘れるとどうなる？

A. 無限再帰になりスタックオーバーフローします。最初の 1 行目に if (base) return; を書く習慣を付けると安全です。Python は sys.setrecursionlimit で上限を変えられますが、根本的にループに書き換える方が安定します。

Q. 再帰を高速化する方法は？

A. 同じ引数で再計算しているなら memoize（メモ化）で結果をキャッシュします。Python は functools.lru_cache、Java/JS は HashMap で実装します。フィボナッチを memo 付きにすると指数 O(2ⁿ) から線形 O(n) に劇的に高速化します。

次のレッスン

次は 桁数を数える（再帰） で、整数の桁数を再帰で求める方法を学びます。

事前確認 — 進む前に次の 3 つができることを確認しましょう。

配列合計の要点を自分の言葉で説明できる
このレッスンの最小コード (または操作手順) を見ずに書ける
練習問題やクイズで間違えた箇所を読み直して理解した

理解度チェック (30 秒)

Q. 配列合計とは何か、1 文で説明してください。

この章のポイント

A. 本文の「このレッスンで分かること」または冒頭の説明文を見直し、自分の言葉で要約できれば OK。詰まったら本レッスンの最初の H2 セクションを読み返してみましょう。

関連レッスン

配列の合計（再帰）