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

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 循环来压入新的状态入栈而不是进行递归调用，出栈而不是返回，并在栈不为空时继续该过程。