LoginSignup
4
3

More than 5 years have passed since last update.

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

Posted at

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

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

4
3
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
4
3