はじめに
ES6 (EcmaScript 6)を試そうと、Babelのドキュメントを読んでいたところ、末尾呼び出し（Tail Call）の最適化をしていることにびっくり。公式リリース（2015年6月）から３ヶ月あまり経ってはいますが、ES6が末尾呼び出し最適化を仕様としてサポートしていることをようやく知りました。
現状で末尾呼び出し最適化をサポートしているブラウザはなく（ブラウザやaltJSなどのES6互換表を参照）、唯一、ES6からES5へのトランスパイラであるBabelのみが部分的（直接的な末尾再帰のみ）ではありながらサポートしているようですね。
今回の記事では、来たるES6時代（いまさらの感はありますが）に備えて、末尾再帰とその最適化について簡単に解説した上で、Babelを利用して実際にJavaScriptでの末尾再帰の最適化を実験してみたいと思います。
ざっくり概要
- 再帰関数 は関数呼び出しの階数が深くなりすぎると スタックオーバーフロー が発生する問題があります。
- 末尾呼び出しのコード最適化 技術により、再帰関数を 末尾再帰 に変換するとこの問題は解決できます。
- ただし、コード最適化はプログラムの実行環境がサポートしていないとその恩恵を受けられません。
- 次世代JavaScriptの仕様となるES6では 末尾呼び出しのコード最適化が仕様化されています。
- そのため、各ブラウザやnode.jsなどの実行環境は、ES6に準拠するにはコード最適化を実装する必要があります。
- 現時点（2015/10）で最適化を実装しているブラウザ（実行環境）はありません。
- ただし、ES6からES5へのトランスパイラである Babel は制限付きながら最適化を実現しています。
- BabelはES6の末尾再帰のコードを通常のループ（whileなど）によるコードに変換します。
再帰関数の問題
再帰関数
自分自身を呼び出す関数を 再帰関数（recursive function） と呼びます。よくある例ですが、与えられた数nの階乗（1からnまでのすべての数値の積）を計算する以下の関数factorialは再帰関数です。
// 階乗を計算する関数
function factorial(n) {
if (n === 0) {
return 1;
}
return n * factorial(n - 1); // 自分自身を呼び出す
}
console.log(factorial(3)); // 6となる
スタックオーバーフロー
再帰関数は自分自身を再帰的に呼び出すため、関数の呼び出し階層が深くなりがちです。内部的には関数の呼び出しごとにメモリ領域が消費されるため、呼び出し階層が深くなりすぎると実行時エラーが発生する場合があります。実際、上記のfactorial関数を手元のnode.js（v0.12.6）上で実行したところ、引数が100000でエラーになりました。（Infinityは数値の上限を超えたからです。今回のエラーとは関係ありません。）
> function factorial(n) {
... if (n === 0) {
..... return 1;
..... }
... return n * factorial(n - 1);
... }
undefined
> factorial(100);
9.33262154439441e+157
> factorial(1000);
Infinity
> factorial(10000);
Infinity
> factorial(100000);
RangeError: Maximum call stack size exceeded
at factorial (repl)
at factorial (repl:5:24)
at factorial (repl:5:24)
at factorial (repl:5:24)
at factorial (repl:5:24)
at factorial (repl:5:24)
at factorial (repl:5:24)
at factorial (repl:5:24)
at factorial (repl:5:24)
at factorial (repl:5:24)
>
factorial(100000)の結果として、"RangeError: Maximum call stack size exceeded"（スタックの上限を超えたよ！）とありますよね。これは関数の呼び出し階層が上限を超えたことを表す実行エラーです。このようなエラーを一般的に スタックオーバーフロー と呼びます。プログラミング言語に関係なく、プログラマならば一度は遭遇したことがあるエラーですよね。
解決方法は？
一つの方法は、再帰を通常のループに書き換えることです。以下は、forループを使用したfactorialの実装です。この関数は引数の大きさにかかわらず、関数の呼び出し階層は一定（１つだけ）なので、スタックオーバーフローは発生しません。
function factorial(n) {
var result = 1;
for (var i = 1; i <= n; i++) {
result = result * i;
}
return result;
}
実際、引数100000で実行しても以下のようにスタックオーバーフローは発生しません。
> function factorial(n) {
... var result = 1;
... for (var i = 1; i <= n; i++) {
..... result = result * i;
..... }
... return result;
... }
undefined
> factorial(100000);
Infinity
>
結局再帰関数って使えないの？
これまでのJavaScriptに対する答えとしては、「はい。注意して使用しないとだめです。」 となるでしょう。上記のような問題が発生するため、再帰があまりにも深くならないように注意するなど、限定的な状況でしか利用できませんでした。
次世代のJavaScript（ES6）に対する答えとしては、「いいえ。そんなことはありません。末尾再帰に変換すればよいのです。」 となるでしょう。再帰関数は 末尾再帰 と呼ばれる特殊な形の再帰関数に書き換えることができます。末尾再帰にすると、 末尾呼び出し最適化 と呼ばれるコード最適化技術の恩恵を受けられるようになります。このコード最適化の技術により、上記のようなスタックオーバーフローは発生しなくなります。ES6は仕様として、JavaScriptの実行環境側に末尾呼び出し最適化を要求しているため、ES6に準拠したブラウザや実行環境であれば末尾再帰を利用すればよいのです。
では、以降では末尾再帰や末尾呼び出し最適化技術について詳しくみていきましょう。
末尾呼び出しと末尾呼び出し最適化
末尾呼び出し
ある関数fが、別の関数gを呼び出すとします。gの呼び出しがfのリターン前の最後の処理であるとき、gの関数呼び出しを 末尾呼び出し（tail call） と呼びます。
例えば、次の関数fにおいて、関数gの実行後にその結果をfはリターンするだけなので、gの呼び出しは末尾呼び出しとなります。
function f() {
return g(); // g()は末尾呼び出し
}
以下のgおよびhの呼び出しも末尾呼び出しとなります。しかし、bの呼び出し後にfの処理が続くため、bの呼び出しは末尾呼び出しではなりません。
function f() {
if (b()) { // b()は末尾呼び出しではない
return g(); // g()は末尾呼び出し
}
else {
return h(); // h()は末尾呼び出し
}
}
以下の例では、ソースコード上、hの呼び出しはfの最後にありますが、末尾呼び出しではありません。なぜなら、hの呼び出し後に+による加算処理が続くためです。
function f() {
return g() + h(); // h()は末尾呼び出しではない。当然ながらg()も末尾呼び出しではない。
}
末尾呼び出し最適化
コールスタック
通常のプログラムの実行モデルでは、関数を呼び出すと、関数自身のローカル変数（引数や局所変数）や戻り先情報を保持するスタックフレーム（アクティベーションレコード）が生成されてコールスタックと呼ばれるスタックにpushされます。関数はスタックフレームに計算途中の値を保持しつつ処理を続けます。関数の実行が終わると対応するスタックフレームがpopされて呼び出し元のスタックフレームに復帰し、呼び出し元関数の実行が再開されます。
以下のコードを題材として、コールスタックの動きをシミュレーションしてみましょう。
function squareSum(x) {
var xs = square(x); //(A)
var result = sum(xs); //(B)
return result; //(C)
}
function square(n) {
return n * n;
}
function sum(n) {
return n + n;
}
//結果は8
squareSum(2); //(X)
表記
以下では、関数fのスタックフレームをf:{x:1, y:2}:returnTo:戻り先の位置で表します。ここで、xとyはfのローカル変数（引数を含む）とし、それぞれ値1と2を保持しているものとします。f関数の終了時の戻り先はreturnToが表すものとします。
シミュレーション
さて、プログラムの開始時のスタックフレームは空です。（X）の位置でsquareSum関数が引数2で呼び出された直後は、コールスタックにsquareSumのスタックフレームがpushされます。ここで、局所変数xsとresultはまだ値が設定されていません。戻り先には位置(X)が設定されます。
| コールスタック |
|---|
| squreSum:{x:2, xs:undefined, result:undefined}:returnTo:(X) |
次に、(A)でsuqare関数が引数2(=x)で呼び出されます。コールスタックには引数nが2で初期化されたスタックフレームがpushされます。関数終了後に戻り先は(A)が設定されます。
| コールスタック |
|---|
| square:{n:2}:returnTo:(A) |
| squreSum:{x:2, xs:undefined, result:undefined}:returnTo:(X) |
関数squareはnの二乗を計算した後、呼び出し元のsquareSumに戻ります。ここで、squareのスタックフレームはpopされて、呼び出し元スタックフレームのxsにはsquareの計算結果4が代入されます。returnToに設定されていた(A)の位置から実行が再開されます。
| コールスタック |
|---|
| squreSum:{x:2, xs:4, result:undefined}:returnTo(X) |
次に、位置(B)でsum関数が引数4(=xs)で呼び出されます。このとき、コールスタックは次のようになります。
| コールスタック |
|---|
| sum:{n:4}:returnTo:(B) |
| squreSum:{x:2, xs:4, result:undefined}:returnTo(X) |
関数sumの実行が終了すると、sumのスタックフレームはpopされます。ここで、resultの値はsumの実行結果が代入されます。returnToに設定されていた(B)の位置から、squareSumの実行が再開されます。
| コールスタック |
|---|
| squreSum:{x:2, xs:4, result:8}:returnTo(X) |
最後にsquareSumはresultの値8をリターンしてプログラムは位置(X)に戻って終了します。ここで、コールスタックは空になります。
末尾呼び出しの除去
上記のsquareSum関数は、スタックフレームに計算途中の値（xsやresult）を保持して実行を続けます。このように、スタックフレームは関数の実行途中の値を保持する一時領域としての役割を持ちますが、再帰関数の例で既にみたように、関数呼び出し階層があまりにも深くなるとスタックフレーム数が大きくなり、メモリ領域を食いつぶしてしまうことがあります。不要なスタックフレームの生成はできれば避けたいところです。
スタックフレームは関数の計算途中の値を保持するのに必要ですが、言い換えると、計算途中の値がそれ以上使用されないのであれば、スタックフレームも不要ということになります。ここで、関数の末尾呼び出しに着目してみましょう。ある関数fが別の関数gを末尾呼び出ししているとき、fの結果（リターン値）はgの結果そのものです。つまり、gの呼び出し後にfのスタックフレームは使用されません。したがって、gの呼び出し時にスタックフレームを新たに生成するのではなく、fのスタックフレームをgのスタックフレームとして再利用することが可能です。これを 末尾呼び出しの除去（tail call elimination） と呼びます。コンパイラや実行環境が行う末尾呼び出しの除去を 末尾呼び出し最適化（tail call optimization） といいます。
以下の簡単なコードをみてください。fooはsumを末尾呼び出ししています。
function foo(x) {
return sum(x, x); // (A)
}
function sum(a, b) {
return a + b;
}
foo(2); // (X)
末尾呼び出しの除去を行わないケース
このコードのスタックフレームの動きをみてみましょう。まず、末尾呼び出しの除去を行わない通常のケースです。
位置(X)でfooを呼び出した直後は次のようになります。
| コールスタック |
|---|
| foo:{x:2}:returnTo:(X) |
次に、(A)の位置でsum関数を呼び出した直後は次のようになります。
| コールスタック |
|---|
| sum:{a:2, b:2}:returnTo:(A) |
| foo:{x:2}:returnTo:(X) |
関数sumが終了するとスタックフレームがpopされ、returnToが示す(A)の位置からfooの関数の実行が再開されます。ここで、sumの戻り値を保持するための一時的な領域が内部的に生成されているはずです。この例では_tmp変数にsumの戻り値が格納されるとします。
| コールスタック |
|---|
| foo:{x:2, _tmp:4}:returnTo:(X) |
最後にfooは_tmpの値をリターンして終了します。
末尾呼び出しの除去を行うケース
次に、末尾呼び出しの除去を行う場合の挙動をみてみましょう。
まず、fooの呼び出し直後のコールスタックは次のようになります。
| コールスタック |
|---|
| foo:{x:2}:returnTo:(X) |
次に、(A)でsum関数を呼び出します。通常（末尾呼び出しの除去を行わない場合）は新しいスタックフレームが生成されてpushされることろですが、末尾呼び出しの除去を行う場合、fooのスタックフレームをsumのコールスタックとして再利用します。このとき、コールスタックは次のようになります。ここで、fooの戻り先として、sumの戻り先（X）が設定されることに注目してください。つまり、sumのリターン値（実行結果）がそのままfooのリターン値となるのです。
| コールスタック |
|---|
| sum:{a:2, b:2}:returnTo:(X) |
関数sumは計算結果4をreturnToが示す位置(X)にリターンします。
末尾再帰と末尾再帰の最適化
末尾再帰
再帰関数のうち、自分自身の呼び出しが末尾呼び出しとなっている再帰関数を 末尾再帰（tail recursive） と呼びます。
本記事の最初に例示した以下の階乗計算関数は自分自身を再帰呼び出ししたあと、*による演算を行っているため、末尾呼び出し（つまり、末尾再帰）ではありません。
// 階乗を計算する再帰関数（末尾再帰ではない）
function factorial(n) {
if (n === 0) {
return 1;
}
return n * factorial(n - 1); // 自分自身を呼び出した後に、* による演算を行っているので末尾呼び出しではない。
}
この関数をを末尾再帰に書き直したコードは以下のようになります。内部関数factorialTailCallは自分自身を末尾呼び出ししています。ポイントは、演算結果を関数の引数として累積してくところです。
// 階乗を計算する関数（末尾再帰バージョン）
function factorial(n) {
// 末尾再帰関数
function factorialTailCall(n, accum) {
if (n === 0) {
return accum;
}
return factorialTailCall(n - 1, n * accum); // 自分自身を末尾呼び出し
}
var result = factorialTailCall(n, 1); // (Y)
return result;
}
console.log(factorial(3)); // (X)
末尾再帰の最適化
末尾再帰は自分自身を末尾呼び出しする再帰関数です。つまり、末尾呼び出しの除去のテクニックが利用できます。
上記のfactorialTailCall関数が末尾呼び出しの除去による最適化がコンパイラによって行われていると仮定しましょう。このとき、factorial(3)を実行したときのコールスタックの状態遷移をみてみましょう。
まず、factorialのスタックフレームがpushされます。resultの値はまだundefinedです。
| コールスタック |
|---|
| factorial:{n:3, result:undefined}:returnTo(X) |
次に、(Y)の位置で、factorialTailCall(3, 1)が呼び出されるため、factorialTailCallの新しいスタックフレームが生成されてpushされます。このとき、nとaccumの値はそれぞれ、3と1に初期設定されます。
| コールスタック |
|---|
| factorialTailCall:{n:3, accum:1}:returnTo(Y) |
| factorial:{n:3, result:undefined}:returnTo(X) |
次に、factorialTailCallが再帰呼び出されると、新しいスタックフレームは生成されず、既にあるスタックフレームのnとaccumの値が更新されます。そして、factorialTailCallの実行が開始されます。
| コールスタック |
|---|
| factorialTailCall:{n:2, accum:3}:returnTo(Y) |
| factorial:{n:3, result:undefined}:returnTo(X) |
さらに、factorialTailCallが再帰的に呼び出されます。スタックフレームのnとaccumの値が更新されます。
| コールスタック |
|---|
| factorialTailCall:{n:1, accum:6}:returnTo(Y) |
| factorial:{n:3, result:undefined}:returnTo(X) |
最後の再帰呼び出しが実行されます。
| コールスタック |
|---|
| factorialTailCall:{n:0, accum:6}:returnTo(Y) |
| factorial:{n:3, result:undefined}:returnTo(X) |
関数factorialTailCallはaccumの値6をリターンします。このとき、スタックフレームはpopされて、位置(Y)からfactorial関数の実行が再開されます。resultはaccumの値が設定されます。
| コールスタック |
|---|
| factorial:{n:3, result:6}:returnTo(X) |
関数factorialはresultの値をリターンし、(X)の位置から処理が再開します。
上記のように、末尾再帰関数factorialTailCallのスタックフレームの消費数は常に１つです。末尾呼び出し最適化により、末尾再帰は効率的に実行できることが理解できると思います。
JavaScriptでの末尾呼び出し最適化
末尾呼び出し最適化はプログラミングテクニックではありません。コンパイラなどの言語処理系によるコード最適化の技術です。例えば、Javaはサポートしていません。同じJVM言語でもScalaは制限付きでサポートしています。Schemeは言語の実装仕様として要求しています。
JavaScriptについては、これまで末尾呼び出し最適化は実行環境の実装者に依存していました。ES6ではSchemeと同じように言語仕様として末尾呼び出し最適化を求めています。そのため、今後、各ブラウザはES6に準拠するために末尾呼び出し最適化を実装するでしょう。ただし、現時点では末尾呼び出し最適化を実装しているブラウザはないようです（ブラウザやaltJSなどのES6互換表を参照）。
ただし、後述するBabelを利用すると、JavaScriptでも末尾再帰の最適化の恩恵を受けることができるようになります。
Babelによる末尾再帰の最適化
BabelはES6のコードからES5のコードを生成するトランスパイラの一種です。Babelでは、ES5を生成する過程で、末尾再帰を通常のループ処理に変換することで、末尾再帰の最適化を実現しています。ただし、Babelが可能な最適化には制約があり、相互再帰（付録を参照してください）などの複雑な再帰関数の最適化はできません。自分自身を直接呼び出す末尾再帰のみが最適化対象です。
では、Babelによる末尾再帰の最適化の実験を行ってみましょう。本記事で紹介した末尾再帰バージョンの再帰関数を再掲します。
// 階乗を計算する関数（末尾再帰バージョン）
function factorial(n) {
function factorialTailCall(n, accum) {
if (n === 0) {
return accum;
}
return factorialTailCall(n - 1, n * accum);
}
return factorialTailCall(n, 1);
}
この関数をBabelによりES5のコードに変換すると、次のようなコードが生成されます。今回の変換は、Babelが提供するWebサービスを利用しました。
function factorial(n) {
function factorialTailCall(_x, _x2) {
var _again = true;
_function: while (_again) {
var n = _x,
accum = _x2;
_again = false;
if (n === 0) {
return accum;
}
_x = n - 1;
_x2 = n * accum;
_again = true;
continue _function;
}
}
return factorialTailCall(n, 1);
}
関数factorialTailCallがwhileを使ったループに変換されているのが分かりますね！
まとめ
再帰関数を利用するとループよりもエレガントにコードが書ける場合があるので、これからのJavaScript(ES6)では積極的に使っていきたいところです。ただし、通常の再帰ではなく、末尾再帰でなければ実行時の効率が悪いという課題があります。方針としては、まずは通常の再帰関数でコード化した後、再帰関数を末尾再帰にリファクタリングするという流れになるでしょう。再帰関数の作成の秘訣は、プログラミングHaskellに紹介されていますので是非参照してみてください。
付録
多重再帰
自分自身を複数回呼び出す再帰関数を 多重再帰関数 と呼びます。フィボナッチ数を求める以下の関数は多重再帰関数です。
// フィボナッチ数を求める関数
function fibonacci(n) {
if (n === 0 || n === 1) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
console.log(fibonacci(0)); // 0
console.log(fibonacci(1)); // 1
console.log(fibonacci(2)); // 1
console.log(fibonacci(3)); // 2
console.log(fibonacci(4)); // 3
相互再帰
複数の関数が、それぞれを呼び出し合う場合、これらの関数を 相互再帰関数 と呼びます。例えば、以下の偶数・奇数を判定する関数は相互再帰関数です。
// nが偶数ならばtrueを返す関数
function isEven(n) {
if (n === 0) {
return true;
}
return isOdd(n - 1);
}
// nが奇数ならばtrueを返す関数
function isOdd(n) {
if (n === 0) {
return false;
}
return isEven(n - 1);
}
ES6の末尾呼び出し最適化の仕様
ES6では抽象操作関数のPrepareForTailCallの実行時の意味論として、末尾呼び出し時のコールスタックの動作が定義されているようです。PrepareForTailCallは末尾呼び出しの位置にある関数を呼び出し前に現在のコールスタックの先頭のスタックフレーム（つまり呼び出し元関数のスタックフレーム）をpopします。次に、関数呼び出しが発生すると新しいスタックフレームをpushします。本記事ではスタックフレームを再利用するという前提で解説しましたが、ES6では、いったんpopしてから再度pushしているようですね。
また、スタックフレームをpopすると関数の戻り先は消えるだろうと思いましたが、ES6のスタックフレームは戻り先の位置ではなく、現在実行中の位置を保持しているようです。つまり、関数呼び出し時に現在の位置を保持してから新しいスタックフレームをpushします。関数の呼び出しが終了するとスタックフレームをpopし、記憶している位置から実行を再開するわけです。この辺は完全に理解しているわけではないので間違っている可能性がありますがご容赦ください。
PrepareForTailCallの意味論のNOTEとして、以下のように記述されています。
For example, a tail position call should only grow an implementation’s activation record stack by the amount that the size of the target function’s activation record exceeds the size of the calling function’s activation record. If the target function’s activation record is smaller, then the total size of the stack should decrease.
つまり、呼び出し先関数のスタックフレーム（原文ではアクティベーションレコードとあります）のサイズが呼び出し元関数のスタックフレームのサイズより超過した分だけ、コールスタックの総サイズは大きくなる（あるいは小さくなる）ということですね。