Home > Artikel > Ausgabe 7/2013 > Rekursion mit VBA

Rekursion mit VBA

Achtung: Sie sind nicht angemeldet. Wenn Sie Abonnent sind und sich anmelden, lesen Sie den kompletten Artikel, laden das PDF herunter oder probieren die Beispieldatenbank aus (sofern vorhanden).

Manche Abläufe erfordern den Einsatz von Schleifen mit einer bestimmten Anzahl von Durchläufen oder einer vordefinierten Abbruchbedingung. In speziellen Fällen reichen Schleifen jedoch nicht aus, um zum Ziel zu kommen: Dann müssen rekursiv definierte Funktionen her. Dies sind solche Funktionen, die sich selbst aufrufen. Der vorliegende Artikel erklärt, wie solche Funktionen arbeiten und liefert einige Beispiele.

Beispieldatenbank

Die Beispiele dieses Artikels finden Sie in der Datenbank 1307_RekursionMitVBA.mdb.

Beispiel Fakultät

Bei der rekursiven Programmierung ruft sich eine Funktion selbst auf. Für einen einfachen Einstieg nehmen wir ein Beispiel, dass vielerorts zum Einsatz kommt: Die Berechnung der Fakultät einer Zahl. Die Fakultät einer Zahl n wird so definiert:

n! = n x (n-1) x ... x 2 x 1

Das bedeutet, dass man alle ganzen Zahlen miteinander multipliziert, die kleiner oder gleich der Zahl n sind. Ein Sonderfall ist die Fakultät von 0 – hierfür ist nämlich der Wert 1 definiert.

Um den Schritt zur Rekursion zu machen, definieren wir die Fakultät etwas anders:

n! = n x (n-1)!

Die Fakultät ist hier als das Produkt der Zahl selbst mit der Fakultät der nächstkleineren Zahl definiert. Und diese Fakultät entspricht natürlich wiederum die Zahl multipliziert mit der Fakultät der nächstkleineren Zahl. Es gibt hier auch eine Ausnahme: Wenn n den Wert 1 annimmt, ist die Fakultät von n gleich 1.

Fakultät per VBA

Wenn wir die Fakultät mit einer Funktion berechnen möchten, die sich selbst aufruft, müssen wir dieser zunächst einmal die Zahl übergeben, für welche die Fakultät berechnet werden soll. Der Funktionskopf sieht also beispielsweise so aus:

Public Function Fakultaet(lngZahl As Long) As Long

Beim ersten Aufruf soll die Funktion die Fakultät für die Zahl lngZahl ermitteln. Diese entspricht aber wiederum dem Produkt der Zahl und der Fakultät der Zahl minus Eins.

Innerhalb der Funktion rufen wir die Funktion also erneut auf – mit der um Eins verminderten Zahl. Das Ergebnis multiplizieren wir dann mit der Zahl selbst.

Die Anweisung sieht also so aus:

Fakultaet = lngZahl * Fakultaet(lngZahl - 1)

Insgesamt erhielten wir nun eine Funktion wie die Folgende:

Public Function Fakultaet(lngZahl As Long) As Long

     Fakultaet = lngZahl * Fakultaet(lngZahl - 1)

End Function

Wenn Sie die Funktion nun etwa aus dem Direktfenster mit dem Befehl Debug.Print Fakultaet(4) aufrufen, sollte das Ergebnis eigentlich 24 lauten (1 x 2 x 3 x 4). Allerdings zeigt Access nach kurzer Zeit eine Fehlermeldung an, die wie in Bild 1 aussieht. Was ist hier passiert? Ganz einfach: Wir haben der Funktion nicht mitgeteilt, wann sie anhalten soll. In diesem Fall berechnet sie nacheinander die Fakultät für 4, 3, 2, 1, 0, -1, -2 und so weiter.

Fehler bei rekursiver Funktion ohne Abbruchbedingung

Bild 1: Fehler bei rekursiver Funktion ohne Abbruchbedingung

