每次递归都可以改为迭代吗？ [英] Can every recursion be changed to iteration?

问题描述

每个递归函数是否可以转换为迭代？递归函数应该具有哪些特性才能使用迭代实现？

Is every recursive function convertible to iteration? What characteristic should a recursive function have in order for it to be implemented using iteration?

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

I've been trying to define the following function using iteration but seems like a no-go! It is supposed to explore all the paths (nodes) in a maze. Can anyone rewrite this using iterations? If it is not possible, why not?

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

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

Extension: Is it possible to convert the mentioned recursive function to iteration without implementing my own stack? One of the answers suggested that every tail recursive function can be converted to iteration without using a stack structure...if that's so, is every recursive function convertible to tail recursion? How?

推荐答案

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

Yes, every recursive function can be converted to an iterative one by following a rather mechanical process.

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

Recall that compilers implement recursion by using a stack, which is typically implemented in the CPU's hardware. You can build a software stack of your own, make it suitable for keeping the state of your function (i.e. its local variables), push the initial state onto that stack, and write a while loop that pushes new state onto the stack instead of making a recursive call, popping the stack instead of returning, and continuing the process while the stack is not empty.

这篇关于每次递归都可以改为迭代吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！