4

我正在尝试查看一个巨大的图表（大约 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++;
                    }
                }
            }
        }
    }
}
4

4 回答 4

7

通常你不应该依赖太深的递归。不同平台的处理方式不同，但一般大致是这样的：

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

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

这是经典的非递归阶乘实现之一。

总而言之，一般的秘诀是：首先将函数的状态放入堆栈，然后继续重构。

于 2012-08-02T12:37:10.937 回答
5

如果每个节点调用一次该函数，您将需要 875000 个堆栈帧，每个堆栈帧至少包含7*sizeof(int*)字节。在 32 位系统上，这需要 23MB 的堆栈，虽然不多，但可能超出了定义的限制。

您将需要提出一种迭代方法来遍历您的图表。基本上，您需要分配一个大型结构数组（大小 == 节点数），其中每个结构都包含“堆栈帧”。在您的情况下，堆栈框架是node并且i因为其他所有内容都只是传递并且不会改变。

node每当需要递归时，将和的当前值保存i在一个新结构中并将其附加到数组中。当递归结束时，恢复这些值。

于 2012-08-02T12:27:24.993 回答
1

您可以将递归代码转换为使用您自己在堆上分配的堆栈数据结构。这比直接递归更困难，也更不干净，但它更健壮，因为它不受调用堆栈大小的限制。

于 2012-08-02T12:26:59.113 回答
1

由于您的计算机只有一定数量的内存（无论是 RAM 还是磁盘），因此存在最大数量的递归调用。每次调用都需要一些内存来保存函数的数据。所以只有一定数量的调用可以容纳在内存中。此外，操作系统和编程工具限制堆栈大小。您也许可以增加该堆栈大小以使用更多可用内存，但它仍然是有限的。

通常，大型图的图算法是通过使用附加信息扩充图来实现的。例如，您可以为每个节点或图形的每条边添加一个字段，指示它是否在当前遍历中被访问过，或者您可以添加一个字段，指定到目前为止找到的最短路径到该节点的长度。然后，您将算法重写为使用该附加数据的迭代算法，而不是使用堆栈的递归算法。如果您无法直接扩充原始图，则可以使用附加数据构建单独的图。

当然，附加数据通常使用与图表大小成比例的空间。如果您的算法递归少于此，例如到日志深度（图的大小），那么您可能希望找到使用更少空间的解决方案。正如其他人所建议的那样，执行此操作的一种方法是分配内存并通过在算法通过各种深度遍历时将数据保存在该内存中来实现您自己的递归模拟。这在理论上等效于递归，但在实践中它有两个优点：分配内存可能比增加允许的堆栈空间更容易，并且它可以让您直接控制每个级别存储多少数据，

于 2012-08-02T12:35:20.690 回答