Der Fehler wird schließlich dadurch ausgelöst, dass die Funktion die Zwischenergebnisse jeweils im Arbeitsspeicher unterbringen muss – und mit wachsender Anzahl Aufrufe ist der Speicher irgendwann einmal voll.

Also bauen wir die Funktion wie in Listing 1 auf. Die Funktion prüft bei jedem Aufruf zunächst, ob der Wert der mit lngZahl gelieferten Zahl gleich Eins ist. Ist dies der Fall, ist auch die Fakultät Eins – die Funktion braucht also kein weiteres Mal aufgerufen zu werden. Der Ablauf zur Berechnung der Fakultät von 4 sieht also so aus:

Public Function Fakultaet(lngZahl As Long) As Double

     If lngZahl = 1 Then

         Fakultaet = 1

     Else

         Fakultaet = lngZahl * Fakultaet(lngZahl - 1)

     End If

End Function

Listing 1: Rekursive Berechnung der Fakultät einer Zahl

  • Erster Aufruf mit lngZahl = 4
  • Zweiter Aufruf mit lngZahl = 3
  • Dritter Aufruf mit lngZahl = 2
  • Vierter Aufruf mit lngZahl = 1: Fakultaet liefert 1 zurück, der vierte Aufruf ist beendet.
  • Im dritten Aufruf wird der Funktionswert Fakultaet auf 2 x 1 = 2 eingestellt, der dritte Aufruf ist beendet.
  • Im zweiten Aufruf wird der Funktionswert Fakultaet auf 3 x 2 = 6 eingestellt, der zweite Aufruf ist beendet.
  • Im ersten Aufruf wird der Funktionswert Fakultaet auf 4 x 6 = 24 eingestellt, der erste Aufruf ist beendet und gibt als Ergebnis 24 zurück.

Hier wird auch gleich deutlich, dass eine rekursiv definierte Funktion immer Aktionen vor dem Aufruf der nächsten Ebnee ausführen kann, aber auch Aktionen nach diesem Aufruf. In diesem Fall tritt die Zuweisung des Ergebnisses immer erst nach dem Aufruf der nächsten Ebene und deren Abarbeitung auf.

Iteration statt Rekursion

In vielen Fällen kann man die Rekursion durch eine Iteration ersetzen. In unserem Fall sähe eine entsprechende Funktion wie in Listing 2 aus. Die Funktion FakultaetIterativ durchläuft eine For...Next-Schleife über die Werte von 1 bis zu der Zahl, deren Fakultät ermittelt werden soll.

Public Function FakultaetIterativ(lngZahl As Long) As Double

     Dim dblFakultaet As Double

     Dim i As Integer

     FakultaetIterativ = 1

     For i = 1 To lngZahl

         FakultaetIterativ = i * FakultaetIterativ

     Next i

End Function

Listing 2: Iterative Berechnung der Fakultät

Dabei multipliziert sie einfach das jeweils in FakultaetIterativ gespeicherte Ergebnis, das zu Beginn auf 1 eingestellt wird, mit dem aktuellen Wert der Laufvariablen i – also 1 x 1 = 1 im ersten Durchlauf, 2 x 1 = 2 im zweiten, 3 x 2 = 6 im dritten und 6 x 4 = 24 im vierten Durchlauf.

Die Vorteile dieser Variante liegen im geringeren Speicherbedarf und daraus resultierend in einer besseren Performance.

Allerdings lassen sich viele Probleme, die sich mit einfachen rekursiven Funktionen abbilden lassen, nicht durch Iteration darstellen. Das hier genannte Beispiel der Fakultät ist geradlinig – jeder Funktionsaufruf führt zu maximal einem weiteren Funktionsaufruf. Es gibt jedoch auch Probleme, bei denen innerhalb der rekursiven Funktion mehrfache Aufrufe der Funktion stattfinden – beispielsweise innerhalb einer Schleife.

