Visual Basic .NET: Rekursion und Iteration

Aus Wikibooks

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:

[Bearbeiten] 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:

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:

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:

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:

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.

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

[Bearbeiten] 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:

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

[Bearbeiten] 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.

[Bearbeiten] Übung

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.

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