閑話休題
株式会社 ONE WEDGEの ＠Shankou です。
前回に引き続き、JavaScriptの再帰関数についてのお話となります。前回までで、末尾再帰による最適化がJavaScriptではサポートされていないという話をしました。そして、末尾再帰による最適化が行われない場合はどうすればいいのか、というところで登場するのがトランポリンという手法になります。
今回は、トランポリンとはなんぞやというお話から、、、
トランポリンとは
トランポリン（もしくはトランポリン化）とは、再帰関数をループ（繰り返し処理）でラップすることで、スタックを積むことなく処理を行うというものです。「おい!ループは悪だって言ったじゃん」と思われるかもしれませんが、状態変数を持たないループを用いて処理を構築していきます。
前項の階乗を計算するfactorial関数をトランポリン化した例を示します。
const factorial = (n, accumulator = 1) => {
if (n === 1) return accumulator
else return () => factorial(n - 1, accumulator * n)
}
const trampoline = (func) => {
return (...args) => {
let result = func(...args)
while (typeof result === typeof (() => {})) {
result = result()
}
return result
}
}
const trampolineFactorial = trampoline(factorial)
trampolineFactorial(6) // 720
factorial関数が単純な末尾再帰でないことに注意してもらえたらと思います。「return () => factorial(n - 1, accumulator * n)」とあるように、無名関数を返す形になっています。
trampoline関数内部では、引数として受け取った初期関数の実行結果が関数型である限り（先程の無名関数が返ってくる限り）、繰り返し関数として実行します。再帰に見えて実はループであるというトリックです。 詐欺かもしれません、注意してください。
while文の継続条件が関数かどうかの確認となりますが「typeof (() => {})」は「'function'」でもいいと思います。直埋めが気になるので無名関数に対してtypeofをしていますが、処理速度的には固定文字列の方が早いですし、実行環境でtypeofに差異が出ることもないでしょう、多分。
「const trampolineFactorial = trampoline(factorial)」で、trampoline関数の引数としてfactorial関数を渡しています。こういったものを高階関数と呼んだりしますが、カーリー化とか関数の部分適用の話とかいろいろ枝葉の話が始まってどんどん長くなってしまうので割愛します。興味がある方は調べてみてください。
最終的に出来上がったtrampolineFactorial関数は、引数にどれだけ大きな数値を入れても、スタックオーバーフローが発生することはありません(計算結果が大きすぎるのでInfinityにはなりますが、、、)。
やっていること自体は単純なので、落ち着いて読み解いてもらえたらと思います。
最初に述べた通り、再帰処理はループで書き直すことができます。ですが、再帰くんには再帰くんなりの理由と背景があるのです。
「こんな面倒なトランポリン化とかするくらいならループで書けばいいじゃん」とか言わないでください。
非同期関数の再帰呼び出し
最後に、非同期関数のトランポリン化についてのお話になります。
御存知の通りJavaScriptではasync/awaitを使って非同期処理を明示的に扱うことができます。
一昔前、async/awaitが言語仕様として実装されるまでは、コールバック関数を用いて処理の同期を取るという手段が取られてきました。
ざっくり以下の様な感じです（※分かりやすいようにasyncを使用しています）
async function func1(callback) {
console.log('処理1')
callback()
}
async function func2(callback) {
console.log('処理2')
callback()
}
async function func3(callback) {
console.log('処理3')
callback()
}
async function func4(callback) {
console.log('処理4')
callback()
}
// 同期的実行
func1(function() {
func2(function() {
func3(function(){
func4(function() {
console.log('最後にしたい処理')
})
})
})
})
これが俗に言う「コールバック祭り」「コールバック地獄」というやつです。もちろん今はawaitで処理の戻りを待つことができるので、こんな段々畑を作る必要はありません。
asyncを掛けるとPromiseが返るので、func().then(() => {})という形でコールバックを書けますが、それはそれというやつです。
さて、非同期関数を再帰で呼び出す場合、awaitを使って処理を同期実行させる必要があります。比較して分かりやすくするためにも、factorial関数にasyncを掛けて例を示します。
const asyncFactorial = async (n, accumulator = 1) => {
if (n === 1) return accumulator
else return () => asyncFactorial(n - 1, accumulator * n)
}
const asyncTrampoline = (asyncFunc) => {
return async (...args) => {
let result = await asyncFunc(...args)
while (typeof result === typeof (() => {})) {
result = await result()
}
return result
}
}
const asyncTrampolineFactorial = asyncTrampoline(asyncFactorial)
await asyncTrampolineFactorial(6) // 720
asyncFactorial関数はasyncが掛かっているので、実行するとPromiseが返ります。そのためasyncTrampoline内部では、awaitを掛けて実行結果を取得する必要があります(継続条件が関数型が返ってくるかどうかなのでawaitでの待機が必須です)。
さらに注意が必要なのはawaitはasyncが掛かっている関数内でしか使用できないということです。そのため、該当部分を実行する無名関数にasyncを掛けてやる必要があり、結果としてasyncTrampolineの呼び出し時にはPromiseが返ることから、asyncTrampolineFactorialはawaitで結果を取得する必要があるということになります。
字面で説明すると何言ってんだという感じなので、頑張ってコードと照らし合わせてください。
これで非同期関数の再帰処理をトランポリン化することができました。
まとめ
再帰関数とは何か、何で使うのか、その背景とスタックオーバーフローの対策である末尾再帰とトランポリンについてを、JavaScriptの非同期処理も交えて説明していきました。ふわふわとした説明でつたない部分だらけかと思いますが、まずはざっくりそんな感じなんだなーと思っていただければと思います。
重要なのは問題の解決方法は一つじゃないということです。再帰というのも一つのアプローチ方法に過ぎません。どの方法が一番適切なのかという視点と費用対効果を見比べて、ベストorベターを理由を持って選択をすることが大切だと思います。
「何でこんな書き方してるの？」って聞かれたときに、「Qiitaに書いてあったのをコピペしました」って答える人は駄目です（最近だとChatGPTに言われた通りに書きましたって人もいるよね、、、）。
以上、ここまで読んでいただきありがとうございました。
社員の成長支えます。そうONE WEDGEならね。