2

独自に作成したスタックを使用して非末尾再帰関数を反復関数に変換する場合、再帰呼び出しの後に来るコードの部分、別名末尾を処理する一般的な方法は何ですか?

次の関数は、迷路内のすべての可能なパスを探索し、スタック内の他のパスにアクセスするために、以前にアクセスしたパスに再アクセスすることになっています。

struct node{
    int id;
    bool free;
    int neighborNode[4];
    int toProcess;
} nodeMap[100];

void findPath(int current){
    visited[current] = true;
    int i;
    for (i=0; i < 4; i++){
       if(nodeMap[nodeMap[current].neighborNode[i]].free == true && visited[nodeMap[current].neighborNode[i]] == false && nodeMap[current].neighborNode[i] != -1){
        path[cc] = nodeMap[nodeMap[current].neighborNode[i]].id;
        cc++;
        findPath(nodeMap[current].neighborNode[i]);
        path[cc] = nodeMap[current].id;
        cc++;
        }
    }
}

コードの再帰部分は反復に簡単に変換できます (toProcessスタックに保存されず、すべての子を処理するために必要なループのインデックスを模倣するためにフィールドを使用しました)。

void findPath(){
    if (isEmpty())
        return;
    else {
        node temp = pop();
        visited[temp.id] = true;
        if (temp.toProcess < 3) {
            temp.toProcess++;
            push(temp);
            temp.toProcess--;
        }
        if(nodeMap[temp.neighborNode[temp.toProcess]].free == true && visited[temp.neighborNode[temp.toProcess]] == false && temp.neighborNode[temp.toProcess] != -1){
            path[cc] = nodeMap[temp.neighborNode[temp.toProcess]].id;
            cc++;
            push(nodeMap[temp.neighborNode[temp.toProcess]]);
        }
    }
}

しかし、アルゴリズムが逆方向に移動して以前に見たノードを再訪し、他の可能なパス (テール) を探索する部分、つまりpath[cc] = nodeMap[current].id;&cc++;はメソッドの反復バージョンには適合しないようです! これに対する一般的なアプローチはありますか?それともケースごとに違う?とにかく、この場合にテール部分を実装する方法について何か提案はありますか?

4

2 に答える 2

4

スタックソリューションは末尾再帰関数を使用すると便利で簡単ですが、例のように、再帰呼び出しの後に何かを実行しているため、呼び出しの終了後にこれらの操作を実行する方法を理解する必要があります。

考えられる解決策は次のとおりです。

struct stack_element
{
    ... your_stuff...
    bool expanded;
};

コード内:

stack_element e;
... fill e
e.expanded = false;
push(e);
while (!empty())
{
    e = pop();
    if (e.expanded)
    {
        ... do the stuff that was supposed to be done
        ... after e and all its children are processed
    }
    else
    {
        e.expanded = true;
        push(e);               // push e, so it would be visited again
                               // once all children are processed
        for (every child of e)
            if (they met the conditions)
            {
                ... do the stuff before
                stack_element child;
                ... fill child
                child.expanded = false;
                push(child);
            }
    }
}

これは基本的に、各ノードに2回アクセスします。一度展開すると、再帰呼び出しの前に実行し、もう1回はすべての子の処理が終了したら、再帰呼び出しのに実行します。

パーツを正しく実行できるように、ノードccなどの一部の状態を保存する必要がある場合があることに注意してください。currentif (e.expanded)


副次的な提案:for再帰的方法で行ったようにループを使用します。これは、を使用するよりも明確ですtoProcess


あなたの場合、子供たちの1つのブランチでの実行が他のブランチを訪問するかしないかに影響する場合、次のアプローチに従うことができます。

ノードを取得するたびに、ノードが必要な条件を満たしているかどうかを確認してください。含まれている場合は、そのノードを呼び出す前に処理を実行します。次に、前と同じように、もう一度押して、再度アクセスして後処理を実行します。このように、あなたが子供たちを押すたびに、後で彼らが良いかどうかを決定します:

