私は単純な問題を解決するために長年のプログラミングで再帰をかなり使用してきましたが、メモリ/速度の問題のために反復が必要になる場合があることを十分に認識しています。
そのため、非常に遠い昔、反復への一般的な再帰アプローチを変換する「パターン」またはテキストブックの方法が存在するかどうかを試してみましたが、何も見つかりませんでした。または、少なくとも私が覚えていることは何も役に立ちません。
- 一般的なルールはありますか？
- 「パターン」はありますか？
167862 次
21 に答える
395
通常、再帰関数に通常渡されるパラメーターをスタックにプッシュすることにより、再帰アルゴリズムを反復アルゴリズムに置き換えます。実際、プログラムスタックを独自のものに置き換えています。
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);
編集：このテーマの詳細については、記事Stacks and Recursion Elimination（またはArticle Backupリンク）を参照してください。
于 2008-10-01T21:12:30.660 に答える
85
実際、これを行う最も一般的な方法は、独自のスタックを保持することです。C の再帰的クイックソート関数は次のとおりです。
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
独自のスタックを保持することで反復的にする方法は次のとおりです。
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
明らかに、この例はスタック境界をチェックしません...そして実際には、左と右の値が与えられた最悪のケースに基づいてスタックのサイズを調整できます。しかし、あなたはその考えを理解します。
于 2008-10-01T20:55:03.197 に答える
64
再帰関数が本体で複数回呼び出され、再帰の特定のポイントに戻ることを処理する (つまり、プリミティブ再帰ではない) 場所に誰も対処していないようです。すべての再帰を反復に変えることができると言われているので、これは可能であるように思われます。
これを行う方法の C# の例を思いついたところです。ポストオーダー トラバーサルのように機能する次の再帰関数があり、AbcTreeNode がポインター a、b、c を持つ 3 項ツリーであるとします。
public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
if (x != null) {
AbcRecursiveTraversal(x.a, list);
AbcRecursiveTraversal(x.b, list);
AbcRecursiveTraversal(x.c, list);
list.Add(x.key);//finally visit root
}
}
反復ソリューション:
int? address = null;
AbcTreeNode x = null;
x = root;
address = A;
stack.Push(x);
stack.Push(null)
while (stack.Count > 0) {
bool @return = x == null;
if (@return == false) {
switch (address) {
case A://
stack.Push(x);
stack.Push(B);
x = x.a;
address = A;
break;
case B:
stack.Push(x);
stack.Push(C);
x = x.b;
address = A;
break;
case C:
stack.Push(x);
stack.Push(null);
x = x.c;
address = A;
break;
case null:
list_iterative.Add(x.key);
@return = true;
break;
}
}
if (@return == true) {
address = (int?)stack.Pop();
x = (AbcTreeNode)stack.Pop();
}
}
于 2011-12-14T21:42:35.173 に答える
36
再帰呼び出しをTail Recursion (最後のステートメントが再帰呼び出しである再帰) にするように努めてください。それができたら、それを反復に変換するのは一般的に非常に簡単です。
于 2008-10-01T20:45:32.877 に答える
22
一般に、ストレージ変数を使用するだけで、反復として再帰を模倣できます。再帰と反復は一般に同等であることに注意してください。ほとんどの場合、一方は他方に変換できます。末尾再帰関数は、反復関数に非常に簡単に変換できます。アキュムレータ変数をローカル変数にして、再帰ではなく反復するだけです。以下は C++ の例です (C はデフォルト引数を使用するためのものではありませんでした)。
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
私を知っているので、おそらくコードを間違えましたが、アイデアはそこにあります。
于 2008-10-01T20:53:27.960 に答える
16
スタックを使用しても、再帰アルゴリズムは反復アルゴリズムに変換されません。通常の再帰は関数ベースの再帰であり、スタックを使用するとスタックベースの再帰になります。しかし、それでも再帰です。
再帰アルゴリズムの場合、空間の複雑さは O(N) であり、時間の複雑さは O(N) です。反復アルゴリズムの場合、空間の複雑さは O(1) であり、時間の複雑さは O(N) です。
しかし、複雑さの観点からスタックを使用しても、同じままです。反復に変換できるのは末尾再帰だけだと思います。
于 2010-11-06T16:27:11.603 に答える
9
「継続渡しスタイル」をグーグルで検索してください。末尾再帰スタイルに変換するための一般的な手順があります。末尾再帰関数をループに変換する一般的な手順もあります。
于 2008-10-01T20:48:00.530 に答える
6
暇つぶし…再帰関数
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
に変換できます
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
stack.push(node->right);
stack.push(node->left);
while(!stack.empty()) {
node1 = stack.pop();
if(node1 == NULL)
continue;
// Do something with node1...
stack.push(node1->right);
stack.push(node1->left);
}
}
于 2011-08-25T05:15:56.270 に答える
6
実際にスタックが必要なものを考えてみましょう:
再帰のパターンを次のように考えると:
if(task can be done directly) {
return result of doing task directly
} else {
split task into two or more parts
solve for each part (possibly by recursing)
return result constructed by combining these solutions
}
たとえば、古典的なハノイの塔
if(the number of discs to move is 1) {
just move it
} else {
move n-1 discs to the spare peg
move the remaining disc to the target peg
move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}
これは、次のように言い換えることで、明示的なスタックで動作するループに変換できます。
place seed task on stack
while stack is not empty
take a task off the stack
if(task can be done directly) {
Do it
} else {
Split task into two or more parts
Place task to consolidate results on stack
Place each task on stack
}
}
ハノイの塔の場合、これは次のようになります。
stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
task = stack.pop();
if(task.size() = 1) {
just move it
} else {
stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
stack.push(new Task(1, task.from(), task.to(), task.spare()));
stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
}
}
ここでは、スタックの定義方法に関してかなりの柔軟性があります。Commandスタックを、洗練された処理を行うオブジェクトのリストにすることができます。または、反対方向に進み、より単純なタイプのリストにすることもできます (たとえば、「タスク」は、スタック上のint1 つの要素ではなく、スタック上の 4 つの要素である可能性がありますTask)。
これは、スタックのメモリが Java 実行スタックではなくヒープにあることを意味しますが、より詳細に制御できるという点で便利です。
于 2017-08-14T15:09:15.953 に答える
5
一般に、再帰関数のスタック オーバーフローを回避する手法はトランポリン手法と呼ばれ、Java 開発者によって広く採用されています。
ただし、C# の場合は、ロジックを変更したり、コードをわかりにくくしたりすることなく、再帰関数を反復関数に変換する小さなヘルパー メソッドがここにあります。C# は非常に優れた言語であり、驚くべきことが可能になります。
メソッドの一部をヘルパー メソッドでラップすることで機能します。たとえば、次の再帰関数:
int Sum(int index, int[] array)
{
//This is the termination condition
if (int >= array.Length)
//This is the returning value when termination condition is true
return 0;
//This is the recursive call
var sumofrest = Sum(index+1, array);
//This is the work to do with the current item and the
//result of recursive call
return array[index]+sumofrest;
}
になる：
int Sum(int[] ar)
{
return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
于 2012-05-23T11:31:20.593 に答える
4
探すパターンの 1 つは、関数の最後での再帰呼び出し (いわゆる末尾再帰) です。これはしばらくの間で簡単に置き換えることができます。たとえば、関数 foo は次のようになります。
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
foo の呼び出しで終了します。これは次のように置き換えることができます:
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
これにより、2 番目の再帰呼び出しがなくなります。
于 2008-10-01T20:48:55.600 に答える
3
この質問の重複としてクローズされた質問には、非常に特殊なデータ構造がありました。
ノードの構造は次のとおりです。
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
再帰的な削除関数は次のようになります。
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
一般に、それ自体を複数回 (または 1 回でも) 呼び出す再帰関数のスタックを常に回避できるとは限りません。ただし、この特定の構造では可能です。アイデアは、すべてのノードを 1 つのリストにフラット化することです。これは、現在のノードchildを一番上の行のリストの最後に置くことによって実現されます。
void cNODE_Delete (cNODE *c) {
cNODE *tmp, *last = c;
while (c) {
while (last->next) {
last = last->next; /* find last */
}
if ((tmp = c->child)) {
c->child = NULL; /* append child to last */
last->next = tmp;
tmp->prev = last;
}
tmp = c->next; /* remove current */
free(c);
c = tmp;
}
}
この手法は、決定論的なトポロジー順序で DAG に縮小できるデータ リンク構造に適用できます。現在のノードの子は、最後の子が他のすべての子を採用するように再配置されます。次に、現在のノードを削除し、トラバーサルを残りの子に反復できます。
于 2016-07-08T10:58:28.307 に答える
2
再帰は、ある関数を別の関数から呼び出すプロセスに他なりません。このプロセスは、関数自体を呼び出すことによって行われます。私たちが知っているように、ある関数が他の関数を呼び出すと、最初の関数はその状態 (変数) を保存してから、呼び出された関数に制御を渡します。呼び出された関数は、同じ名前の変数を使用して呼び出すことができます。ex fun1(a) は fun2(a) を呼び出すことができます。再帰呼び出しを行うと、新しいことは何も起こりません。1 つの関数は、同じ型で名前が似ている変数 (ただし、変数に格納されている値は明らかに異なり、名前だけが同じままです) を自分自身に渡すことによって自分自身を呼び出します。ただし、すべての呼び出しの前に、関数はその状態を保存し、この保存プロセスが続行されます。保存はスタックで行われます。
今、スタックが登場します。
したがって、反復プログラムを作成し、毎回スタックに状態を保存し、必要に応じてスタックから値をポップアウトすると、再帰プログラムを反復プログラムに正常に変換できます!
証明は単純で分析的です。
再帰ではコンピューターがスタックを維持し、反復バージョンでは手動でスタックを維持する必要があります。
考えてみてください。深さ優先検索（グラフ上）の再帰プログラムをdfs反復プログラムに変換するだけです。
ではごきげんよう！
于 2012-05-18T10:06:16.303 に答える