JavaScriptで末尾再帰で素数

今度は、JavaScriptで末尾再帰を利用して素数を取得してみました。

paiza.ioでは処理時間が2秒が上限のため、700000まで取得できました。
スタックオーバーフローはおきませんでした。

末尾再帰とは

関数の末尾が自分自身の呼び出しのみになっている再帰のこと。
ここでいう末尾とは、関数の最後の行ということではなく、処理の末尾のこと。（普通はreturn文）

意味のないコードですが、以下のようなものが末尾再帰になります。

function f(x) {
   if (x == 0) {
      return 1;
   }
   return f(x - 1);
}

以下は階乗を取得する再帰関数ですが、最後が自分自身の呼び出しのみになっていないため、末尾再帰ではありません。

function fact(x) {
   if (x == 1) {
      return 1;
   }
   return x * fact(x - 1);
}

なんで、わざわざ再帰でも末尾再帰と特別な名前がついているのかといいますと、簡単に末尾再帰最適化ができるからです。
これは、コンパイラが自動的に対応する場合もありますし、手でも簡単にできます。

JavaScriptには末尾再帰最適化の機能がES6で導入されたため、まだ実装されている処理系はあまりありません。
paiza.ioのNode.jsも未対応です。

なので、手で末尾再帰最適化を行ってみましょう。

問題のコードはこちら

function prime(n) {
    var limit = Math.sqrt(n);
    
    function primemain(primelist, remain) {
        if (remain.length === 0) {
            return primelist;
        }
        else if (limit < remain[0]) {
            return primelist.concat(remain);
        }
        else {
            primelist.push(remain[0]);
            return primemain(primelist, remain.filter(function (x) {return x % remain[0] !== 0}));
        }
    }
    
    var remain = [];
    for (var i = 2; i < n + 1; i++) {
        remain.push(i);
    }

    return primemain([], remain);
}

末尾再帰最適化したコードはこちら。

function prime(n) {
    var limit = Math.sqrt(n);
    var primelist = [];
    var remain = [];
    for (var i = 2; i < n + 1; i++) {
        remain.push(i);
    }
    
    while (true) {
        if (remain.length === 0) {
            return primelist;
        }
        else if (limit < remain[0]) {
            return primelist.concat(remain);
        }
        else {
            primelist.push(remain[0]);
            remain = remain.filter(function (x) {return x % remain[0] !== 0});
        }
    }
}

以下の手順で変更します。

1. 関数定義前に、パラメータだった変数を初期化
2. 関数定義を無限ループに変更。
3. 再帰呼び出し箇所で、パラメータを修正するように変更。

実際に動作するものは以下になります。

せっかく直したのにほとんど速度は変わりませんでした。

※ paiza.ioで、「don't make functions within a loop」のワーニングがでていますが、このケースではクロージャでないため、問題ありません。（クロージャで遅延評価をする場合は危険）
※ 通常の再帰を末尾再帰に変換するほうが大変です。