Dafür gibt es einige Beispiele, zum Beispiel diese:

  • Einlesen der Verzeichnisse und Dateien: Hier kann jedes Verzeichnis Unterverzeichnisse enthalten, die wiederum eingelesen werden müssen.
  • Hierarchische Daten wie Vorgesetzte/Untergebene oder Stücklisten, bei denen jedes Bauteil aus einem oder mehreren anderen Teilen besteht

Vorgesetze und Untergebene

Das wohl bekannteste Beispiel für den Einsatz von Rekursion unter Access und VBA ist das der Mitarbeiterhierarchie.

Hier soll es einen oder mehrerer Vorgesetzte einer obersten Ebene geben, die sich dadurch auszeichnen, dass sie keinen Vorgesetzten haben. Alle anderen Mitarbeiter haben einen Vorgesetzten – entweder den der obersten Ebene oder einen darunter angesiedelten Mitarbeiter.

Typischerweise legt man das Datenmodell so an, dass man die sogenannte reflexive Beziehung innerhalb einer einzigen Tabelle abbildet. Dies sieht so aus, dass etwa die Tabelle tblMitarbeiter wie in Bild 2 ein Feld namens VorgesetzterID aufweist, dass mit dem Primärschlüsselfeld der gleichen Tabelle verknüpft ist.

Vorgesetzte, Variante I

Bild 2: Vorgesetzte, Variante I

Im Beziehungsfenster haben wir die Tabelle tblMitarbeiter zweimal hinzugefügt, um die Beziehung anlegen zu können. Man kann dann wie in Bild 3 den jeweiligen Vorgesetzten in das Feld VorgesetzterID eintragen.

Werte der Tabelle tblMitarbeiter inklusive der Vorgesetzten

Bild 3: Werte der Tabelle tblMitarbeiter inklusive der Vorgesetzten

Der Mitarbeiter mit dem Wert 1 im Feld MitarbeiterID ist der einzige Mitarbeiter der höchsten Ebene. Die Mitarbeiter mit den Werten 2 und 3 im Feld MitarbeiterID sind diesem direkt untergeordnet. Die übrigen Mitarbeiter haben die Mitarbeiter der zweiten Ebene als Vorgesetzte.

Es gibt noch eine zweite, weniger bekannte Variante der Zuordnung von Vorgesetzten und Untergebenen. Dabei enthält die Mitarbeitertabelle selbst kein Feld, um die Zuordnung vorzunehmen.

Stattdessen erledigen Sie dies mit einer weiteren Tabelle, welche die beiden an einer Zuordnung beteiligten Mitarbeiter als Vorgesetzten und Untergebenen definiert. Die für dieses Beispiel verwendete Tabelle tblMitarbeiterOhne ist prinzipiell wie die Tabelle tblMitarbeiter aufgebaut, es fehlt jedoch das Feld VorgesetzterID.

Dafür gibt es nun eine weitere Tabelle namens tblVorgesetzteUntergebene, die neben einem Primärschlüsselfeld zwei Felder namens VorgesetzterID und UntergebenerID enthält. Die Tabelle ist wie in Bild 4 aufgebaut. Außerdem müssen Sie auch noch einen eindeutigen Schlüssel für das Feld UntergebenerID festlegen, damit jeder Untergebene nur einem Vorgesetzten zugeordnet werden kann.

Entwurf der Tabelle tblVorgesetzteUntergebene

Bild 4: Entwurf der Tabelle tblVorgesetzteUntergebene

Die Beziehung zwischen den Tabellen sieht wie in Bild 5 aus. Dort ist zu erkennen, dass die Tabelle tblVorgesetzteUntergebene über die beiden Felder VorgesetzterID und UntergebenerID jeweils mit der Tabelle tblMitarbeiterOhne verknüpft ist.

Beziehungen zwischen den Tabellen tblMitarbeiterOhne und tblVorgesetzteUntergebene

Sie haben das Ende des frei verfügbaren Teil dieses Artikels erreicht!

Wenn Sie mehr lesen und auf viele weitere Artikel zugreifen möchten, melden Sie sich als Abonnent unter Login an. Falls nicht, bestellen Sie doch einfach ein Jahresabonnement!