每次递归都可以改为迭代吗？

Question

是每一个递归函数转换为迭代？递归函数应该具有什么特性才能使用迭代实现它？

我一直在尝试使用迭代定义以下函数,但似乎是不行!它应该探索迷宫中的所有路径(节点).任何人都可以使用迭代重写这个吗？如果不可能,为什么不呢？

typedef int[0,99] id_t;
bool visited[id_t];
int path[id_t];
int pathCounter = 0;

struct { 
    id_t id;
    bool free;
    int neighborNode[4];
} nodeMap[id_t];

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

扩展:是否可以将提到的递归函数转换为迭代而不实现我自己的堆栈？其中一个答案表明,每个尾递归函数都可以转换为迭代而不使用堆栈结构......如果是这样,每个递归函数是否可以转换为尾递归？怎么样？

Answer 1

是的,每个递归函数都可以通过一个相当机械的过程转换为迭代函数.

回想一下,编译器通过使用堆栈来实现递归,堆栈通常在CPU的硬件中实现.您可以构建自己的软件堆栈,使其适合于保持函数的状态(即其局部变量),将初始状态推送到该堆栈,并编写一个while循环,将新状态推送到堆栈而不是创建递归调用,弹出堆栈而不是返回,并在堆栈不为空时继续进程.

Answer 2

通常可以将任何递归算法转换为循环。方法很简单：我们可以模仿编译器如何生成函数调用的代码：进入函数，从函数返回，继续执行。

要将递归函数转换为迭代循环，您可以：

• 定义一个记录，它存储函数的参数和局部变量。这相当于堆栈帧。
• 定义一个堆栈，记录推送到该堆栈。这类似于程序堆栈。
• 当一个函数被调用时，创建一个参数和局部变量的当前值的记录并压入堆栈。
• 当您从函数返回时，从堆栈中弹出并用记录中的值覆盖当前值。

上面的整个过程是在一个while循环中完成的，当栈为空时会退出，