0

再帰的なバックトラッキングが必要な問題を解決しようとしていますが、私のソリューションではスタックオーバーフロー エラーが発生します。このエラーは多くの場合、不適切な終了条件を示していることは理解していますが、私の終了条件は正しいようです。スタックオーバーフローエラーを引き起こす可能性がある悪い終了条件以外に何かありますか? 問題が何であるかをどのように把握できますか？

編集:申し訳ありませんが、コードを投稿しようとしましたが、あまりにも醜い..

4

6 に答える 6

6

@irreputable が言うように、コードに正しい終了条件がある場合でも、スタックに対して問題が大きすぎる可能性があります (そのため、条件に達する前にスタックが使い果たされます)。3 つ目の可能性もあります。再帰がループに入っている可能性です。たとえば、グラフの深さ優先検索では、ノードを訪問済みとしてマークするのを忘れると、円を描いて、既に見たノードを再訪問することになります。

これら 3 つの状況のうち、自分がどの状況にいるかをどのように判断できますか? 各再帰呼び出しの「場所」を記述する方法を作成してみてください (これには通常、関数パラメーターが含まれます)。たとえば、関数が隣接するノードで自分自身を呼び出すグラフ アルゴリズムを作成している場合、ノード名またはノード インデックスは、再帰関数がどこにあるかを適切に説明します。再帰関数の先頭に説明を表示すると、その関数が何をするかがわかります。おそらく、その関数が正しいことを行っているかどうか、または循環しているかどうかがわかります。サークルに入ったかどうかを検出するために、説明を HashMap に保存することもできます。

于 2011-06-07T22:41:53.843 に答える
3

再帰を使用する代わりに、スタックを使用するループを常に使用できます。たとえば、（疑似コード）の代わりに：

function sum(n){
  if n == 0, return 0
  return n + sum(n-1)
}

使用する：

function sum(n){
  Stack stack
  while(n > 0){
    stack.push(n)
    n--
  }
  localSum = 0
  while(stack not empty){
    localSum += stack.pop()
  }
  return localSum
}

簡単に言うと、状態をローカル スタックに保存して再帰をシミュレートします。

于 2011-06-07T23:04:51.590 に答える
1

問題が大きすぎてデフォルトのスタック制限サイズで修正できない場合は、-Xssオプションを使用してスタックにより多くのメモリを与えることができます。

于 2011-06-07T22:44:19.950 に答える
1

他の仲間がすでに述べたように、それにはいくつかの理由があるかもしれません:

  • あなたのコードには、本質的に、または再帰のロジックに問題があります。これは、再帰関数の停止条件、基本ケース、または終了点でなければなりません。

  • メモリが小さすぎて、再帰呼び出しの数をスタックに保持できません。ここでは、大きなフィボナッチ数が良い例かもしれません。参考までに、フィボナッチは次のとおりです (ゼロから始まる場合もあります)。

    1,1,2,3,5,8,13,...

    Fn = Fn-1 + Fn-2

    F0 = 1、F1 = 1、n>=2

于 2015-02-05T23:45:49.550 に答える
0

プログラムが無限ループに陥る (したがって、スタック オーバーフローが発生する) 可能性がある一般的なコーディング エラーが2 つあります。

  • 終了条件が悪い
  • 不正な再帰呼び出し

例：

public static int factorial( int n ){
    if( n < n ) // Bad termination condition
        return 1;
    else
        return n*factorial(n+1); // Bad recursion call
}

そうしないと、プログラムが正常に機能しているだけで、スタックが小さすぎる可能性があります。

于 2011-06-07T23:20:44.220 に答える
0

コードが正しければ、問題に対してスタックが小さすぎるということです。本物のチューリングマシンはありません。

于 2011-06-07T22:36:47.513 に答える