In komplexer Datenstruktur suchen

[Don P]

Hallo Patrick,

Mit einer einzigen Funktion ist mir die Rekursion auch nicht gelungen.

Da meine Kenntnisse der Perl-Syntax ziemlich eingeschlafen sind, will ich mich hier nicht darauf einlassen und poste lieber eine Beschreibung dessen, was ich meine. Ist hoffentlich auch so verständlich.

Auf die Gefahr, dass ich dir nichts neues erzähle, nochmal grundsätzlich zur Rekursion:
Die Datenstruktur ist immer eine Baumstruktur:

  
TV--flintstones--series--flintstones  
    |            |  
    |            nights--monday  
    |            |       |  
    |            |       thursday  
    |            |       |  
    |            |       friday  
    |            |  
    |            members-----name--fred  
    |                     |  |  
    |                     |  role--husband  
    |                     |  |  
    |                     |  age--36  
    |                     |  
    |                     |--name--wilma  
    |                     |  |  
    |                     |  role--wife  
    |                     |  |  
    |                     |  age--31  
    |                     |  
    |                     |--name--pebbles  
    |                        |  
    |                        role--kid  
    |                        |  
    |                        age--4  
   etc.  

Um darin etwas zu suchen, geht man am besten der Reihe nach alle Knoten durch, angefangen also beim TV:

Wenn der übergebene Parameter eine Liste ist (zuerst also TV), geht es sofort in den nächsten Rekursionsschritt mit dem ersten Listenelement als Parameter (flintstones) usw. bis man am Ende des Zweigs angekommen ist (TV->flintstones->series->flintstones). Damit endet der letzte Rekursionsschritt und es geht weiter im vorherigen mit dem nächsten Element der Liste (nights) und wenn das wieder eine Liste ist, dann sofort wieder zum nächsten Rekursionsschritt bis zum Ende (monday), dann wieder zurück bis zum nächsten Element der vorherigen Liste (thursday) usw. usf.

Das ist m.E. soweit die einfachste rekursive Algorithmus, der alle Elemente der Struktur durchläuft, ähnlich File::Find. Genau wie dort oder bei dem genannten Walk-Modul könnte man nun für jeden erreichten Knoten eine Funktion aufrufen, die mit dem besuchten Knoten etwas unternimmt, z.B. einen Vergleich mit dem gesuchten Datum anstellt. Da diese Funktion aber außerhalb der eigentlichen Rekursionskette liegt, müsste sie das Ergebnis des Vergleichs auch irgendwo außerhalb abspeichern, damit alle Rekursionsschritte (auch die vorherigen) darauf zugreifen und die gefundene Übereinstimmung zur Kenntnis nehmen können, oder aber die externe Funktion müsste das Ergebnis an den aufrufenden Rekursionsschritt direkt zurückgeben, damit dieser wiederum einen entsprechenden Wert an den vorherigen Rekusionsschritt weitergeben kann.

Denn für deine Zwecke ist klar, dass, wenn eine Übereinstimmung irgendwo gefunden wird, der vorherige Rekursionsschritt davon Kenntnis erhalten sollte, weil ja derjenige Rekursionsschritt, in dem die Übereinstimmung gefunden wurde, zunächst selbst nicht "weiß", welche Rekursionsschritte vor ihm statt gefunden haben, d.h. eine Ausgabe wie "wilma ist der name eines members der flinstones im TV" kann eigentlich erst zustande kommen, wenn die Rekursion von der gefundenen "wilma" komplett zurückgekehrt ist zur TV-Liste, wobei bei gefundener Übereinstimmung mit dem Suchbegiff (erkennbar z.B. mittels Flag in jeweiligen Rückgabewerten der rekursiven Funktion) die Namen der Elemente rückwärts eingesammelt werden können (wilma->members->fintstones->TV).

Denkbar wäre jetzt, dass man den tieferen Rekursionsschritten jeweils als zusätzliche Parameter Informationen über die besuchten Ebenen mitteilt, z.B. einen Tiefenzähler mitgibt und eine Liste der in direkter aufsteigender Linie breits besuchten Elternelemente. Damit "wüsste" ein Rekursionsschritt jeweils, wo genau er sich befindet und könnte bei gefundener Übereinstimmung sofort reagieren mit z.B. "Wow, ich habe 'wilma' gefunden in Tiefe 4, und weil es Tiefe 4 ist und ein members-hash, gebe ich gleich mal aus: 'wilma ist ein Eltern[Eltern.length] der Eltern[Eltern.length-1] der Eltern[Eltern.length.2]...' Jetzt bin ich also fertig und gebe zurück: 'gefunden!' ". Der vorhergehende Rekursionsschritt "hört" dieses "gefunden!" und kann darauf regieren mit "Wow, wir haben's gefunden in Tiefe 3+1, und weil ich selber in Tiefe 3 bin, gebe ich die anderen Geschwister auch gleich aus: "Other members are: ....".

Soweit ist das alles möglich mit einer einzigen rekursiven Funktion, meine ich jedenfalls. Aber natürlich muss man dann etwas über die Struktur wissen und an geeigneter Stelle die gewünschten Reaktionen bzw. Bedingungen hardcodieren.

Gruß, Don P