1    Kleine Aufgaben

Zu Beginn betrachten wir einige einfache Aufgaben, die sich mit einigen relativ kurzen Funktionen lösen lassen. Auch wenn diese Aufgaben klein sind, erlauben sie uns doch, einige interessante Problemlösungstechniken zu erarbeiten. Betrachten Sie diese Aufgaben als gutes Aufwärmtraining.

1.1    Die Fibonacci-Folge

Die Fibonacci-Folge ist eine Folge von Zahlen, in der jede Zahl außer der ersten und der zweiten die Summe ihrer beiden Vorgänger ist:

Der Wert der ersten Fibonacci-Zahl in der Folge ist 0. Der Wert der vierten Fibonacci-Zahl ist 2. Daraus folgt, dass man folgende Formel verwenden kann, um den Wert jeder beliebigen Fibonacci-Zahl n in der Reihe zu erhalten:

1.1.1    Ein erster rekursiver Ansatz

Die obige Formel zur Berechnung einer Zahl in der Fibonacci-Folge (grafisch dargestellt in Abbildung 1.1) ist eine Form von Pseudocode, die sich trivial in eine rekursive Python-Funktion übertragen lässt. (Eine rekursive Funktion ist eine Funktion, die sich selbst aufruft.) Diese mechanische Übertragung dient als unser erster Ansatz, eine Funktion zu schreiben, die den angegebenen Wert der Fibonacci-Folge zurückliefert.

Listing 1.1    fib1.py

Versuchen wir, diese Funktion auszuführen, indem wir sie mit einem Wert aufrufen.

Listing 1.2    fib1.py (Fortsetzung)

Abbildung 1.1    Die Höhe jedes Strichmännchens ist die Summe der Höhe der beiden vorherigen Strichmännchen.

Oje! Wenn wir versuchen, fib1.py auszuführen, erzeugen wir einen Fehler:

Das Problem ist, dass fib1() immer weiterlaufen wird, ohne je ein Ergebnis zurückzuliefern. Jeder Aufruf von fib1() erzeugt zwei weitere Aufrufe von fib1(), ohne dass ein Ende in Sicht wäre. Einen solchen Umstand nennt man Endlosrekursion (siehe Abbildung 1.2), das rekursive Gegenstück zu einer Endlosschleife.

Abbildung 1.2    Die rekursive Funktion »fib(n)« ruft sich selbst mit den Argumenten »n–2« und »n–1« auf.

1.1.2    Abbruchbedingungen verwenden

Wie Sie merken, gibt es keine Anzeichen aus Ihrer Python-Umgebung, dass irgendetwas mit fib1() nicht stimmt, solange Sie die Funktion nicht ausführen. Es ist Aufgabe des Programmierers, Endlosrekursionen zu vermeiden, nicht diejenige des Compilers oder Interpreters. Der Grund für die Endlosrekursion ist, dass wir nie eine Abbruchbedingung festgelegt haben. In einer rekursiven Funktion dient eine Abbruchbedingung als Haltepunkt.

Im Fall der Fibonacci-Funktion haben wir natürliche Abbruchbedingungen in Form der ersten beiden Folgewerte 0 und 1. Weder 0 noch 1 ist die Summe der vorigen beiden Zahlen in der Folge. Stattdessen handelt es sich um die speziellen ersten beiden Werte. Versuchen wir, sie als Abbruchbedingungen festzulegen.

Listing 1.3    fib2.py

fib2() kann erfolgreich aufgerufen werden und liefert korrekte Ergebnisse zurück. Versuchen Sie, sie mit einigen kleinen Werten aufzurufen.

Listing 1.4    fib2.py (Fortsetzung)

Versuchen Sie nicht, fib2(50) aufzurufen. Die Ausführung wird niemals enden! Warum? Jeder Aufruf von fib2() erzeugt zwei weitere Aufrufe von fib2() durch die rekursiven Aufrufe fib2(n - 1) und fib2(n - 2) (siehe Abbildung 1.3). Der Aufrufbaum wächst mit anderen Worten exponentiell. Ein Aufruf von fib2(4) erzeugt beispielsweise diese Gesamtmenge von Aufrufen:

Abbildung 1.3    Jeder nicht in die Abbruchbedingung fallende Aufruf von »fib2()« erzeugt zwei weitere Aufrufe von »fib2()«.

Wenn Sie sie zählen (und wie Sie sehen werden, wenn Sie ein paar Ausgabebefehle hinzufügen), entstehen 9 Aufrufe von fib2(), um lediglich das vierte Element zu berechnen! Es wird schlimmer. 15 Aufrufe werden benötigt, um Element 5 zu berechnen, 177 Aufrufe, um Element 10 zu berechnen, und 21.891 Aufrufe für Element 20. Das können wir besser machen.

1.1.3    Memoisation eilt zu Hilfe

Memoisation ist ein Verfahren, bei dem Sie die Ergebnisse von Berechnungen speichern, sobald sie abgeschlossen sind, damit Sie sie nachschlagen können, wenn Sie sie erneut brauchen, statt sie ein zweites (oder millionstes) Mal berechnen zu müssen (siehe Abbildung 1.4).[ 4 ]

Abbildung 1.4    Die menschliche Memoisations-Maschine

Schreiben wir eine neue Version der Fibonacci-Funktion, die ein Python-Dictionary zum Zweck der Memoisation verwendet.

Listing 1.5    fib3.py

Sie können fib3(50) jetzt sicher aufrufen.

Listing 1.6    fib3.py (Fortsetzung)

Ein Aufruf von fib3(20) erzeugt nur 39 Aufrufe von fib3() im Gegensatz zu den 21.891 Aufrufen von fib2(), die aus dem Aufruf von fib2(20) entstehen. memo wird mit den früheren Abbruchbedingungen 0 und 1 vorausgefüllt, was fib3() vor der Komplexität einer weiteren if-Anweisung bewahrt.

1.1.4    Automatische Memoisation

fib3() kann noch weiter vereinfacht werden. Python enthält einen eingebauten Decorator für die automatische Memoisation jeder beliebigen Funktion. In fib4() wird der Decorator @functools.lru_cache() mit genau demselben Code wie in fib2() verwendet. Jedes Mal, wenn fib4() mit einem bisher unbekannten Argument ausgeführt wird, sorgt der Decorator dafür, dass der Rückgabewert gecacht wird. Bei weiteren Aufrufen von fib4() mit demselben Argument wird der frühere Rückgabewert von fib4() aus dem Cache gelesen und zurückgegeben.