https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
単純な問題を解決するために長年のプログラミングで再帰をかなり使用しましたが、メモリ/速度の問題のために繰り返しが必要になる場合があることを十分に認識しています。
そのため、非常に過去のある時点で、「パターン」が存在するかどうかを調べてみました。または一般的な再帰アプローチを反復に変換する教科書的な方法で、何も見つかりませんでした。または、少なくとも私が覚えていることは何の助けにもなりません。
- 一般的なルールはありますか
- 「パターン」はありますか？
解決
通常、通常は再帰関数に渡されるパラメーターをスタックにプッシュすることにより、再帰アルゴリズムを反復アルゴリズムに置き換えます。実際、プログラムスタックを独自のものに置き換えています。
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
// Do something
my_object = stack.pop();
// Push other objects on the stack.
}
注：内部に複数の再帰呼び出しがあり、呼び出しの順序を保持する場合は、スタックに逆の順序で追加する必要があります。
foo(first);
foo(second);
に置き換える必要があります
stack.push(second);
stack.push(first);
編集：記事スタックと再帰の除去（または記事のバックアップリンク）でこの件について詳しく説明しています。
他のヒント
実際、最も一般的な方法は、独自のスタックを保持することです。 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;
}
}
明らかに、この例はスタックの境界をチェックしません...そして実際に、左と右の値を与えられた最悪のケースに基づいてスタックのサイズを決めることができます。しかし、あなたはアイデアを得る。
再帰関数が本体内で自分自身を複数回呼び出し、再帰の特定のポイントへの戻りを処理する（つまり、原始再帰ではない）ことについて誰も対処していないようです。 すべての再帰を反復に変換できる、したがって、これは可能であるはずです。
これを行う方法の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();
}
}
再帰呼び出しを行うように努める末尾再帰（最後のステートメントが再帰呼び出しである再帰）。それが得られたら、それを反復に変換するのは一般的に非常に簡単です。
まあ、一般に、再帰は単純にストレージ変数を使用することで反復として模倣できます。再帰と反復は一般に同等であることに注意してください。一方はほとんど常に他方に変換できます。末尾再帰関数は、反復関数に非常に簡単に変換されます。アキュムレータ変数をローカル変数にし、再帰ではなく反復するだけです。 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;
}
私を知って、おそらくコードを間違えたかもしれませんが、アイデアはそこにあります。
スタックを使用しても、再帰アルゴリズムは反復アルゴリズムに変換されません。通常の再帰は関数ベースの再帰であり、スタックを使用するとスタックベースの再帰になります。しかし、それでも再帰です。
再帰アルゴリズムの場合、空間の複雑度はO（N）であり、時間の複雑度はO（N）です。 反復アルゴリズムの場合、空間の複雑さはO（1）であり、時間の複雑さはO（N）です。
しかし、スタックを使用する場合、複雑さに関しては同じままです。末尾再帰のみが反復に変換できると思います。
スタックと再帰の排除この記事では、ヒープ上のスタックフレームを外部化するというアイデアを取り入れていますが、単純で再現性のある変換方法は提供していません。以下に1つを示します。
反復コードへの変換中、再帰呼び出しは任意の深さのコードブロックから発生する可能性があることに注意する必要があります。パラメータだけでなく、実行されずに残っているロジックに戻るポイントと、後続の条件に関与する変数の状態も重要です。以下は、最小限の変更で反復コードに変換する非常に簡単な方法です。
この再帰コードを検討してください：
struct tnode
{
tnode(int n) : data(n), left(0), right(0) {}
tnode *left, *right;
int data;
};
void insertnode_recur(tnode *node, int num)
{
if(node->data <= num)
{
if(node->right == NULL)
node->right = new tnode(num);
else
insertnode(node->right, num);
}
else
{
if(node->left == NULL)
node->left = new tnode(num);
else
insertnode(node->left, num);
}
}
反復コード：
// Identify the stack variables that need to be preserved across stack
// invocations, that is, across iterations and wrap them in an object
struct stackitem
{
stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
tnode *node; int num;
int ra; //to point of return
};
void insertnode_iter(tnode *node, int num)
{
vector<stackitem> v;
//pushing a stackitem is equivalent to making a recursive call.
v.push_back(stackitem(node, num));
while(v.size())
{
// taking a modifiable reference to the stack item makes prepending
// 'si.' to auto variables in recursive logic suffice
// e.g., instead of num, replace with si.num.
stackitem &si = v.back();
switch(si.ra)
{
// this jump simulates resuming execution after return from recursive
// call
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
// replace a recursive call with below statements
// (a) save return point,
// (b) push stack item with new stackitem,
// (c) continue statement to make loop pick up and start
// processing new stack item,
// (d) a return point label
// (e) optional semi-colon, if resume point is an end
// of a block.
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
}
}
v.pop_back();
}
}
コードの構造が再帰的ロジックに忠実であり、修正が最小限であり、バグの数が少ないことに注意してください。比較のために、変更を++および-でマークしました。 v.push_backを除き、新しく挿入されたブロックのほとんどは、変換された反復ロジックに共通です
void insertnode_iter(tnode *node, int num)
{
+++++++++++++++++++++++++
vector<stackitem> v;
v.push_back(stackitem(node, num));
while(v.size())
{
stackitem &si = v.back();
switch(si.ra)
{
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
------------------------
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
-------------------------
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
-------------------------
}
}
+++++++++++++++++++++++++
v.pop_back();
}
-------------------------
}
Googleで＆quot; Continuation Passing Style＆quot;を検索します。末尾再帰スタイルに変換する一般的な手順があります。末尾再帰関数をループに変換する一般的な手順もあります。
時間をつぶすだけ...再帰関数
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);
}
}
一般に、スタックオーバーフローを回避する手法は、再帰関数であり、Java開発者によって広く採用されているトランポリン手法と呼ばれます。
ただし、C＃には小さなヘルパーメソッドこちらを使用すると、ロジックを変更したり、コードを理解しやすくしたりすることなく、再帰関数を反復的に変更できます。 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);
}
実際にスタックが必要なものを考える：
再帰のパターンを次のように考えた場合：
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 オブジェクトのリストにすることができます。または、反対の方向に進み、より単純なタイプのリストにすることができます（たとえば、「タスク」は、のスタック上の1つの要素ではなく、）。 int のスタック上の4つの要素です。タスク
これはつまり、スタックのメモリがJava実行スタックではなくヒープ内にあることを意味しますが、これはより詳細に制御できるという点で役立ちます。
検索するパターンの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回目の再帰呼び出しを排除します。
私は正しい答えであり、一般的な適用性があると思う明示的なスタックを使用することを示唆する答えを支持しました。
つまり、再帰関数を反復関数に変換するために使用できるということです。再帰呼び出しで保存される値を確認するだけです。これらは、再帰関数に対してローカルである もので、呼び出しをスタックにプッシュするサイクルに置き換えます。スタックが空の場合、再帰関数は終了していました。
すべての再帰関数が異なるデータ型の反復関数と同等であるという証拠は否定できません。それは大学時代の最も大切な記憶の1つです。それが、コンピュータプログラミングが何であるかを本当に理解させたコース（および教授）でした。
このの複製として閉じられた質問は、非常に具体的なデータ構造を持っていました：
ノードの構造は次のとおりです。
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回）呼び出す再帰関数のスタックを常に回避できるとは限りません。ただし、この特定の構造については可能です。アイデアは、すべてのノードを単一のリストにフラット化することです。これは、現在のノードの 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に還元できる任意のデータリンク構造に適用できます。現在のノードの子は、最後の子が他のすべての子を採用するように再配置されます。その後、現在のノードを削除し、トラバーサルで残りの子を反復処理できます。
再帰は、1つの関数を他の関数から呼び出すプロセスに他なりません。このプロセスのみが、関数を単独で呼び出すことによって実行されます。ある関数が他の関数を呼び出すとわかるように、最初の関数はその状態（変数）を保存してから、呼び出された関数に制御を渡します。呼び出された関数は、同じ名前の変数を使用して呼び出すことができます。例fun1（a）はfun2（a）を呼び出すことができます。 再帰呼び出しを行うと、新しいことは何も起こりません。 1つの関数は、同じ型および類似の名前変数（ただし、変数に格納されている値が異なるため、名前のみが同じままである）を自分自身に渡すことで、それ自体を呼び出します。ただし、関数を呼び出すたびに状態が保存され、この保存プロセスが続行されます。スタックの保存が完了しました。
スタックがプレイされるようになりました。
したがって、反復プログラムを作成し、毎回スタックに状態を保存し、必要なときにスタックから値をポップアウトすると、再帰プログラムが反復プログラムに正常に変換されました！
証明は単純で分析的です。
再帰では、コンピューターはスタックを維持し、反復バージョンではスタックを手動で維持する必要があります。
考え直して、深さ優先検索（グラフ上）再帰プログラムをdfs反復プログラムに変換するだけです。
最高！
システムがどのように再帰関数を取り、スタックを使用して実行するかの大まかな説明：
これは、詳細なしでアイデアを示すことを目的としています。グラフのノードを印刷するこの関数を考えてみましょう：
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
グラフの例： A-＆gt; B A-＆gt; C show（A）はB、A、Cを出力します
関数呼び出しは、ローカル状態と継続ポイントを保存することを意味するため、戻って、呼び出したい関数をジャンプできます。
たとえば、show（A）の実行が開始されたとします。 3行目の関数呼び出しは、show（B）が意味する -スタックにアイテムを追加します。「ローカル変数state node = A」で行2に進む必要があります。 -node = Bで行0に移動します。
コードを実行するために、システムは指示を実行します。関数呼び出しが発生すると、システムは元の場所に戻るために必要な情報をプッシュし、関数コードを実行し、関数が完了すると、続行する必要がある場所に関する情報をポップします。
このリンクいくつかの説明を提供し、「場所」を維持するというアイデアを提案します。いくつかの再帰呼び出しの間の正確な場所に到達できるようにするために：
ただし、これらの例はすべて、再帰呼び出しが fixed 回数行われるシナリオを説明しています。次のようなものがあると、物事が複雑になります。
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
複数の反復子サプライヤを連結する遅延反復子（反復子を返すラムダ式）を使用して、再帰トラバーサルを反復子に変換する一般的な方法があります。 再帰的トラバーサルのイテレータへの変換を参照してください。
スタックを使用して再帰関数を反復関数に変換する別の簡単で完全な例。
#include <iostream>
#include <stack>
using namespace std;
int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};
int GCDIter(int a, int b)
{
stack<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
