c - 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システムごとに大きく異なります。一部のOSは、固定量のメインメモリを使用する場合もあれば、スタックの拡張を許可する場合もあります。ページファイルを使用してメモリをスワップして拡張する場合もあり、制限はまったくありません。抽象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;
}

これは、古典的な非再帰的な階乗の実装の1つです。

要約すると、一般的なレシピは次のとおりです。関数の状態をスタックに入れることから始めて、次にリファクタリングを続けます。

Answer 2

関数がノードごとに 1 回呼び出される場合、それぞれ少なくとも7*sizeof(int*)バイトの 875000 スタック フレームが必要になります。32 ビット システムでは、23MB のスタックが必要ですが、これはそれほど多くはありませんが、おそらく定義された制限を超えています。

グラフをたどる反復的なアプローチを考え出す必要があります。基本的に、各構造に「スタック フレーム」が含まれる構造の大きな配列 (サイズ == ノード数) を割り当てる必要があります。あなたの場合、スタック フレームはnodeand でありi、他のすべては渡されるだけで変更されないためです。

再帰が必要なときはいつでも、 と の現在の値を新しい構造体に保存し、nodeそれiを配列に追加します。再帰が終了したら、値を復元します。

Answer 3

コンピュータには特定の量のメモリ（RAMまたはディスク）しかないため、再帰呼び出しの最大数があります。各呼び出しには、関数のデータを保存するためのメモリが必要です。したがって、特定の数の呼び出しのみがメモリに収まります。追加のオペレーティングシステムとプログラミングツールは、スタックサイズを制限します。そのスタックサイズを増やして、使用可能なメモリをより多く使用できる場合がありますが、それは有限のままです。

通常、大きなグラフのグラフアルゴリズムは、グラフに追加情報を追加することで実装されます。たとえば、現在のトラバーサルでアクセスされたかどうかを示すフィールドを各ノードまたはグラフの各エッジに追加したり、そのノードまでにこれまでに見つかった最短パスの長さを指定するフィールドを追加したりできます。次に、スタックを使用する再帰的アルゴリズムとしてではなく、その追加データを使用する反復アルゴリズムとしてアルゴリズムを書き直します。元のグラフを直接拡張できない場合は、追加データを使用して別のグラフを作成できます。

もちろん、追加データは通常、グラフのサイズに比例したスペースを使用します。対数の深さ（グラフのサイズ）など、アルゴリズムの繰り返しがそれより少ない場合は、より少ないスペースを使用するソリューションを見つけることをお勧めします。他の人が示唆しているように、これを行う1つの方法は、アルゴリズムがトラバーサルのさまざまな深さを進むときに、メモリを割り当て、そのメモリにデータを保存することによって再帰の独自のアナログを実装することです。これは理論的には再帰と同等ですが、実際には2つの利点があります。メモリの割り当ては、許可されたスタックスペースを増やすよりも簡単な場合があり、各レベルに保存されるデータの量を直接制御できます。

Answer 4

再帰コードを変換して、自分でヒープに割り当てたスタック データ構造を使用できます。これは単純な再帰よりも難しく、きれいではありませんが、呼び出しスタックのサイズによって制限されないため、より堅牢です。