再帰的アルゴリズムを反復的アルゴリズムに変換するために使用できる一般的なヒューリスティック、ヒント、トリック、または一般的な設計パラダイムはありますか？私はそれができることを知っています、そうするときに覚えておく価値のある慣行があるかどうか疑問に思います。
30206 次
7 に答える
30
多くの場合、再帰アルゴリズムの元の構造を完全に保持できますが、このブログ エントリで提案されているように、テール コールを採用し、継続渡しに変更することで、スタックを回避できます。（私は本当により良いスタンドアロンの例を調理する必要があります。）
于 2009-10-11T07:40:00.790 に答える
22
再帰アルゴリズムを反復アルゴリズムに置き換えるプロセスで使用する一般的な手法は、通常、スタックを使用して、再帰関数に渡されるパラメーターをプッシュすることです。
次の記事を確認してください。
- 再帰をスタックに置き換える
- スタックと再帰の除去(pdf)
于 2009-10-11T06:06:23.583 に答える
8
一般的な方法は、「まだやるべきこと」の実行中のリストを保持する LIFO スタックを管理し、リストが空になるまで続く while ループでプロセス全体を処理することです。
このパターンでは、真の再帰モデルでの再帰呼び出しは、
現在の (部分的に終了した) タスクの「コンテキスト」のスタックへ
のプッシュ、新しいタスク (再帰を促したタスク)のスタックへのプッシュに置き換えられます。スタック
- while ループを「続行」(つまり、ループの先頭にジャンプ) します。ループの先頭近くで、ロジックは最後に挿入されたコンテキストをポップし、これに基づいて作業を開始します。
事実上、これは単に「システム」スタックのネストされたスタックフレームに保持されていた情報を、アプリケーション管理のスタックコンテナーに「移動」するだけです。ただし、このスタック コンテナーはどこにでも割り当てることができるため、改善されています (通常、再帰制限は「システム」スタックの制限に関連付けられています)。したがって、本質的に同じ作業が行われますが、「スタック」の明示的な管理により、再帰呼び出しではなく単一のループ構造内でこれを行うことができます。
于 2009-10-11T06:01:47.057 に答える
7
多くの場合、一般的な再帰は、部分的な結果をアキュムレータに収集し、再帰呼び出しで渡すことにより、末尾再帰に置き換えることができます。末尾再帰は本質的に反復的であり、再帰呼び出しはジャンプとして実装できます。
たとえば、factorial の標準的な一般的な再帰的定義
factorial(n) = if n = 0 then 1 else n * factorial(n - 1)
で置き換えることができます
factorial(n) = f_iter(n, 1)
と
f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)
これは末尾再帰です。と同じです
a = 1;
while (n != 0) {
a = n * a;
n = n - 1;
}
return a;
于 2009-10-11T08:30:56.303 に答える
4
パフォーマンスの例については、これらのリンクをご覧ください
と
と
Q：再帰バージョンは通常高速ですか？A：いいえ-通常は遅くなります（スタックを維持するためのオーバーヘッドのため）
Q: Does the recursive version usually use less memory? A: No -- it usually uses more memory (for the stack). Q: Then why use recursion?? A: Sometimes it is much simpler to write the recursive version (but本当に良い例を見るには、木について話し合うまで待つ必要があります...）
于 2009-10-11T05:44:22.473 に答える
4
私は通常、基本ケース (すべての再帰関数に 1 つある) から開始し、必要に応じて結果をキャッシュ (配列またはハッシュテーブル) に格納して逆方向に作業します。
再帰関数は、小さな部分問題を解決し、それらを使用して問題のより大きなインスタンスを解決することにより、問題を解決します。各サブ問題もさらに分割され、サブ問題が非常に小さくなり、解が自明になるまで (つまり、基本ケース)、それが繰り返されます。
アイデアは、基本ケース (または基本ケース) から始めて、それを使用してより大きなケースのソリューションを構築し、それらを使用してさらに大きなケースを構築するなど、問題全体が解決されるまでです。これはスタックを必要とせず、ループで実行できます。
簡単な例 (Python):
#recursive version
def fib(n):
if n==0 or n==1:
return n
else:
return fib(n-1)+fib(n-2)
#iterative version
def fib2(n):
if n==0 or n==1:
return n
prev1,prev2=0,1 # start from the base case
for i in xrange(n):
cur=prev1+prev2 #build the solution for the next case using the previous solutions
prev1,prev2=cur,prev1
return cur
于 2009-10-12T19:00:41.300 に答える