配列の合計（再帰）
配列の合計はループで書けば数行です。それでも再帰で書いてみるのは、「先頭 1 つ」と「残り全部」に分ける発想を手に入れるためです。この分け方は、このあとのソートや探索でも繰り返し出てきます。
同じ配列を渡すと、何も減らない
配列を受け取る再帰で、最初にやりがちな失敗です。
Python
def walk(items):
if len(items) == 0:
return
print(items[0])
walk(items) # items がそのまま止まる条件は書いてあるのに終わりません。渡している items が、呼び出しのたびに同じものだからです。数値のときは n - 1 と書けば減りましたが、配列では「短くした配列を作って渡す」という一手間が要ります。
先頭を外した配列を渡す
Python なら items[1:]、JavaScript なら items.slice(1)、Java なら Arrays.copyOfRange で「2 番目以降」を取り出せます。
Python
def walk(items):
if len(items) == 0:
return
print(items[0])
walk(items[1:])これで walk([10, 20, 30]) は 10, 20, 30 を表示して止まります。長さが 3, 2, 1, 0 と必ず 1 ずつ減るので、どんな配列を渡しても空にたどり着きます。
items[0] で先頭 1 つ、items[1:] で残り全部。この 2 つが、配列を再帰で扱うときの基本の道具です。言語ごとの書き方は次のとおりです。
プレーンテキスト
Python items[0] items[1:]
JavaScript items[0] items.slice(1)
Java items[0] Arrays.copyOfRange(items, 1, items.length)
Go items[0] items[1:]空になるまで降ろす
止める位置にも注意が要ります。「1 個になったら、その 1 個を返せばいい」と考えて長さ 1 で止めると、最初から空の配列を渡されたときに条件を素通りし、items[0] で範囲外エラーになります。
空配列まで降ろしてから止めるほうが安全です。要素が 1 個でも 0 個でも同じ道を通るので、境界のことを別に考えずに済みます。
そのとき「空の配列に対して何を返すか」を決めておく必要があります。合計を求めるなら、何も足していない状態を表す値を返すのが自然です。この「何もしていないときの値」は問題ごとに違い、掛け算なら別の値になります。まずここを決めてから残りを書くと、途中で手が止まりません。
短くした配列を作る書き方は分かりやすい代わりに、呼び出しのたびに配列を丸ごとコピーします。要素が数万を超えるような場面では、代わりに「何番目から見るか」という数値だけを持ち回る書き方に切り替えます。
要件
- 関数
sumArray(arr)を実装し、合計を整数で返す - for / while / 組み込みの sum を使わず、必ず再帰で実装する
- 基底ケース (空配列のとき 0 を返す) を必ず書く
入出力例
sumArray([1,2,3]) → 6
sumArray([5]) → 5
sumArray([1,2,3,4,5]) → 15
sumArray([10,20,30]) → 60
sumArray([-1,1,-2,2]) → 0ヒント
