Stackoverflow:递归调用太多了？在C.

Question

我正在尝试通过一个巨大的图形(大约875000个节点和5200000个边缘),但我得到了一个stackoverflow.我有一个递归函数来循环它.它将仅探索未探索的节点,因此无法进入无限递归.(或者至少我认为)我的递归函数适用于较小的输入(5000个节点).

我该怎么办？是否有最大数量的成功递归调用？

我真的很无能为力.

编辑:我也在最后发布了迭代等价物.

这是递归的代码:

int main()
{
int *sizeGraph,i,**reverseGraph;
// some code to initialize the arrays
getGgraph(1,reverseGraph,sizeGraph); // populate the arrays with the input from a file

getMagicalPath(magicalPath,reverseGraph,sizeGraph);

return 0;
}

void getMagicalPath(int *magicalPath,int **graph,int *sizeGraph) {
    int i;
    int *exploredNode;
    /* ------------- creation of the list of the explored nodes ------------------ */
    if ((exploredNode =(int*) malloc((ARRAY_SIZE + 1) * sizeof(exploredNode[0]))) == NULL) {
        printf("malloc of exploredNode error\n");
        return;
    }
    memset(exploredNode, 0, (ARRAY_SIZE + 1) * sizeof(exploredNode[0]));

    // start byt the "last" node
    for (i = ARRAY_SIZE; i > 0; i--) {
        if (exploredNode[i] == 0)
            runThroughGraph1stLoop(i,graph,exploredNode,magicalPath,sizeGraph);
    }
    free(exploredNode);
}

/*
 *      run through from the node to each adjacent node which will run to each adjacent node etc...
 */
void runThroughGraph1stLoop(int node,int **graph,int *exploredNode,int *magicalPath,int *sizeGraph) {
    //printf("node = %d\n",node);
    int i = 0;
    exploredNode[node] = 1;
    for (i = 0; i < sizeGraph[node]; i++) {
        if (exploredNode[graph[node][i]] == 0) {
            runThroughGraph1stLoop(graph[node][i],graph,exploredNode,magicalPath,sizeGraph);
        }
    }
    magicalPath[0]++; // as index 0 is not used, we use it to remember the size of the array; quite durty i know
    magicalPath[magicalPath[0]] = node;
}

以上的迭代等价物:

struct stack_t { 
        int node;
        int curChildIndex;
    };

void getMagicalPathIterative(int *magicalPath,int **graph,int *sizeGraph) {
    int i,k,m,child,unexploredNodeChild,curStackPos = 0,*exploredNode;
    bool foundNode;
    stack_t* myStack;
    if ((myStack    = (stack_t*) malloc((ARRAY_SIZE + 1) * sizeof(myStack[0]))) == NULL) {
        printf("malloc of myStack error\n");
        return;
    }
    if ((exploredNode =(int*) malloc((ARRAY_SIZE + 1) * sizeof(exploredNode[0]))) == NULL) {
        printf("malloc of exploredNode error\n");
        return;
    }
    memset(exploredNode, 0, (ARRAY_SIZE + 1) * sizeof(exploredNode[0]));

    for (i = ARRAY_SIZE; i > 0; i--) {
        if (exploredNode[i] == 0) {
            curStackPos = 0;
            myStack[curStackPos].node = i;
            myStack[curStackPos].curChildIndex = (sizeGraph[myStack[curStackPos].node] > 0) ? 0 : -1;

            while(curStackPos > -1 && myStack[curStackPos].node > 0) {
                exploredNode[myStack[curStackPos].node] = 1;
                if (myStack[curStackPos].curChildIndex == -1) {
                    magicalPath[0]++;
                    magicalPath[magicalPath[0]] = myStack[curStackPos].node; // as index 0 is not used, we use it to remember the size of the array
                    myStack[curStackPos].node = 0;
                    myStack[curStackPos].curChildIndex = 0;
                    curStackPos--;
                }
                else {
                    foundNode = false;
                    for(k = 0;k < sizeGraph[myStack[curStackPos].node] && !foundNode;k++) {
                        if (exploredNode[graph[myStack[curStackPos].node][k]] == 0) {
                            myStack[curStackPos].curChildIndex = k;
                            foundNode = true;
                        }
                    }
                    if (!foundNode)
                        myStack[curStackPos].curChildIndex = -1;

                    if (myStack[curStackPos].curChildIndex > -1) {
                        foundNode = false;
                        child = graph[myStack[curStackPos].node][myStack[curStackPos].curChildIndex];
                        unexploredNodeChild = -1;
                        if (sizeGraph[child] > 0) { // get number of adjacent nodes of the current child
                            for(k = 0;k < sizeGraph[child] && !foundNode;k++) {
                                if (exploredNode[graph[child][k]] == 0) {
                                    unexploredNodeChild = k;
                                    foundNode = true;
                                }
                            }
                        }
                        // push into the stack the child if not explored
                        myStack[curStackPos + 1].node = graph[myStack[curStackPos].node][myStack[curStackPos].curChildIndex];
                        myStack[curStackPos + 1].curChildIndex = unexploredNodeChild;
                        curStackPos++;
                    }
                }
            }
        }
    }
}

