JavaScriptの末尾呼び出し最適化（TCO）

JavaScriptには、再帰が実装されている。
再帰とは、関数のなかでその関数自身を呼び出すこと。

下記のrecursion()では、再帰を行っている。

function recursion(num, limit){
    console.log(num);
    if(num === limit){ return; };
    num++;
    recursion(num, limit);
};

recursion(0, 10);を実行すると、0から10の数字が順番に表示される。
仮引数numがlimitに到達するまでrecursion()は呼ばれ続ける。

だが、limitの数を大きくすると、途中でエラーになりプログラムが終了してしまう。

function recursion(num, limit){
    console.log(num);
    if(num === limit){ return; };
    num++;
    recursion(num, limit);
};

// RangeError: Maximum call stack size exceeded
// 17000前後で終了
// limitに到達する前に
recursion(0, 30000);

これは、関数を何度も繰り返し呼び出しているうちに、メモリを食い尽くしてしまうために起きる。
何回再帰すればエラーになるかは環境によるが、いつか必ずエラーになる。

末尾呼び出し最適化

このように、何度も再帰を繰り返すとエラーになってしまうが、言語によってはそれを避ける仕組みが用意されている。
それが、末尾呼び出し最適化（tail call optimization）である。

末尾呼び出しとは、その関数の最後の処理として再帰を行うことである。
先程のrecursion()も末尾呼び出しである。

そして、末尾呼び出しの際にメモリを解放し、いくら再帰してもエラーにならないようにする仕組みのことを、末尾呼び出し最適化と呼ぶ。

JavaScriptには末尾呼び出し最適化の仕組みは用意されていなかったが、ES2015で導入された。

2017/08/19 追記

> 末尾呼び出しとは、その関数の最後の処理として再帰を行うことである。

おお？？
JavaScriptの末尾呼び出し最適化（TCO） - 30歳からのプログラミングhttps://t.co/BhRreYTANM

— κeen (@blackenedgold) 2017年8月18日

末尾呼び出しと末尾再帰と末尾再帰関数は区別しような！

— κeen (@blackenedgold) 2017年8月18日

とのことなので、改めて確認した。

処理の最後での呼び出しを、末尾呼び出しという。再帰かどうかを問わない。
そして、末尾呼び出しのうち再帰であるものが、末尾再帰。
そして、末尾再帰となっている関数、つまり、自分自身を末尾呼び出ししている関数が、末尾再帰関数。

この記事が分かりやすい気がする。

こうしてみると、末尾呼び出しとは、その関数の最後の処理として再帰を行うことである。という自分の説明は滅茶苦茶であることが分かる……。

追記終わり

使い方

strictモードで、return fn()という形で末尾呼び出しを行う。

'use strict'

function recursion(num, limit){
    console.log(num);
    if(num === limit){ return; };
    num++;
    return recursion(num, limit);
};

// 30000になるまで実行される
recursion(0, 30000);

このようにすると末尾呼び出し最適化が行われ、エラーにならず最後まで再帰が続けられる。

対応状況

ES2015は仕様であり、実際にそれを使えるかどうかはブラウザ等の実装に依存する。
そして、末尾呼び出し最適化を実装している環境は、かなり少ない。

	Safari	Node.js	Chrome	Firefox	Babel
対応状況	◯	△	×	×	×
確認したバージョン	10.0.2	6.9.2	55.0.2883.95	50.1.0	6.18.0
備考	-	harmonyのみ	-	-	v6で削除された

詳細はこちらを参照。
ECMAScript 6 compatibility table

Node.jsでは、--harmonyオプションをつけた場合のみ、動作する。

Babelについては、かつては動作したようだが、現在のバージョンである6では削除されている。
Babelを使えば動くという記事がいくつかあるが、それは過去のものであり、本日現在では使えないので注意が必要。
BabelのGitHubのIssueを漁ってみると、いろいろと書かれてある。

TCO has since been removed from Babel 6 due to issues and will be redeveloped in the future.
https://github.com/babel/babel/issues/2547#issuecomment-155588021

実装されている環境がほとんどなく、Babelによるトランスパイルも出来ないので、現時点ではほとんど実用性がない。
だがES2015の仕様で定められているのだから、いずれ実装が進んで使えるようになるはず。

参考資料

• 末尾呼び出し最適化が実装された - JS.next