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

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来模拟循环的索引，因为它没有保存在堆栈中，并且需要处理所有子项）：

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

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

请注意，您可能需要保存一些状态，例如 Maybecc和current连同节点，以便您能够if (e.expanded)正确完成该部分。

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

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

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

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