Rekursionsalgorithmen: vorgeschlagene Muster und Praktiken?

Question

Ich schreibe ein Dienstprogramm, das auf zwei Objektdiagramme reflektiert und einen Wert zurückgibt, um anzuzeigen, ob die Diagramme identisch sind oder nicht. Es hat mich zum Nachdenken gebracht, gibt es ein allgemein akzeptiertes Muster für das Schreiben eines Rekursionsalgorithmus, der einen Wert von einigen wo in der Rekursion zurückgibt?

Meine Lösung wahrscheinlich einen ref-Parameter und in etwa so aussehen Pseudo-Code verwenden würde:

public static bool IsChanged(T current, T previous) 
{ 
    bool isChanged = false;   
    CheckChanged(current, previous, ref isChanged);   
    return isChanged ; 
} 


private static void CheckChanged(T current, T previous, ref isChanged) 
{ 
    //perform recursion 
    if (graphIsChanged) 
     isChanged = true; 
    else 
     CheckChanged(current, previous, ref isChanged); 
} 

Gibt es eine bessere/Reinigungsmittel/effizientere Art und Weise? Gibt es ein allgemeines Muster für eine solche Funktion?

Answer 1

Ich sehe keine Vorteile Ihrer Version, wenn auf diese höchst triviale Version verglichen:

public static bool IsChanged(T current, T previous) 
{ 
    //perform recursion 
    if (graphIsChanged) 
     return true; 
    else 
     return IsChanged(current, previous); 
} 

Als zusätzlichen Vorteil, einige Compiler können Endrekursion Optimierung verwenden, um diese Version in ein einfaches drehen Schleife, die effektiver ist.

Answer 2

Ich war schon immer ein Fan von einem tatsächlichen Rückgabewert von einer rekursiven Funktion, nicht nur eine Referenz auf eine Variable übergeben. Ich bin mir nicht sicher, was Sie in Ihrer Probe versuchen wollen, aber warum nicht einfach einen Bool von CheckChanged zurückgeben?

Answer 3

Es gibt kein allgemeines Muster für rekursive Funktionen. Die einzige Anforderung besteht darin, dass die Funktion garantiert einen degenerierten (d. H. Nicht rekursiven) Fall erreicht, so dass Sie nicht mit einer unendlichen Rekursion enden. Im Allgemeinen ist die Verwendung eines Rückgabewerts wahrscheinlich etwas effizienter als die Übergabe eines Zeigerparameters, aber dies hängt von dem spezifischen Problem und dem verwendeten Compiler ab.

In jedem Fall sind solche Mikrooptimierungen selten hilfreich. Konzentrieren Sie sich darauf, zuerst die beste Laufzeitkomplexität zu erzielen, und optimieren Sie den Code später, wenn Sie ein Leistungsproblem haben.

Answer 4

Endrekursion ist nicht nur effektiver, es hält Sie aus dem Stapel Ausblasen auf tiefe Rekursion: http://en.wikipedia.org/wiki/Tail_recursion

Das heißt, es wird ein „Stack-Überlauf“ :)

http://en.wikipedia.org/wiki/Stack_overflow