Posted at

JavaScriptで末尾再帰最適化(後付け)する

More than 1 year has passed since last update.

Qiita初投稿です

ES2015では、関数の末尾再帰最適化が仕様としてあったと思うのですが、

未だに各ブラウザでは(標準で)実装されていません。

以下のサイトでは、Pythonでデコレータを使って末尾再帰最適化を実現していました。

これのJavaScript版を書いてみようと思います

http://tanihito.hatenablog.com/entry/20110119/1295459297


var tail_recursion = function(func) {
var is_first = true;
var cont = {};
var saved_args;
var _in = function() {
if (is_first) {
var args = arguments;
while (true) {
is_first = false;
var result = func.apply(null, args);
if (result === cont) {
args = saved_args;
is_first = true;

} else {
is_first = true;
return result;
}
}
} else {
saved_args = arguments;
return cont;
}
};
return _in;
};

こんなふうに使います


var sum = function(num, total){
total = total || 0;
if(num == 0) {
return total
}
return sum(num - 1, total + num);
};
sum = tail_recursion(sum);
console.log(sum(1000000)); //500000500000

こんな風に、関数内部用の名前をつけた場合はうまく動きません


var sum = function sum(num, total){
total = total || 0;
if(num == 0) {
return total
}
return sum(num - 1, total + num);
};
sum = tail_recursion(sum);
console.log(sum(1000000)); //RangeError: Maximum call stack size exceeded

おそらくどのブラウザでも動くのではないでしょうか