c - 将非尾递归函数转换为迭代函数时处理其尾部部分

Question

当使用您自己制作的堆栈将非尾部递归函数转换为迭代函数时，处理递归调用之后的代码部分(即尾部)的一般方法是什么？

以下函数应该探索迷宫中所有可能的路径，重新访问预先访问过的路径以便访问堆栈中的其他路径:

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来模仿循环的索引，因为它没有保存在堆栈中，并且需要处理所有 children ):

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++ ; 似乎不适合该方法的迭代版本! 有没有通用的方法？还是每个情况都不一样？无论如何，您对如何在这种情况下实现尾部有什么建议吗？

Answer 1

使用尾递归函数，堆栈解决方案非常简单，但正如您的示例所示，由于您在递归调用后执行某些操作，因此您需要找出一种方法来在调用结束后执行这些操作。

以下是可能的解决方案:

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);
            }
    }
}

这基本上所做的就是访问每个节点两次。一次是在展开时，此时您执行递归调用之前的内容，另一次是在其所有子级完成处理后，此时您执行递归调用之后的内容递归调用。

请注意，您可能需要保存一些状态，例如 cc 和 current 以及节点，以便您能够执行 if (e.expanded) 部分正确。

---

侧面建议:像在递归方法中那样使用for循环，这比使用toProcess更清晰。

---

在您的情况下，对一个子分支的执行会影响访问或不访问其他子分支，您可以遵循以下方法:

每次获取节点时，检查它是否满足必要的条件。如果是，则在调用该节点之前进行处理。然后像以前一样，再次推送它，以便再次访问它并完成后处理。这样，每次你只是插入 children ，然后再决定他们好不好:

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 的存在，它是一个全局变量。如果您有一个不使用全局变量的递归函数，转换会更简单。