Wie kann man eine rekursive Suche abbrechen?

  • VB.NET
  • .NET (FX) 4.0

Es gibt 9 Antworten in diesem Thema. Der letzte Beitrag () ist von Link275.

    Wie kann man eine rekursive Suche abbrechen?

    Hey,
    kann mir jemand sagen, wie man eine rekursive Suche abbrechen kann?

    Hier die Situation:
    Ich habe im Programm eine globale Abbruchvariable deklariert, die zunächst
    auf False gesetzt ist. Wenn ich die Funktion abbrechen möchte, setze ich diese
    Variable über ein Button im Hauptprogramm auf True.
    Innerhalb der 'Rekursiven Funktion' frage ich nun diese Variable ab und wenn
    sie dann auf True steht, sollte die 'Rekursiven Funktion' DAUERHAFT verlassen
    werden (Die Abfrage funkioniert, da die Abbruchvariablenänderung im
    Hauptprogramm durch 'Application.DoEvents' in der 'Rekursiven Funktion'
    ausgeführt und damit dort bemerkt wird!).
    Nun ist es aber mit 'If Cancel = True then Return -1: Exit Function' innerhalb
    der aufgerufenen Funktion nicht getan, da der Rücksprung ja nur in die selbe
    (also in die aufrufende) Funktion erfolgt. Dies funktioniert auch dann nicht,
    wenn das Abbruchkriterium ganz am Anfang der Funktion abgefragt wird, so
    dass -wie ich dachte- sofort jeder Rücksprung wieder erneut ausgeführt wird.

    Für einen Lösungsansatz wäre ich dankbar.
    mfG DHB

    Ich meine:
    :P Es sollten nur ernstzunehmende Beiträge eingestellt werden!
    :( Beiträge, die nur deren Anzahl in die Höhe treiben sollen, stehlen Lesern deren Zeit und schenken nur Frust.
    ;) Wenn ein Autor sein Thema für erledigt hält, sollte er dies kurz als letzten Eintrag vermerken.
    8) Leser wüssten dann, dass hier weitere Beiträge nicht mehr sinnvoll sind.

    DHB schrieb:

    Application.DoEvents
    So programmiert man aber nicht. Wenn du was abbrechen können willst, dann muss alles in nen anderen Thread.

    So würde dann eine rekursive Funktion aussehen, die sich beenden kann:

    VB.NET-Quellcode

    1. Public Function SomeRecursiveFunction(parameters As SomeType, ByRef canceled As Boolean) As SomeType
    2. If cancelRequested Then
    3. canceled = True
    4. Return Nothing
    5. End If
    6. 'some code
    7. If successInThisStep Then
    8. Return something
    9. Else
    10. Return SomeRecursiveFunction(ModifyParametersForNextStep(parameters), canceled)
    11. End If
    12. End Function​
    ich bevorzuge ja, Rekursionen in anonymen Methoden anzulegen. So braucht man übergeordnete Parameter wie canceled nicht durch jeden Aufruf durchschleifen, und ist trotzdem lokal gekapselt.
    Ansonsten gibt es auch iterative Alternativen zur Rekursion - die haben aber annere Stärken und Schwächen, also kommt drauf an, was man machen will.

    Auch denkbar ist, einem TryCatch zu missbrauchen, um gewissermaßen mit einem Befreiungsschlag aus dem ganzen verschachtelten Stack rauszuhopsen.
    @ Artentus: Mit Deinem Vorschlag muss ich mich noch befassen - werde ich auch tun! Weißt Du, ich bin zwar seit VB1 (1991) dabei (seit 1975 andere VB.-Dialekte und andere Programmiersprachen), habe aber erst 2010 begonnen mit VB-Net zu programmieren und wenn Du bedenkst, dass ich ein 46er bin, fallen mir diese ständigen Neuerungen nicht mehr ganz so leicht - aber ich hab's bisher immer geschafft und werde mich auch diesmal in das Thema 'Eigener Thread' einarbeiten.
    @ ErfinderDesRades: Von Dir habe ich bisher immer für mich verständliche Tipps erhalten - so auch jetzt! Die letzten beiden Vorschläge kommen für mich nicht in Frage. Die Idee mit der anonymen Methode habe ich - nachdem ich dazu Dein "Special post" zu anonymen Methoden gelesen habe - verstanden und werde diesen Weg verfolgen; danke!
    @ Sonne75: Zitat: "Jede rekursive Funktion muss ja eine (Abbruch-)Bedingung haben, ..." - wieso? Ich durchsuche Verzeichnisse bis diese "alle durch" sind; eine Abbruchbedingung soll eben das 'Button-Click-Ereignis' im Hauptprogramm sein; das war meine Frage!
    Bin gespannt, wie sich Dein Persönlichkeitsprofil auswirkt ;) - nicht böse sein!
    mfG DHB

    Ich meine:
    :P Es sollten nur ernstzunehmende Beiträge eingestellt werden!
    :( Beiträge, die nur deren Anzahl in die Höhe treiben sollen, stehlen Lesern deren Zeit und schenken nur Frust.
    ;) Wenn ein Autor sein Thema für erledigt hält, sollte er dies kurz als letzten Eintrag vermerken.
    8) Leser wüssten dann, dass hier weitere Beiträge nicht mehr sinnvoll sind.
    Eine CancellationTokenSource erstellen und im ButtonClick die Methode CancellationTokenSource.Cancel() aufrufen.
    Das kannst du in jeder Schleife deiner rekursiven Abfrage über CancellationTokenSource.IsCancellationRequested abfragen und so ggf. aus der Rekursion aussteigen. Dabei muss dir aber bewusst sein, dass dies nicht aus dem GUI-Thread passieren darf - Threads bzw. Action (genauer Delegates).
    Die Delegaten bzw. Actions kannst du dann via BeginInvoke asynchron starten.
    hier mal das mit dem TryCatch - quasi ein Rekursions-sprengendes Goto:

    VB.NET-Quellcode

    1. Private Function GetReleaseDirInfo() As DirectoryInfo
    2. GetReleaseDirInfo = Nothing
    3. Dim recurse As Action(Of DirectoryInfo) = Sub(di)
    4. Console.WriteLine(di.FullName)
    5. If di.Name = "Release" Then
    6. GetReleaseDirInfo = di
    7. Throw New NotSupportedException
    8. End If
    9. For Each chld In di.GetDirectories
    10. recurse(chld)
    11. Next
    12. End Sub
    13. Try
    14. recurse(New DirectoryInfo("..\..\"))
    15. Catch ex As NotSupportedException
    16. End Try
    17. End Function
    Im Grunde sollte man extra dafür einen neue Exception-Erben erfinden - NotSupportedException herzunehmen ist ganz willkürlich.

    DHB schrieb:

    Bin gespannt, wie sich Dein Persönlichkeitsprofil auswirkt - nicht böse sein!

    Dann pass mal acht :P

    DHB schrieb:

    wieso? Ich durchsuche Verzeichnisse bis diese "alle durch" sind

    Wieso jede rekursive Methode eine Abbruchbedingungen haben muss? Na, sonst würde sie ja ewig laufen und das Programm würde sich aufhängen ;) "Alle durch" ist doch deine Abbruchbedingung ;)
    Wie weißt du denn, ob "alle durch" sind? ;) Hast du da ein If? Wenn ja, warum kannst du in dem If auch deine Abbruchbedingung abfragen (sagtest du nicht, du setzt eine Variable bei Buttonclick, die du überall abfragen kannst). Irgendwie verstehe ich das Problem nicht ganz...
    "alle durch" lese ich in diesem Fall als "For Each".


    Wenn man aus einer rekursiven Konstruktion unstrukturiert raus will, geht das meiner Meinung nach am elegantesten mit einer Exception.
    Wurde oben ja schon erläutert.
    Du schriebst zwar, dass das für dich nicht in Frage kommt, aber was spricht denn deiner Meinung nach dagegen, eine Exception zu werfen, die mit einem gezielten Try..Catch abgefangen wird?

    Es geht auch noch wesentlich härter:
    Du betreibst die Rekursion in einem eigenen Thread, den du bei Button-Click einfach killst. ;)
    --
    If Not Program.isWorking Then Code.Debug Else Code.DoNotTouch
    --
    Ich würd' den Aufruf für die rekursive Funktion in einen Thread auslagern und so starten. Via ButtonClick lässt sich das doch dann ganz einfach beenden.
    Mit Threads wäre es generell am sinnvollsten, und zwar immer dann, wenn man im vornherein schon weiß dass die Ausführung eine ganze Zeit lang dauern wird.
    Und "bis alle durch sind" sieht für mich bereits nach Abbruchbedingung aus ;)


    Link :thumbup:
    Hello World