JavaScriptでスタックオーバーフローを起こさず高速に再帰呼び出しをする

JavaScriptでは、以下のような関数の再帰呼び出しをすると、ブラウザごとに定義されている最大コールスタック数を超えたとき、エラーが出ます。

var i = 0;

function recurse() {
    i++;
    recurse();
}

recurse();

// Uncaught RangeError: Maximum call stack size exceeded
// InternalError: too much recursion

手元のGoogle Chromeでは、上記のコードでiが20888まで増加したところでエラーが出ました。

このエラーを一般に、「スタックオーバーフロー」と言います。

スタックオーバーフローの回避

JavaScriptにおいて、このエラーは、再帰的に呼び出す関数を非同期的に呼び出すことによって回避できます。すなわち、以下のようにすることで、スタックオーバーフローを回避することができます。

var i = 0;

function recurseSafe() {
    i++;
    setTimeout(function () {
        recurseSafe();
    }, 0);
}

recurseSafe();

setTimeout関数は非同期関数であり、第一引数に与えた関数を実行する前に結果を返します。なので、コールスタックを再帰的に消費しません。

そして、setTimeoutの第二引数に0を指定しているので、最小限の遅延で関数を実行します。

しかし、実際にこの関数を実行してみると、とても遅いことがわかります。例えば、以下のコードを実行してみましょう。

var i = 0;

function recurseSafe(callback) {
    i++;
    if (i < 30000) {
        setTimeout(function () {
            recurseSafe(callback);
        }, 0);
    } else {
        callback(i);
    }
}

console.time('timer');
recurseSafe(function () {
    console.timeEnd('timer');
});

上記のコードは、setTimeout関数を利用して、30000回再帰呼び出しをするというだけのコードです。そして、その間、console.time及びconsole.timeEndメソッドにより、処理にかかる時間を計測しています。それ以外の処理は一切ありません。

ですが、手元のGoogle Chromeでは、上記のコードを実行したところ、以下のように表示されました。

timer: 139795.931ms

具体的な処理は一切ないのにも関わらず、2分以上かかっています。かなり遅いです。

というのも、setTimeout関数は、正確には「第二引数 n ミリ秒以上後に指定処理を行う」ものであり、0を指定したからといって必ずしも0ミリ秒後に実行するわけではないのです。実際には、ブラウザのタイマーの最小解像度（ブラウザにもよるが数ms程度）の後、処理がキューに追加され、更にキューに追加されている処理が順番に実行される仕組みとなっています。

つまり、setTimeout関数は少なくとも数msは遅延する上、処理が輻輳すればそれ以上遅延することもあるということです。

再帰処理によるスタックオーバーフローのエラーこそ出なくなりましたが、状況によってはこれでは使い物にならない場合もあります。

`setTimeout`関数（遅延ゼロ）の高速化

setTimeout関数の遅延が問題となる場合には、高速に非同期で実行してくれる関数setZeroTimeoutを、以下のように定義します。

(function () {
    var timeouts = [],
        messageName = 'zero-timeout-message';

    function setZeroTimeoutPostMessage(fn) {
        timeouts.push(fn);
        window.postMessage(messageName, '*');
    }

    function setZeroTimeout(fn) {
        setTimeout(fn, 0);
    }

    function handleMessage(event) {
        if (event.source == window && event.data == messageName) {
            if (event.stopPropagation) {
                event.stopPropagation();
            }
            if (timeouts.length) {
                timeouts.shift()();
            }
        }
    }

    if (window.postMessage) {
        if (window.addEventListener) {
            window.addEventListener('message', handleMessage, true);
        } else if (window.attachEvent) {
            window.attachEvent('onmessage', handleMessage);
        }
        window.setZeroTimeout = setZeroTimeoutPostMessage;
    } else {
        window.setZeroTimeout = setZeroTimeout;
    }
}());

ここでは詳しい説明はしませんが、setZeroTimeout関数はwindow.postMessageを利用して、高速に非同期処理を行うことを実現した関数です。

この関数を定義し使用することで、スタックオーバーフローを起こさず、なおかつ高速に処理をループすることができます。

var i = 0;

function recurseSafeFast(callback) {
    i++;
    if (i < 30000) {
        setZeroTimeout(function () {
            recurseSafeFast(callback);
        }, 0);
    } else {
        callback(i);
    }
}

console.time('timer');
recurseSafeFast(function () {
    console.timeEnd('timer');
});

上記のsetZeroTimeout関数を使って30000回再帰呼び出しをするコードを実行したところ、手元のGoogle Chromeでは、以下のような結果になりました。

timer: 4333.111ms

4秒程度で終わりました。setTimeoutの場合と比べてかなり高速です。

なお、このsetZeroTimeout関数を大量に利用する場合、多くの場合では大丈夫だと思いますが、多すぎると重くなることも考えられますので、ご利用は計画的にどうぞ。

スタックオーバーフローの回避

setTimeout関数（遅延ゼロ）の高速化

参考

`setTimeout`関数（遅延ゼロ）の高速化