struct stack_element
{
    ... your_stuff...
    bool expanded;
    ... save also cc, current and i
};

stack_element e;
... fill e
e.expanded = false;
push(e);
while (!empty())
{
    e = pop();
    if (e.expanded)
    {
        ... do the stuff that was supposed to be done
        ... when function called with e is returning and
        ... after the function returns to parent
    }
    else if (conditions for are met)
    {
        ... do the stuff that was supposed to be done before
        ... e is recursively called and at the beginning of the
        ... function
        e.expanded = true;
        push(e);               // push e, so it would be visited again
                               // once all children are processed
        for (every child of e, in reverse order)
        {
            stack_element child;
            ... fill child
            child.expanded = false;
            push(child);
        }
    }
}

正確なコードを確認した後、変換されたバージョンは次のとおりです。

struct stacknode{
    int id;
    int parent;
    bool free;
    bool expanded;
};

int cc = 0;

void findPath2(int current){

    // special case for the first call:
    visited[current] = true;

    // expand the first node, because when the first node is popped,
    // there was no "stuff before recursion" before it.
    int i;
    for (i=3; i >= 0; --i){
        // Put the neighbors on the stack so they would be inspected:
        stacknode child;
        child.id = nodeMap[current].neighborNode[i];
        child.parent = current;
        child.free = nodeMap[child.id].free;
        child.expanded = false;
        push(child);
    }

    while (!isEmpty())
    {
        stacknode cur = pop();
        if (cur.expanded == true)
        {
            // Now, it's like a return from a recursive function
            // Note: cur.id will be nodeMap[current].neighborNode[i] because that was the value the function was called with
            // Stuff at the end of the function:
            path[0]=current;    // Note: this is kind of absurd, it keeps getting overwritten!
            // Stuff after recursion:
            cc++;  // note that path[0] is reserved for first node, so you should first increment cc, then set path[cc]
            path[cc] = nodeMap[cur.parent].id;  // nodeMap[current].id: current was the parent of
                                // nodeMap[current].neighborNode[i] for which the function was called
        }
        else
        {
            // Now, it's like when the recursive function is called (including stuff before recursion)
            // Note: cur.id will be nodeMap[current].neighborNode[i] because that was the value the function was called with
            // Check whether child was supposed to be added:
            if(cur.id != -1 && nodeMap[cur.id].free == true && visited[cur.id] == false)
                // Node: Put cur.id != -1 in the beginning. Otherwise, you would possibly check
                // nodeMap[-1] and visited[-1] which is not nice
            {
                cur.expanded = true;
                push(cur);
                // Stuff before recursion:
                cc++;
                path[cc] = nodeMap[cur.id].id;      // in cur.id, nodeMap[current].neighborNode[i] was stored
                // Stuff at the beginning of function call:
                visited[cur.id] = true;
                // The body of the function:
                for (i=3; i >= 0; --i){
                    // Put the neighbors on the stack so they would be inspected:
                    stacknode child;
                    child.id = nodeMap[cur.id].neighborNode[i];
                    child.parent = cur.id;
                    child.free = nodeMap[child.id].free;
                    child.expanded = false;
                    push(child);
                }
            }
        }
    }
    // end of special case for first call:
    path[0] = current;
}

それが複雑になり始める理由は、その存在がccグローバル変数であることに注意してください。グローバル変数を使用しない再帰関数があれば、変換はもっと簡単だったでしょう。

于 2012-07-31T09:27:36.597 に答える
1

再帰を反復に変換する一般的な方法は、スタックからイベントを繰り返しポップしてそのハンドラーを実行する一種のイベント ループを使用することです。最初に、再帰関数に似た疑似コードをいくつか書きます。これにより、変換が理解しやすくなります。

recurse (node)
{
    for (i = 0; i < 4; i++) {
        if (condition(node, i)) {
            recurse(next_node(node, i));
        }
    }
}

