Visual Basic .NET: Rekursion und Iteration

Vor allem bei mathematischen Funktionen unterscheidet man zwischen zwei grundlegenden Arbeitsweisen: Iteration und Rekursion. Dieses Kapitel soll eine Einführung in Vor- und Nachteile beider Wege sein.

So wie dieses Buch mit dem obligatorischen „Hello World“-Beispiel begonnen hat, so werden wir auch hier ein obligatorisches Beispiel bemühen: die Fakultätsfunktion. In der Mathematik ist die Fakultät einer positiven, ganzen Zahl n (geschrieben „n!“) die Multiplikation aller Zahlen von 1 bis n miteinander. Zum Beispiel:

$5!=1\cdot 2\cdot 3\cdot 4\cdot 5=120$

$6!=1\cdot 2\cdot 3\cdot 4\cdot 5\cdot 6=720$

Rekursion

Visual Basic .NET besitzt wie fast alle modernen Programmiersprachen die erstaunliche Möglichkeit, aus einer Funktion heraus die gleiche Funktion nochmals aufzurufen. Zum Beispiel kann sich innerhalb einer Funktion Test ein Befehl Test() befinden. Das machen wir uns mit Rekursion zunutze.

Der Ansatz der Rekursion ist nämlich, ein vorliegendes Problem (hier: „Was ist die Fakultät von n?“) auf ein einfacheres Problem zu reduzieren. Das nächsteinfachere Problem ist hier: „Was ist die Fakultät von n-1?“ Bei einem Blick auf die obigen Beispiele fällt auf, dass die Fakultät von 6 genau das sechsfache der Fakultät von 5 ist. Das ist logisch, schließlich fehlt bei 5! genau der Faktor 6. Allgemein ist also:

$n!=n\cdot (n-1)!$

Damit haben wir das erreicht, was unser Ziel war. Wir haben das Ausgangsproblem auf ein einfacheres Problem reduziert. Dieser Vorgang heißt Rekursionsschritt. So sieht der Rekursionsschritt in Code aus:

Code:  

Private Function FakRek(ByVal n As Integer) As Integer
    Return n * FakRek(n - 1)
End Function

Der Rückgabewert der Funktion FakRek (also die Fakultät von n) ist das n-Fache des Rückgabewertes der Funktion FakRek mit dem Parameter „n - 1“ (also die Fakultät von n - 1). Versuchen Sie nun, diese Funktion in einem Ihrer Programme aufzurufen, zum Beispiel mit FakRek(6). Problem: Das Programm wird sich festfahren und irgendwann abgebrochen, weil der Speicher alle ist oder ein Überlauf auftritt.

Was ist passiert? Wenn Sie FakRek(6) aufrufen, wird der Ausdruck hinter Return ausgewertet. Dazu wird FakRek(5) aufgerufen. Damit dieser Aufruf seinen Rückgabewert berechnen kann, wird FakRek(4) aufgerufen. Damit dieser Aufruf seinen Rückgabewert berechnen kann, wird FakRek(3) aufgerufen. Damit dieser Aufruf seinen Rückgabewert berechnen kann, wird FakRek(2) aufgerufen... Ich glaube, Sie verstehen, worauf ich hinaus will. Beim Versuch, die Return-Ausdrücke auszuwerten, verzettelt sich Visual Basic in Funktionsaufrufen, die immer neue Funktionsaufrufe starten. Wir haben es also mit einer Endlosschleife zu tun. Da auch Funktionsaufrufe Speicherplatz (in einem speziellen Speicherbereich) benötigen, ist der irgendwann voll. Alternativ kann es schon vorher passieren, dass der Parameter so negativ wird, dass er nicht mehr auf Integer gespeichert werden kann, es kommt zum erwähnten Überlauf.

