Rekursive Algorithmen ◦ Zusammenfassung ◦ ?

Wie die Implementation der Klasse cEintrag im Wörterbuch-Projekt andeutet, lassen sich Bäume rekursiv definieren. Rekursiv definierbare Datenstrukturen lassen sich oft auch mit rekursiven Algorithmen durchlaufen. Ob eine rekursive Lösung besser ist als eine iterative (mit Wiederholungsanweisungen wie Do While) muss man von Fall zu Fall entscheiden.

Wir suchen nach einer rekursiven Variante der Einfügeoperation und gehen dazu von der rekursiven Definition eines Baumes aus. Ein Baum ist entweder ...

1. ein Knoten ohne Nachfolger oder
2. ein Knoten mit Bäumen als Nachfolger.

Die Definition unterscheidet zwei Fälle. Der Basisfall (1) nennt alle trivialen Ausprägungen. Er umfasst all jene Bäume, die nur einen einzigen Knoten besitzen. Die Reduktion (2) beschreibt alle komplexeren Strukturen, indem sie Teile davon wiederum als Elemente im Sinne des Basisfalls oder der Reduktion identifiziert. Sie zerlegt einen Baum in eine Wurzel und eine Menge von Teilbäumen, die ihrerseits Bäume im Sinne der Definition sind. Einen trivialen Binärbaum gemäss dem ersten Teil der Definition zu erzeugen, ist einfach, da ein solcher Baum nur aus einem Wurzelknoten besteht.

Um einen neuen Knoten in einen bestehenden Baum einzufügen, geht man zur Wurzel, bestimmt in welchen Teilbaum der Knoten eingefügt werden muss und ruft die Einfügeoperation mit dem Teilbaum rekursiv auf. Der folgende Entwurfscode formuliert den Algorithmus:

    fügeHinzuRekursiv Begriff, Baum
      '-- 1 Basisfall
      Falls Baum leer
        erzeuge Wurzelknoten
        fülle Begriff ein.

      '-- 2 Reduktion
      sonst
        Falls Begriff < Begriff im Wurzelknoten von Baum
          fügeHinzuRekursiv Begriff, linker Teilbaum von Baum.
        Falls Begriff > Begriff im Wurzelknoten
          fügeHinzuRekursiv Begriff, rechter Teilbaum von Baum.

Beachten Sie bei der Konstruktion rekursiver Algorithmen drei Regeln. Sonst laufen Sie Gefahr einer Endlosrekursion:

1. Ein rekursiver Algorithmus muss immer einen Basisfall und eine Reduktion haben.

2. Der Basisfall muss vor der Reduktion geprüft werden. Er beschreibt die Bedingung, unter welcher die Rekursion abbricht (Abbruchbedingung).
3. Die Reduktion muss die Aufgabe vereinfachen, und zwar so, dass eine der Abbruchbedingungen nach endlich vielen Schritten erfüllt wird. Die Reduktion enthält die rekursiven Aufrufe.

Die Implementation in VBA gelingt wegen der doppelten Verkettung nicht ganz so elegant wie im Entwurfscode dargestellt. Der Basisfall muss unterscheiden, ob der neue Knoten die Wurzel des Baumes, ein linkes Blatt oder ein rechtes Blatt wird.

Klassenmodul cWörterbuch

    Private Sub fügeHinzuRekursiv(Begriff As String, Definition As String, Baum As CEintrag)
      '-- Abbruchbedingungen
      If Baum Is Nothing Then
        Set Wurzel = New CEintrag
        Wurzel.Begriff = Begriff
        Wurzel.Definition = Definition
      ElseIf Begriff < Baum.Begriff And Baum.KindLinks Is Nothing Then
        erzeugeKindLinks Baum, Begriff, Definition
      ElseIf Begriff > Baum.Begriff And Baum.KindRechts Is Nothing Then
        erzeugeKindRechts Baum, Begriff, Definition

      '-- Reduktion
      ElseIf Begriff < Baum.Begriff Then
        fügeHinzuRekursiv Begriff, Definition, Baum.KindLinks
      ElseIf Begriff > Baum.Begriff Then
        fügeHinzuRekursiv Begriff, Definition, Baum.KindRechts
      End If
    End Sub

Über das Argument Baum muss man jeweils den aktuellen Teilbaum übergeben, der mit jedem rekursiven Aufruf kleiner wird. Nach einigen rekursiven Aufrufen ist der übergebene Baum leer. Der Basisfall erzeugt einen neuen Knoten als trivialen Baum und gibt ihn im Argument wieder zurück.

Der erste Aufruf der Prozedur muss die Wurzel übergeben:

    fügeHinzuRekursiv Begriff, Definition, Wurzel

Übungsaufgabe "Wörterbuch Standard"

Rekursive Navigation eines Dateiverzeichnisses

©abo