7

私の質問は、複雑な再帰アルゴリズムをデバッグするスマートな方法があるかどうかです。複雑なものがあると仮定します (「ネストされた反復」ごとに再帰カウンターが減少する単純なケースではありません)。

ループが可能な場合のグラフの再帰的トラバースのようなものを意味します。

どこかで無限ループになっていないかどうかを確認する必要があります。そして、デバッガーを使用してこれを行うだけでは、特定の答えが得られません(アルゴリズムが無限ループにあるのか、それとも単に処理されているのかがわからないため)。

具体例なしで説明するのは難しいです。しかし、私が必要なのは...

「たとえば、複雑な再帰アルゴリズムで無限ループが発生しないかどうかを確認する」.

4

5 に答える 5

4

アルゴリズムが終了すると考える理由について理論を立てる必要があります。理論を数学的な定理として証明するのが理想的です。

各再帰呼び出しで削減する問題状態の関数を探すことができます。たとえば、ウィキペディアのアッカーマン関数に関する次の説明を参照してください。

A(m, n) の評価が常に終了することは、すぐにはわからない場合があります。ただし、各再帰アプリケーションで m が減少するか、m が同じままで n が減少するため、再帰は制限されます。n が 0 になるたびに m が減少するため、m も最終的には 0 になります。(より技術的に表現すると、それぞれの場合、ペア (m, n) はペアの辞書式順序で減少します。これは、負でない単一の整数の順序付けと同様に、適切な順序付けです。これは、順序付けが下がらないことを意味します。ただし、m が減少する場合、n の増加量に上限はなく、多くの場合、大幅に増加します。

これは、アルゴリズムに適用することを考えるべきタイプの推論です。

アルゴリズムの終了を証明する方法が見つからない場合は、終了を証明できるバリエーションを探すことを検討してください。任意のプログラムが終了するかどうかを常に判断できるとは限りません。秘訣は、終了を証明できるアルゴリズムを作成することです。

于 2012-11-26T11:50:04.997 に答える
3

最良は、前後の条件、バリアント、および不変量によって有限性を証明することです。呼び出しごとに値が増加する（仮想）式を指定できる場合は、保証があります。

これは、ループが有限であることを証明することと同じです。さらに、複雑なアルゴリズムをより扱いやすくする可能性があります。

于 2012-11-26T11:34:48.200 に答える
2

再帰呼び出しの深さをカウントする必要があります...そして再帰呼び出しの深さが特定のしきい値に達した場合は例外をスローします。

例えば：

void TheMethod(object[] otherParameters, int recursiveCallDepth)
{
   if (recursiveCallDepth > 100) { 
      throw new Exception("...."); }
   TheMethod(otherParameters, ++recursiveCallDepth);
}
于 2012-11-26T11:33:49.113 に答える
1

無限ループをチェックしたい場合は、

System.out.println("no its not endless");再帰関数呼び出しの次の行にa を書きます。

ループが無限になる場合、このステートメントは印刷されません。そうでない場合は、出力が表示されます

于 2012-11-26T11:26:53.263 に答える
0

1 つの提案は次のとおりです。

無限ループがある場合、グラフの場合、グラフ内の頂点の総数よりも多い頂点の数を持つパスが取得されます。グラフ内の頂点の数がグローバル変数であると仮定すると (これが最も一般的なケースだと思います)、深さが既に頂点の総数を上回っている場合は、再帰の開始時に条件付きブレークポイントを設定できます。

これは、Eclipse で Java の条件付きブレークポイントを行う方法のリンクです。

于 2012-11-26T11:28:08.957 に答える