Abhilfe schafft ein Rekursionsanfang. Den benutzen wir, sobald das Problem auf das einfachste denkbare Problem reduziert wurde, um die Rekursion abzubrechen. Im Falle der Fakultät ist das einfachste Problem die Fakultät von 1, die ist 1. Ein zweites Kriterium für den Rekursionsanfang ist, dass sich alle Probleme durch Rekursionsschritte auf diesen Anfang reduzieren lassen. Auch das ist gegeben, da wir nur positive Zahlen benutzen. Wenn die kleiner werden, kommen wir garantiert irgendwann bei 1 an. So sieht das ganze dann aus:

Code:  

Private Function FakRek(ByVal n As Integer) As Integer
    If n = 1 Then
        Return 1                    'Rekursionsanfang
    Else
        Return n * FakRek(n - 1)    'Rekursionsschritt
    End If
End Function

Wenn n gleich 1 ist, befinden wir uns am Rekursionsanfang, der Rückgabewert wird als absoluter Wert (Literal) angegeben. Ansonsten wird der Rekursionsschritt benutzt, um das bestehende Problem zu vereinfachen.

Man kann das Beispiel auch kürzer schreiben, indem man die einzeilige Fassung der If-Anweisung verwendet. Dabei nutzen wir aus, dass die Return-Anweisung die Ausführung der Funktion beendet, nachfolgende Befehle werden nicht ausgewertet. Im Falle des Rekursionsanfangs wird hier also der Rekursionsschritt nicht ausgeführt:

Code:  

Private Function FakRek(ByVal n As Integer) As Integer
    If n = 1 Then Return 1      'Rekursionsanfang
    Return n * FakRek(n - 1)    'Rekursionsschritt
End Function

Ein verbleibendes Problem ist der für die Funktion zu große Wertebereich. Bei Werten von 0 und kleiner verpassen wir den Rekursionsanfang und landen wieder in der Endlosschleife. Indem Sie den Parameterdatentyp in UInteger ändern, lässt sich dieses Problem umgehen. Die Fakultät von 0 wird allgemein auch mit 1 definiert. Verschieben Sie den Rekursionsanfang von 1 nach 0, lässt sich auch diese letzte Lücke schließen.

Code:  

Private Function FakRek(ByVal n As UInteger) As UInteger
    If n = 0 Then Return 1      'Rekursionsanfang
    Return n * FakRek(n - 1)    'Rekursionsschritt
End Function

Iteration

Warum erzähle ich das alles? Weil es noch ein alternatives Modell gibt: die Iteration. Während die Rekursion komplexe Probleme zu einfachen Problemen auflöst, löst Iteration zuerst das einfachste Problem und löst, darauf bauend, komplexe Probleme. Es handelt also in aller Hinsicht um den totalen Gegenentwurf.

Als Ausgangspunkt verwenden wir bei der Iteration das einfachste Problem, nämlich die Fakultät von Null (= 1). Nun gehen wir nach und nach zum nächstkomplexeren Problem über, also erst zur Fakultät von 1, dann zu der von 2, und so weiter. Das setzen wir fort, bis das konkrete Problem erreicht ist und die Lösung vorliegt. So sieht der Code für die iterative Implementation der Fakultätsfunktion aus:

Code:  

Private Function FakIter(ByVal n As Integer) As Integer
    Dim Temp As Integer = 1 'die Fakultät von 0 als Ausgangspunkt
    Dim Crnt As Integer = 0 'zurzeit berechnen wir die Fakultät von 0 (Crnt = Current = zurzeit)
    Do While Crnt < n       'die gewünschte Fakultät ist noch nicht erreicht
        Crnt += 1           'wir berechnen die nächsthöhere Fakultät
        Temp *= Crnt        'Berechnung der nächsthöheren Fakultät
                            'Temp enthält die aktuelle Fakultät (i-1)!, Crnt enthält i
    Loop
    Return Temp             'nach der Schleife liegt auf Temp die gewünschte Fak. vor
End Function

Vergleich

