每次递归都可以改成迭代吗? [英] 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.

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屋！