可以在每次递归改为迭代？(Can every recursion be changed to ite

是每一个递归函数转换为迭代？应该递归函数有什么特点，以便它使用迭代来实现？

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

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

延伸：是否有可能提到的递归函数迭代转换没有实现我自己的堆栈？答案之一提出，每一个尾递归函数可以被转换成迭代，而不使用堆栈结构......如果可以的话，是每一个递归函数转换为尾递归？怎么样？

Answer 1:

是的，每个递归函数可以被转化成由下列一个相当机械过程的迭代之一。

回想一下，编译器通过使用一个堆栈，其通常在CPU的硬件来实现执行递归。你可以建立自己的软件栈，使其适合于保持你的函数的状态（即局部变量），按初始状态到该堆栈，谱写while循环，推动新的状态到堆栈，而不是做的递归调用，出栈，而不是返回，并继续处理而堆栈不为空。

Answer 2:

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

要打开一个递归函数到迭代循环，您可以：

定义一个记录，存储了函数的自变量和局部变量。这等同于堆栈帧。
定义一个栈，到记录推送。这是比喻程序堆栈。
当一个函数被调用时，创建的参数和局部变量的当前值的记录，并推入堆栈。
当你从函数返回，从堆栈弹出并覆盖从记录的当前值。

整个上述过程在while循环完成，当堆栈为空时将退出，

Answer 3:

就像已经指出其他的答案，在技术上可以做到这一点与模拟堆栈。但我猜你不想这样做。你可能希望在不使用堆栈迭代求解。如果是这样的话，你需要有一个尾递归函数。 AFAIR这是唯一可能的方式。你可以重写每一个尾递归函数势在必行一个没有模拟堆栈。

Answer 4:

如果你有一个简单的“尾巴”递归，那么你可以使用一个循环，而不是（如阶乘函数）。在更复杂的功能，你必须使用一个stack结构和while (!stack.empty())循环。不过，如果你有相当复杂的递归，如Towers of Hanoi ， Merge Sort ，并printing truth table ，你将不得不使用一个stack与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其中详细解释的过程。