[解決済み] 再帰から反復への道

質問

私は長年のプログラミングで、簡単な問題を解決するために再帰をよく使ってきましたが、メモリや速度の問題で反復が必要な場合があることは十分承知しています。

そこで、かなり昔のことですが、一般的な再帰処理を反復処理に変換するパターンや教科書的な方法がないか調べてみたのですが、何も見つかりませんでした。少なくとも、私が覚えている限りでは、役に立ちそうなものはありませんでした。

• 一般的なルールはありますか？
• パターンがありますか？

解決方法は？

通常、再帰的な関数に渡されるはずのパラメータをスタックに押し込んで、再帰的なアルゴリズムを反復的なアルゴリズムに置き換えるんだ。実際には、プログラムのスタックを自分自身のスタックに置き換えているのです。

var stack = [];
stack.push(firstObject);

// while not empty
while (stack.length) {

    // Pop off end of stack.
    obj = stack.pop();

    // Do stuff.
    // Push other objects on the stack as needed.
    ...

}

注意：内部に複数の再帰呼び出しがあり、呼び出しの順番を守りたい場合は、逆順にスタックに追加する必要があります。

foo(first);
foo(second);

は、次のように置き換える必要があります。

stack.push(second);
stack.push(first);

編集部：記事 スタックと再帰性の排除 (または 記事バックアップリンク には、このテーマについてより詳しく書かれています。