4

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

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

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

扩展：是否可以在不实现我自己的堆栈的情况下将提到的递归函数转换为迭代？其中一个答案表明，每个尾递归函数都可以在不使用堆栈结构的情况下转换为迭代......如果是这样，每个递归函数都可以转换为尾递归吗？如何？

4

5 回答 5

7

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

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

于 2012-07-29T11:48:37.943 回答
5

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

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

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

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

于 2012-07-29T11:50:37.100 回答
3

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

于 2012-07-29T12:32:59.533 回答
0

如果您有一个简单的“尾”递归，那么您可以使用循环代替（例如阶乘函数）。在更复杂的函数中，您必须使用stack结构和while (!stack.empty())循环。但是，如果您有相当复杂的递归，例如Towers of Hanoi、Merge Sort和printing truth table，您将不得不使用stackwithwhile循环，如前所述，但使用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，它详细解释了这个过程。

于 2012-07-29T12:39:52.853 回答
-3

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

于 2012-07-29T11:37:12.953 回答