再帰関数とは
一言で言うと、「自分の中で自分を呼ぶ関数」のことです！
下記再帰関数のコード例：
function sumArray(arr) {
if (arr.length === 0) return 0;
return arr[0] + sumArray(arr.slice(1));
}
こういうやつです！
再帰関数が難しいと感じる人は多いと思います。
筆者も理解力が高くないので、上記のコードを理解するのに一時間以上費やしましたw
その結果、再帰関数の理解にはコールスタックの理解が必要不可欠だと感じました。
そのためこの記事は筆者の理解向上&備忘録として書く一方で、再帰の考え方が全く理解できず悩んでいる方の助けになればと思い書いてます！
コールスタックの仕組みが理解できると案外すんなりと再帰の考え方が理解できると思うので、下記の流れで説明しようと思います！
言語はJavaScriptで解説します!
- コールスタックとは何か
- 実際のコード例を用いた解説
コールスタックとは何か
まずは下記関数を見てください。
function a() {
console.log("A1");
b();
console.log("A2");
}
function b() {
console.log("B");
}
a();
結果は、「A1 → B → A2」の順でコンソールに表示されます。
なぜ b() 実行後に、a() の続きである "A2" が実行できるのでしょうか？
JavaScriptに限らず多くの言語で、処理の実行を下記イメージ図のように管理しています！
ChatGPTで生成。便利ですね。
この図のように処理を積み上げていく入れ物を「コールスタック」と言います。
積まれる処理一つ一つを「スタックフレーム」と言います。
そして、最後に積まれた処理から順に完了して取り除かれていく仕組みを「Last In First Out(通称LIFO)」といいます。
日本語だと、「後入先出法」という言い方をします。
非同期処理については、一旦非同期レーンに飛ばされコールスタックが空いたタイミングでイベントループに呼ばれて実行されるという特殊な仕組みのため今回は説明を割愛します。
webの非同期APIとPromiseで挙動が違うため興味がある方は非同期処理の流れについても調べると面白いと思います。
ここまでコールスタックについて説明したため、最後に最初の例として利用した再帰関数を用いて処理の流れを解説します。
実際のコード例を用いた再帰の解説
まず、下記の関数を見てください。
ぱっと見、sumArrayの中でsumArrayを呼び出し、引数として配列をsliceしたものを渡すという頭がこんがらがりそうな関数になっています...
この処理が何を行なっているか説明すると、配列の数字の合計を導き出しています。
結果は「10」になります。
たったそれだけです！
それだけですが、複雑そうに見えますね...
これを今からコールスタックの仕組みを用いて解説します!
function sumArray(arr) {
if (arr.length === 0) return 0;
return arr[0] + sumArray(arr.slice(1));
}
const array = [1, 2, 3, 4]
再帰では同じ関数が何度もコールスタックに積まれていくため、どの呼び出しの話をしているのか分からなくなりがちです。そのため、この記事では積まれた順に「スタック1」「スタック2」…と番号を振って解説していきます。
ベースケース(停止条件)
再帰を終了させる条件を「ベースケース」と呼びます。
この関数では下記の部分がベースケースに該当します。
if (arr.length === 0) return 0;
再帰関数は、自分を呼び続ける関数であるため、このベースケースがないと無限に自分自身を呼び出し続け(無限再帰)、コールスタックが上限に達して下記のエラーが表示されます。
Maximum call stack size exceeded
そのため、ベースケースは再帰を終了させるために必ず必要になります。
再帰開始!
補足ですが、slice(1)が何をしているかと言うと、今回の例で言うと配列の先頭の数字を除いた新しい配列を作っています。
arr.slice(1) ///[2, 3, 4]こんな感じです！
スタック1
最初の呼び出し時の状態は以下のようになります！
初期の状態を「スタック1」と名付けます。
//スタック1
return arr[0] + sumArray(arr.slice(1));
//arr = [1, 2, 3, 4]
//arr[0] = 1
//sumArray(arr.slice(1)) = [2, 3, 4]
ここでコールスタック登場です!
まだ、この関数は引数のarrに[1, 2, 3, 4]を持っていて、lengthが0ではないため、ベースケースに該当せず、後続の「sumArray(arr.slice(1))」の戻り値を待っている状態になります。
そして、sumArrayの引数に [2, 3, 4] が渡され、新しいスタックフレームが積まれます。
スタック2
下記は現在の状態です。
この状態を「スタック2」と名付けます。
//スタック2
return arr[0] + sumArray(arr.slice(1));
//arr = [2, 3, 4]
//arr[0] = 2
//sumArray(arr.slice(1)) = [3, 4]
そして、sumArrayの引数に[3, 4]が渡され、新しいスタックフレームが積まれます。
スタック3
まだ、lengthが0ではないため再帰的に呼び出されます。
この状態を「スタック3」と名付けます。
//スタック3
return arr[0] + sumArray(arr.slice(1));
//arr = [3, 4]
//arr[0] = 3
//sumArray(arr.slice(1)) = [4]
そしてsumArrayの引数に[4]が渡され、新しいスタックフレームが積まれます。
スタック4
まだ、lengthが0ではないため再帰的に呼び出されます。
この状態を「スタック4」と名付けます。
//スタック4
return arr[0] + sumArray(arr.slice(1));
//arr = [4]
//arr[0] = 4
//sumArray(arr.slice(1)) = []
そしてsumArrayの引数には空配列が渡され、新しいスタックフレームが積まれます。
スタック5
ついにlengthが「0」になりました！
ベースケースに到達したので、if文に入って「0」がreturnされます!
この時点で再帰呼び出しが終了し、ここから巻き戻しが始まります。
//スタック5
if (arr.length === 0) return 0;
//この条件に該当するため、sumArrayはもう実行されない。
//arr = [] 空配列
ここからが重要です!
現在の状態をイメージ図で確認してください。
ChatGPTで生成
ここから折り返し!
スタック5→スタック4へ戻る
この時、スタック4で実行したsumArrayの戻り値が「0」となります。
コールスタックに積まれた一つ一つのスタックフレームは、その時の状態を覚えています。
そのため、スタック4では下記のような処理が実施されます。
//スタック4
return arr[0] + sumArray(arr.slice(1));
//arr[0] = 4
//sumArray(arr.slice(1))の戻り値「0」
//4 + 0 = 4
//合計された「4」が戻り値となる。
スタック4→スタック3へ戻る
スタック3で実行したsumArrayの戻り値が「4」となります。
そのため、スタック3では下記のような処理が実施されます。
//スタック3
return arr[0] + sumArray(arr.slice(1));
//arr[0] = 3
//sumArray(arr.slice(1))の戻り値「4」
//3 + 4 = 7
//合計された「7」が戻り値となる。
スタック3→スタック2へ戻る
スタック2で実行したsumArrayの戻り値が「7」となります。
そのため、スタック2では下記のような処理が実施されます。
//スタック2
return arr[0] + sumArray(arr.slice(1));
//arr[0] = 2
//sumArray(arr.slice(1))の戻り値「7」
//2 + 7 = 9
//合計された「9」が戻り値となる。
スタック2→スタック1へ戻る
スタック1で実行したsumArrayの戻り値が「9」となります。
そのため、スタック1では下記のような処理が実施されます。
//スタック1
return arr[0] + sumArray(arr.slice(1));
//arr[0] = 1
//sumArray(arr.slice(1))の戻り値「9」
//1 + 9 = 10
//合計された「10」が戻り値となる。
そして、「10」がreturnされsumArray関数はコールスタックから削除され処理が終了します。
まとめ
再帰関数は「行き(スタックを積む)」と「折り返し(戻り値を計算しながら戻る)」の2段階で動きます。コールスタックという入れ物にスタックフレームが積まれ、ベースケースに到達したら巻き戻しが始まる──この流れを意識すると、複雑に見えた再帰もシンプルに読めるようになります。
解説の中で違う部分などありましたらコメントください!