使用您自己制作的堆栈将非尾递归函数转换为迭代函数时,处理递归调用(即尾)之后的代码部分的一般方法是什么?
以下函数应该探索迷宫中所有可能的路径,重新访问预先访问的路径以访问堆栈中的其他路径:
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++;
似乎不适合该方法的迭代版本!有一个通用的方法吗?还是每个案例都不一样?无论如何,你有什么建议如何在这种情况下实现尾部?