1Ein erstes Beispiel
Die Reihe der Fibonacci-Zahlen beginnt bekanntlich so:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, . . .
Offensichtlich ist jede Zahl die Summe ihrer beiden Vorgänger, wenn wir 0, 1 als Anfang vorgeben. Die rekursive Definition der Folge (Fn)n∈ℕ sieht bekanntlich so aus:
1.1Implementierungen
Ein Python-Skript, mit dem man die Zahlen rekursiv berechnet, lässt sich wie folgt formulieren:
Dann berechnet der Aufruf fib(0, 1, n) die Zahl F n. In der Tat gibt der Aufruf fib(0, 1, 0) den Wert 0 = F0, der Aufruf fib(0, 1, 1) = fib(1, 1, 0) = 1 gibt also 1 = F1 zurück. Wir behaupten, dass for n ≥ 1 der Aufruf fib(a, b, n) den Wert Fn−1 ⋅a+Fn ⋅b ergibt. Für n = 1 sehen wir fib(a, b, 1) = fib(b, a+b, 0) = b,wegen b = F0⋅a+F1 ⋅b ist die Vermutung also für n = 1 bewiesen. Sehen wir uns an, was im Induktionsschritt geschieht. Wir nehmen also an, dass die Behauptung für den Wert n ≥ 1 bewiesen ist, und rechnen aus
In (∗) wurde die Induktionsvoraussetzung benutzt, in (‡) die Definition der Fibonacci-Zahlen. Also ist die Behauptung auch for n + 1 bewiesen. Mit vollständiger Induktion ergibt sich also insgesamt, dass F n durch den Aufruf fib(0, 1, n) berechnet wird.
Damit können wir eine Funktion definieren, die – wie üblich – mit einem Parameter auskommt, die allerdings fib als lokale Funktion verwendet:
Aus den Überlegungen zur Korrektheit folgt, dass der Aufruf fibIterativ(n) die n-te Fibonacci-Zahl Fn liefert.
Der Leser, der schon rekursive Methoden in der Programmierung kennen gelernt hat, hat vermutlich als zweites Beispiel für den Gebrauch von Rekursion diese Formulierung gesehen:
Das ist die direkte Übertragung der Definition, man überlegt sich aber, dass hier Rechenzeit verschwendet wird, weil für jeden Aufruf Werte mehrfach berechnet werden.
1.2Diskussion
Hier gibt es ja nun schon einiges zu diskutieren und zu erklären. Fangen wir mit der Definition der Funktion an: eine Funktion wird durch das Schlüsselwort def eingeleitet, dann folgt der Name der Funktion und, in Klammern, eine Parameterliste, die auch leer sein kann. In der Tat ist es so, dass jede Funktion eine Parameterliste mitbekommt: Auch wenn sie leer ist, muss sie notiert werden. In unserem Beispiel ist die Liste der Parameter eine durch Kommata abgetrennte Liste von Namen; im Gegensatz zu anderen populären Sprachen (Java, C, C++) benötigen wir keine Typangaben für die Parameter. Auf die schließende Klammer folgt ein Doppelpunkt, auf den der definierende Block der Funktion folgt.
Sie sehen, dass der Block eingerückt ist. Alle folgenden Anweisungen, die dieselbe oder eine größere Tiefe der Einrückung aufweisen, gehören zu diesem Block. Wir werden gleich sehen, dass Blöcke auch geschachtelt werden können, dadurch wird auch optisch klar, welche Anweisungen zu diesem Block gehören. Die Anzahl der Leerzeichen zur Definition eines Blocks ist beliebig. In der Regel findet man Einrückungen von sechs Leerzeichen, man muss ein wenig vorsichtig sein, weil manche Editoren das Einrücken durch das Setzen der Tabulatortaste bewerkstelligen. Das führt leicht zu Irritationen, die sich jedoch durch die Einstellungen beim Editor beseitigen lassen. Die Einrückung muss konsistent sein:
(alles, was in der Zeile auf # folgt, wird als Kommentar betrachtet). Ist eine Zeile zu lang, so kann durch \ angedeutet werden, dass sie in der nächsten Zeile fortgesetzt wird (das ist bei umfangreichen arithmetischen Ausdrücken oder Funktionsaufrufen mit einer langen Liste von Parametern hilfreich).
Halten wir also fest, dass die Definition des Rumpfs einer Funktion in einem Block erfolgt. Sehen wir uns den Block genauer an, in dem die erste Funktion definiert ist. Hier finden wir zunächst die durch das Schlüsselwort if eingeleitete Abfrage, ob das dritte Argument negativ oder null ist. Diese Abfrage wird durch einen Doppelpunkt, der auf die Bedingung folgt, abgeschlossen, hierauf folgt ein Block, in dem die entsprechende Aktion spezifiziert wird. In diesem Fall handelt es sich darum, den Wert des ersten Arguments zurückzugeben, was durch das Schlüsselwort return angedeutet wird. Dieser Block wird dann verlassen, um die Alternativen zu erkunden, die in diesem Fall durch das Schlüsselwort else angedeutet werden, hierauf folgt wieder ein Doppelpunkt, auf den ein Block folgt, der hier ebenfalls den Rückgabewert für die Funktion angibt, wobei die Parameter geeignet modifiziert werden.
Wenn wir uns die zweite Funktion ansehen, so stellen wir fest, dass der definierende Block dieser Funktion, der äußeren, eine lokale Funktion enthält (nämlich die, die wir gerade definiert haben), der Rückgabewert der äußeren Funktion ist gerade ein Aufruf der lokalen Funktion, der den obigen Überlegungen zur Korrektheit entspricht. Dieser Rückgabewert wird wieder durch das Schlüsselwort return eingeleitet, darauf folgt der Wert, der zurückgegeben werden soll.
Die innere Funktion ist lokal, das bedeutet insbesondere, dass sie von außen nicht sichtbar ist, also nicht aufgerufen werden kann. Wir werden uns mit der Lokalität und Sichtbarke...
