gpt4 book ai didi

能不能把每一个递归都改成迭代呢?

转载 作者:行者123 更新时间:2023-11-30 16:51:29 25 4
gpt4 key购买 nike

每个递归函数都可以转换为迭代吗?递归函数应该具备什么特征才能使用迭代来实现?

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

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

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

最佳答案

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

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

关于能不能把每一个递归都改成迭代呢?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/41753605/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com