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

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

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

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循环,将新状态推送到堆栈而不是制作递归调用,弹出堆栈而不是返回,并在堆栈不为空时继续进程。

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

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

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

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

与已经陈述的其他答案一样,技术上可以通过模拟堆栈来实现。 但我猜你不想这样做。 您可能想要一个不使用堆栈的迭代解决方案。 如果是这种情况,你需要有一个尾递归函数。 AFAIR是唯一可行的方式。 您可以将每个尾递归函数重写为命令式函数,而无需模拟堆栈。

如果你有一个简单的“尾部”递归,那么你可以使用一个循环(例如阶乘函数)。 在更复杂的函数中,您必须使用stack结构和while (!stack.empty())循环。 但是,如果您有非常复杂的递归,例如Towers of HanoiMerge Sortprinting truth table ,则必须使用带有while循环的stack ,如前所述,但使用switch语句来确定调用的当前状态。

递归:

 void mergeSort(int start, int end) { if (start < end) { mergeSort(start, (start + end) / 2); mergeSort((start + end) / 2 + 1, end); Merge(start, end); } } 

迭代:

 void mergeSort() { stack st; st.push(1); int status; while (!st.empty()) { status = st.pop(); switch (status) { case 1: .... break; case 2: break; } } } 

我强烈推荐这个优秀的pdf ,详细解释了这个过程。

根据http://en.wikipedia.org/wiki/Recursion_%28computer_science%29#Recursion_versus_iteration,所有递归定义的函数都可以转换为迭代函数。