每个递归函数都能转化为迭代的形式吗?一个递归函数应该具备什么特征,以便可以使用迭代方式实现?
我一直在尝试使用迭代定义以下函数,但似乎行不通!它应该探索迷宫中的所有路径(节点)。有人能否使用迭代重写这个函数?如果不可能,为什么?
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;
}
扩展:是否可以将上述递归函数转换为迭代,而不需要实现自己的堆栈?其中一个答案建议每个尾递归函数都可以被转换为迭代而不使用堆栈结构……如果是这样,那么每个递归函数都可以转换成尾递归吗?如何做到呢?