ここで行うことは、この再帰関数を一連の操作に分割することですが、明示的に記述する代わりに、各操作をイベントとそれに対応するイベント ハンドラーとして定義し、この操作の後にさらに作業が必要な場合に備えて、ハンドラーは、操作を実行する前に、この追加作業をスタックにプッシュします。

my_iterative_function ()
{
    // build the event stack and push the initial event
    EventStack stack;
    stack.push(NewRecurseEvent(node = first_node));

    // pop and execute events
    while (!stack.isEmpty()) {
        Event ev = stack.pop();
        ev.executeHandler();
    }
}

RecurseEventHandler (node)
{
    // We are at the beginning of the "recurse" function.
    // Push iteration 0 (we could optimize this and just do it here).
    stack.push(NewIterationEvent(node = node, i = 0));
}

IterationEventHandler (node, i)
{
    // Unless this is the last iteration, push the next iteration
    // to be executed after this iteration is complete. It will work
    // with the same node, but 'i' one greater.
    if (i < 3) {
        stack.push(NewIterationEvent(node = node, i = i + 1));
    }

    // do the work of this iteration
    if (condition(node, i)) {
        # Initiate the recursion by pushing.
        # It is crutial to understand that the event loop will pop this event,
        # and all events pushed by it, recursively, before
        # popping the continuation event we pushed above.
        # That is, it will behave just like the recursive variant.
        stack.push(NewRecurseEvent(node = next_node(node, i)));
    }
}

この疑似コードを実際に実装する方法は、言語によって異なります。C では、イベント オブジェクトは、さまざまなイベント ハンドラーへの引数を保持するタグ付きユニオンにすることができ、イベント ループにイベント ハンドラー アクションを直接実行させることができます。

struct event {
    int type; // RECURSE_EVENT or ITERATION_EVENT
    union {
        struct {
            node node;
        } recurse_event;
        struct {
            node node;
            int i;
        } iteration_event;
    };
};

while (!stack.isEmpty()) {
    struct event ev = stack.pop();
    switch (ev.type) {
        case RECURSE_EVENT: {
            node n = ev.recurse_event.node;
            ...
        } break;
        case ITERATION_EVENT: {
            node n = ev.iteration_event.node;
            int i = ev.iteration_event.i;
            ...
        } break;
    }
}

実際の再帰関数は、再帰呼び出しに続く部分があるため、私の単純な例よりも複雑であるため、これを処理するにはより多くのイベントが必要になります。たとえば、再帰後のステップを処理する別の種類のイベントを追加できます。

IterationEventHandler (node, i)
{
    if (i < 3) {
        stack.push(NewIterationEvent(node = node, i = i + 1));
    }

    if (condition(node, i)) {
        // This PostEvent will be executed after the recursive work,
        // but before the next iteration pushed above.
        stack.push(NewPostEvent(node = node, i = i));
        stack.push(NewRecurseEvent(node = next_node(node, i)));
    }
}

PostEventHandler (node, i)
{
    // do your post-recursion work here
}

これは、1 つのイベント ハンドラーを見ると、プッシュされたときとは逆の順序ですべての作業が実行されることを考えると、簡単に理解できます。たとえば、IterationEventHandler上記では、最初に再帰が実行され、次に再帰後のステップが実行され、最後に次の反復ステップが開始されます (ある場合)。さらに簡単に言えば、各プッシュは再帰的な関数呼び出しとして理解できますが、これらの呼び出しはボトムアップで実行されます。

これは一般的なアプローチであることに注意してください。再帰関数をそのようなイベントループに変換するコンパイラを構築することはおそらく可能です。また、このアプローチは、再帰を反復に変換するエレガントな方法であるだけではありません。「スタックイベントループ」のアイデアは、イベント駆動型ソフトウェアの設計において非常に実用的です。特に、プッシュされたがまだ実行されていないイベントをデキューする機能がある場合はそうです。これについては、この質問への回答で説明しました。

于 2012-07-31T11:52:49.920 に答える