Rekursion und Iteration haben verschiedene Vorteile, die in ihrem Ausmaß nicht zu unterschätzen sind. Die Rekursion ist, wie auch aus den obigen Beispielen ersichtlich wird, sehr einfach und intuitiv implementierbar. Negativ fallen die lange Laufzeit und der größere Speicherbedarf auf. Dies ergibt sich durch die andauernden Funktionsaufrufe. Die Iteration kennt diese Probleme nicht. Mit ihr lassen sich auch komplexe Probleme in kurzer Zeit berechnen. Das ist vor allem für zeitkritische oder aufwändige Berechnungen von Bedeutung. Der Nachteil dieser Methode ist die komplexere Implementierung.

Alles in allem ist Iteration empfehlenswerter als Rekursion. Sie erfordert zwar mehr Arbeit, die investierte Zeit zahlt sich jedoch aus.

Übung

Fibonacci-Folge

Ein anderes, etwas komplexeres Beispiel für Rekursion und Iteration ist die Fibonacci-Folge. Sie berechnet sich wie folgt: Die ersten zwei Glieder (Index 1 und 2) sind 1, jedes andere Glied ergibt sich als Summe der zwei vorhergehenden Glieder.

Index	Wert
1	1
2	1
3	1 + 1 = 2
4	1 + 2 = 3
5	2 + 3 = 5
6	3 + 5 = 8
...

Ihre Aufgabe ist es nun, die Fibonacci-Folge rekursiv und iterativ zu implementieren. Eine Lösung mit Erklärungen steht für Sie bereit.

Diophantische Gleichung

Falls die Fibonacci-Folge zu leicht für Sie war oder Sie noch mehr üben möchten, können Sie versuchen den Algorithmus für das Lösen einer einfachen diophantischen Gleichung zu implementieren. Es sei angemerkt, dass die iterative Lösung einen Stapelspeicher benötigen.

Aufgabenstellung: Die zu lösende diophantische Gleichung hat die Form $ax+by=c$, wobei $a$, $b$ sowie $c$ gegeben und $x$ sowie $y$ gesucht werden. Alle Variablen sind ganze Zahlen.

Eigentlich können Sie hier schon loslegen und erste Lösungskonzepte erarbeiten. Trotzdem sollten Sie einen Blick auf die folgenden Tipps werfen:

• Die Gleichung hat nicht immer Lösungen; Sie können sich ja ein einfaches Beispiel überlegen.
• Sie sollten $x$ und $y$ als Referenzparameter übergeben und die Funktion so gestalten, dass diese beim endgültigen Verlassen sie die Lösungen darstellen. Die Funktion selbst gibt einen Wahrheitswert zurück, der angibt, ob die Gleichung lösbar war.
• Eliminieren Sie die Spezialfälle $c=0$ und $a=0$ gleich am Anfang.
• Überlegen Sie sich, wann die Gleichung für $b=0$ Lösungen hat und welche.
• Für $b\neq 0$ können Sie durch Division mit Rest Zahlen $q$ und $r$ finden, die $a=qb+r$ mit $|r|<|b|$ lösen. $q$ entspricht hier dem üblichen Quotienten und $r$ dem zugehörigen Divisionsrest. Damit Lösen Sie die neue Gleichung $bx^{\prime }+ry^{\prime }=c$ nach $x^{\prime }$ und $y^{\prime }$. Falls diese nicht lösbar ist, ist es die gegebene auch nicht. Ansonsten ist $x=y^{\prime }$ und $y=x^{\prime }-qy^{\prime }$ eine mögliche Lösung.
• (Kleine Zusatz: Zeigen Sie, dass die Funktion immer terminiert, also irgendwann in einen Fall mündet, der einen Wert zurück gibt.)
• Falls Sie sich schon fragen: Die imperative Variante sollte unbedingt nach Lösung des rekursiven Algorithmus angegangen werden. Dann ist sie verhältnismäßig einfach lösbar, denn die meiste Arbeit wurde schon gemacht.

Damit bleibt die Aufgabe anspruchsvoll genug und ist auch mit den Fähigkeiten der grundlegenden Schulmathematik lösbar. Auch hier steht eine ausführliche Anleitung zur Lösung bereit.