はじめに
初投稿になります、株式会社 ONE WEDGEの ＠Shankou です。
今回はJavaScriptの非同期関数の再帰処理についてのすごくふんわりとした解説記事になります。
アルゴリズムの専門家でも、言語の設計者でもない、主に先輩風を吹かせて後輩に読ませようと思って書いているだけの記事となりますので、間違いがあったら優しく指摘していただけると嬉しいです。主に初心者から中級者の方向けの内容になりますので、あまり深く突っ込まないでください。
二重三重の予防線
Scalaを触っていた経験から、末尾再帰とトランポリンについてのぼんやりとした理解は持っていましたが、少し前に仕事で「JavaScriptで非同期関数の再帰呼び出し」を考えなきゃいけない機会がありましたので、知識の整理がてらちょっとまとめてみようと思った次第です。
再帰関数
再帰関数って何？ っていう初心者の方は、こちらの解説記事（ 再帰関数を学ぶと、どんな世界が広がるか, @drken ）が図説付きで分かりやすくておすすめです。
再帰関数の定義には大きく2つのポイントがあります。
- 終了条件を持たなければならない
- 状態を変えながら終了条件に進んでいかなければならない
これを満たすことができない場合、無限再帰ループと言って、いわゆる無限ループと同じ状態になってしまいます。
さて、問題となるのは再帰の回数が多くなるとスタックオーバーフローが発生するということです。そもそも、再帰処理というのはループで書き直すことができます。
先程の条件を読んだときに「これってループ処理じゃね？」思った人もいるでしょう。その通りです。そして、ループ処理というのはスタックを積むことがないので、オーバーフローが発生しません。
！！？？？？？
じゃあ、そもそもなんで再帰関数なんかを使うのかというと、再帰の方がスッキリ書けるという理由もありますが、その源流には関数型プログラミングの影響があったりします。
近年、オブジェクト指向と関数型の融合、イイトコドリのようなものが様々な言語で進んでいると思います。Javaでラムダ式や関数型インタフェースが導入されたりもしていますしね。
関数型プログラミングでは状態変数は最大悪です。そして、その代表悪がループで使われるカウンター「 i 」の存在です。
プログラミングを始めたばかりの頃にデバッグでグルグルと、今の「 i 」はいくつだ？ 配列のどこを指しているんだ？ みたいなことを追いかけた記憶があると思います。あれは「 i 」がそのときどきで変化する状態変数であるからこそ発生する問題です。
状態変数はバグの温床であり、状態変数を持たないだけでこの世に存在するバグの9割は消せます。（当社比）
近年のオブジェクト指向言語は、できるだけ余計な状態変数を持たないように論理フローを構築しましょうね、という感じで関数型の概念を取り込んでいる感じです（あってるよね？）。
そして、関数型では副作用のない小さな関数を作り、その組み合わせで大きな処理を構築するというのが基本的な考え方になります。再帰の考え方もこれと同じで、ループという大きな処理ではなく、小さな関数を組み合わせて(自身の再呼び出しを行うことで)全体を処理するという流れをとります。こういった考え方、手法を分割統治法というそうです。このあたりがループと再帰の考え方の違いになります。
さて、問題となるのは再帰の回数が多くなるとスタックオーバーフローが発生するということです。そもそも、再帰処理というのはループで書き直すことができます。ループ処理というのはスタックを積むことがないので、オーバーフローが発生しません。
！！？？？？？
break;
このままでは話がループして進まないので、それではどうやって再帰処理でのスタックオーバーフロー問題を解決するのか、という話に移ろうと思います。
一般的には末尾再帰による最適化という手法が取られます。
末尾再帰による最適化
末尾再帰による最適化というのは、末尾再帰を検知したコンパイラがスタックの累積をなくして処理の効率化を行ってくれるというものです。実装者は末尾再帰を意識して再帰関数を作ればいいということになります。
では、末尾再帰とはどういったものかというと、簡単に説明すれば自身の呼び出しで処理が終わっている再帰関数のことです。
あるあるですが、階乗を計算する関数をJavaScriptでの例で示します。
const factorial = (n) => {
if (n === 0) return 1
else return n * factorial(n - 1)
}
console.log(factorial(6)) // 720
普通に階乗を計算する再帰関数を作ると上記のようになると思います。「n * factorial(n - 1)」で自身を呼び出した結果を利用して、最後に計算をしてしまっている形です。これは「自身の呼び出しで処理が終わっている」ことにはならないので末尾再帰ではありません。
この関数に10000くらいを渡すとスタックオーバーフローが発生しました。
それではこの再帰関数を末尾再帰に書き直してみたいと思います。以下の通りです。
const factorial = (n, accumulator = 1) => {
if (n === 1) return accumulator
else return factorial(n - 1, accumulator * n)
}
console.log(factorial(6)) // 720
先程とは違い、「factorial(n - 1, accumulator * n)」 という自身の呼び出しで処理が終わっています。末尾再帰ではaccumulator（累算器、積算器、加算器）という途中計算を保持する変数がよく使われるそうです。途中計算を引数で渡し歩くことが末尾再帰を実装する上でのミソとなるんですね。
この関数に10000くらいを渡すとスタックオーバーフローが発生しました。
！！？？？？？
末尾再帰による最適化ですが、JavaScriptではまだまだサポートが追いついていません(執筆時点でSafariのみの限定対応だと思われます)。
では、末尾再帰による最適化が行われない場合はどうすればいいのか、というところで登場するのがトランポリンという手法になります。
意外と長くなったので②に続きます。
社員の成長支えます。そうONE WEDGEならね。