每个递归函数都可以改写成迭代形式吗？

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

扩展：是否可以将上述递归函数转换为迭代，而不需要实现自己的堆栈？其中一个答案建议每个尾递归函数都可以被转换为迭代而不使用堆栈结构……如果是这样，那么每个递归函数都可以转换成尾递归吗？如何做到呢？

- Saba Ahang

---

请参阅维基百科关于递归与迭代的内容。 - Jonathan Leffler

可能是Can every recursion be converted into iteration?的重复问题。 - thepurpleowl

Answer 1

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

回顾一下编译器是如何使用堆栈（通常在CPU硬件中实现）来实现递归的。您可以构建一个自己的软件堆栈，使其适合保持函数状态（即它的局部变量），将初始状态推入该堆栈，并编写一个while循环，将新状态推入堆栈而不是进行递归调用、弹出堆栈而不是返回，并在堆栈不为空的情况下继续该过程。

- Sergey Kalinichenko

---

我有点不想实现自己的堆栈，将我的函数转换为迭代是否仍然可能？ - Saba Ahang

@SabaAhang 如果递归是“尾递归”（现代编译器会将其作为优化处理），则可以在不使用堆栈的情况下重写递归。对于您特定的问题，堆栈仅是一个由int数组和标量int表示的“堆栈指针”，因此实现堆栈非常容易。 - Sergey Kalinichenko

实际上需要存储两个数字：当前数字和i。 - nhahtdh

Answer 2

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

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

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

整个过程在while循环中完成，在堆栈为空时退出。

- nhahtdh

Answer 3

像其他答案已经提到的那样，模拟堆栈技术上是可以做到的。但我猜你不想那样做。你可能想要一种迭代的解决方案，而不使用堆栈。如果是这样，你需要一个尾递归函数。据我所知，这是唯一可能的方法。你可以将每个尾递归函数重写为非模拟堆栈的命令式函数。

- duedl0r

---

没错！你能告诉我更多关于如何将我的函数转换为尾递归，以便稍后可以使用迭代重写它吗？任何递归都可以转换为尾递归吗？ - Saba Ahang

你不能将每个递归函数转换为尾递归函数。也许对于你的函数来说是可能的，但我还不确定 ;) - duedl0r

该函数是树递归的，因此我认为基本上排除了能够将其转换为使用尾递归而不使用辅助数据结构的可能性。 - jamesdlin

Answer 4

如果您有一个简单的“尾递归”，那么可以使用循环代替（例如阶乘函数）。在更复杂的函数中，您必须使用一个“堆栈”结构和一个“while（！stack.empty（））”循环。但是，如果您有非常复杂的递归，例如汉诺塔，归并排序和打印真值表，则必须使用带有“while”循环的“堆栈”，如前所述，但使用“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<int> st;
  st.push(1);
  int status;

  while (!st.empty())
  {
      status = st.pop();
      switch (status)
      {
        case 1:
             ....
            break;
        case 2:
             break;
      }
  }
}

我强烈推荐这份详细解释了该过程的优秀PDF文件。

- user586399

---

那个函数怎么样？它是尾递归吗？如果不是，它能转换成尾递归吗？怎么做？ - Saba Ahang

@SabaAhang 这并不是非常复杂，也不需要使用尾递归。可以使用栈来实现。我提供的 pdf 很好，你可以从中学习如何使用栈来实现它。 - user586399

Answer 5

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

- Colin 't Hart

---

这段内容有些过于简短了，无法成为一个完整的答案。或许您可以加入更多的评论来补充完善它。 - Joel Cornett