Debugging eines rekursiven Algorithmus

Question

Meine Frage ist, ob es einige kluge Wege gibt, komplizierte rekursive Algorithmen zu debuggen. Angenommen, wir haben eine komplizierte (nicht ein einfacher Fall, wenn der Rekursionszähler in jeder 'verschachtelten Iteration' verringert wird).

Ich meine so etwas wie rekursives Traversieren eines Graphen, wenn Schleifen möglich sind.

Ich muss überprüfen, ob ich irgendwo keine Endlosschleife bekomme. Und dies nur mit einem Debugger zu tun gibt keine sichere Antwort (weil ich nicht sicher bin, ob ein Algorithmus in einer Endlosschleife ist oder einfach so verarbeitet wird, wie er sollte).

Es ist schwer, es ohne konkretes Beispiel zu erklären. Aber was ich brauche, ist ...

'um zu überprüfen, ob die Endlosschleifen nicht in einem komplizierten rekursiven Algorithmus auftreten'.

Answer 1

Sie müssen eine Theorie dafür bilden, warum Sie denken, dass der Algorithmus beendet wird. Idealerweise sollte die Theorie als mathematisches Theorem bewiesen werden.

Sie können nach einer Funktion des Problemstatus suchen, die bei jedem rekursiven Aufruf reduziert wird. Zum Beispiel finden Sie in der folgenden Diskussion von Ackermanns Funktion von Wikipedia

Es ist nicht sofort offensichtlich ist, dass die Bewertung von A (m, n) immer beendet. Die Rekursion ist jedoch beschränkt, da in jeder rekursiven Anwendung entweder m abnimmt oder m gleich bleibt und n abnimmt. Jedes Mal, wenn n Null erreicht, nimmt m ab, so dass m schließlich ebenfalls Null erreicht.(Technisch ausgedrückt, nimmt in beiden Fällen das Paar (m, n) in der lexikografischen Ordnung der Paare ab, was ebenso wie die Ordnung der einzelnen nicht-negativen ganzen Zahlen eine Ordnungsordnung ist, das heißt, man kann nicht in der Ordnung untergehen unendlich oft hintereinander.) Wenn m jedoch abnimmt, gibt es keine Obergrenze dafür, wie viel n zunehmen kann - und es wird oft stark zunehmen.

Das ist die Art von Argumentation, die Sie auf Ihren Algorithmus anwenden sollten.

Wenn Sie keine Möglichkeit finden, zu beweisen, dass Ihr Algorithmus terminiert, sollten Sie nach einer Variation suchen, deren Beendigung Sie nachweisen können. Es ist nicht immer möglich zu entscheiden, ob ein beliebiges Programm endet oder nicht. Der Trick besteht darin, Algorithmen zu schreiben, die Sie als terminieren können.

Answer 2

, wenn Sie für Endlosschleifen überprüfen möchten,

Brief System.out.println("no its not endless"); in der nächsten Zeile der rekursiven Funktion aufrufen.

wenn die Schleife endlos sein würde, diese Aussage wird nicht Druck erhalten, wenn Sie sonst die Ausgabe

Answer 3

Ein Vorschlag sehen, ist die folgende:

Wenn Sie dann werden Sie in der grafischen Darstellung Fall Endlosschleife haben Ermitteln Sie einen Pfad mit der Anzahl der Scheitelpunkte, die größer als die Gesamtzahl der Scheitelpunkte im Diagramm ist. Angenommen, die Anzahl der Scheitelpunkte im Graphen ist eine globale Variable (was meiner Meinung nach der häufigste Fall ist), können Sie einen bedingten Breakpoint am Anfang der Rekursion ausführen, wenn die Tiefe bereits über der Gesamtzahl der Scheitelpunkte liegt.

Here is a link wie Sie bedingte Haltepunkte für Java in Eclipse tun.

Answer 4

Sie müssen die Tiefe der rekursiven Aufrufe zählen ... und dann eine Ausnahme auslösen, wenn die Tiefe der rekursiven Aufrufe einen bestimmten Schwellenwert erreicht.

Zum Beispiel:

void TheMethod(object[] otherParameters, int recursiveCallDepth) 
{ 
    if (recursiveCallDepth > 100) { 
     throw new Exception("...."); } 
    TheMethod(otherParameters, ++recursiveCallDepth); 
} 

Answer 5

Beste ist beweisen Endlichkeit von Pre- und Post-Bedingungen, Varianten und Invarianten. Wenn Sie eine (virtuelle) Formel angeben können, deren Wert bei jedem Anruf erhöht wird, haben Sie eine Garantie.

Dies ist das gleiche wie Loops als endlich zu beweisen. Außerdem könnte es komplexe Algorithmen anpassungsfähiger machen.