Answer 1

通常,您不应该依赖太深的递归.不同的平台处理方式不同,但通常大致如下:

max number of recursion = stack memory / function state

该stack memory变量是因系统非常不同.某些操作系统可能只使用固定数量的主内存,其他操作系统可能允许不断增长的堆栈,有些可能会使用页面文件和交换内存来增长,并且根本没有限制.作为具有抽象C标准的C程序员,您不能依赖任何东西.

所以你可以先优化函数状态(去掉变量,使用较小的整数等).但这可能不是真正的解决方案.

• 一些编译器识别尾递归并将递归转换为迭代.但同样,这不是可以依赖的东西(C标准不保证它;你可以依赖它的语言是Common LISP).另请参阅C++是否限制递归深度？作为一个相关的问题.

• 编译器可以提供设置递归限制的选项.但是再一次,如果你的深度在设计上实际上是无限的,那就不应该依赖它.

但真正的解决方案是手动将递归转换为迭代.最简单的方法是将所有函数内部数据存储在堆栈中并手动模拟递归:

int fac(int x) {
    if (x<=1) return 1;
    return x*fac(x-1);
}

To(Pcode告诉你):

int fac(int x_) {
    struct state_t { 
        int x;
        int ret;
    }; // <-- all parameters and local variables would go here in the beginning
    struct stack_of_state_t {...};
    stack_of_state_t stack;

    push(stack, {x_, 1});

    while (1) {
        if (top(stack).x<=1) return top(stack).ret;
        push(stack, {x-1, (top(stack).x) * top(stack).ret});            
    }
}

虽然这通常比递归更好,但这可能不是最聪明的解决方案,您应该开始确定哪个状态真的必须保存.

在我们的例子中,我们发现我们总是只需要堆栈的顶部,所以我们立即再次摆脱堆栈:

int fac(int x) {    
    int ret = 1;
    while (1) {
        if (x<=1) return ret;
        ret = x * ret;
        x = x-1;
    }
}

并使它更美丽:

int fac(int x) {    
    int ret = 1;
    while (x>1)
        ret *= x--;
    return ret;
}

这是一个经典的,非递归的阶乘实现.

总而言之,一般方法:首先将函数的状态放入堆栈,然后继续重构.

Answer 2

如果每个节点调用一次该函数,则需要875000个堆栈帧7*sizeof(int*),每个堆栈帧至少有一个字节.在32位系统上,需要23MB的堆栈,这个堆栈并不多,但可能超出了定义的限制.

您需要提出一种迭代方法来处理图表.基本上,您需要分配一个大型数组(size ==个节点数)的结构,其中每个结构都包含"堆栈帧".在你的情况,堆栈帧node和i,因为其他一切都只是传来传去,并不会改变.

每当你需要递归,你保存的当前值node,并i在一个新的结构,并追加到数组中.递归结束时,恢复值.