Wir haben gesehen, dass Funktionen es uns erlauben, Teile unseres Codes zu organisieren und wiederzuverwenden. Wir haben außerdem auch gesehen, dass Funktionen unter Verwendung anderer Funktionen definiert werden können. In dieser Lektion lernen wir, dass eine Funktion mit sich selbst definiert werden kann! Diese sehr hilfreiche Herangehensweise nennt man Rekursion. Gerüchte sagen: "Um Rekursion zu verstehen, musst du zuerst Rekursion verstehen."

Beispiel

In unserer Lektion zu Schleifen verwendeten wir eine while Schleife, um die folgende Ausgabe zu erzeugen.

5
4
3
2
1
Blastoff!

Hier ist ein Programm, das Rekursion verwendet, um den selben Effekt zu erzielen.

Lass uns ein paar zusätzliche print Statements hinzufügen, damit wir verstehen, wie das Programm funktioniert. Diese Version des Programms holt sich außerdem den Startwert für den Countdown als Input.

Wenn du möchtest, kannst du Teststatements eingeben beim obigen Programm verwenden, um andere Eingaben auszuprobieren. Versuche es zuerst mit 0 und schau, was passiert, danach mit 1.

Wenn die Eingabe 5 ist, ruft das Programm zuerst eine Kopie der countdown Funktion auf mit n=5, was 5 ausgibt und countdown(4) aufruft. Dies wird fortgeführt bis countdown(0), welches "Blastoff!" ausgibt und countdown nicht mehr aufruft. Wenn Python damit fertig ist, den n=0 Aufruf der countdown Funktion auszuführen, kehrt Python zu der Funktion zurück, die ihn ursprünglich aufgerufen hat, nämlich der n=1 Aufruf von countdown. Dann kehren wir zurück zum n=2 Aufruf und so weiter.

Um unser Verständnis doppelt zu prüfen, können wir auch den rekursiven Code visualisieren:

Die nächste Wendung, die die Rekursion einzigartig macht gegenüber denen, die wir vorher gesehen haben, ist,
dass mehrere Versionen der Funktion gleichzeitig laufen. Sozusagen korrespondiert jeweils mehr als ein Rahmen mit der gleichen Funktion. Dies ist so ziemlich das gleiche wie was wir in der Visualisierung sahen, wo eine Funktion eine andere aufrief, nur ist jetzt die aufrufende und die aufgerufte Funktion die gleiche. Allerdings musst du vorsichtig sein um festzustellen, dass bei jedem Schritt nur die "aktuellen" Variablen (der neuste/ganz untere Rahmen) wirklich benutzt werden — die nichtunteren Rahmen sind "angehalten" und ihre Variablen unzugänglich.

Jetzt bist du an der Reihe, Code zu schreiben. Modifiziere die countdown Funktion so, dass sie aufsteigend zählt anstatt absteigend.

Lass uns als nächstes unser countdown Programm so modifizieren, dass wir in 2er-Schritten zählen. Die Ausgabe sollte 5, 3, 1, Blastoff! sein. Wir werden das Funktionsargument von n-1 zu n-2 ändern. Gibt es noch etwas anderes, das geändert werden muss?

Wie du sehen kannst, hat dieses Programm nicht so funktioniert, wie wir das wollten. Es hat 5, 3, 1, wie geplant ausgedruckt, aber statt inne zu halten, hat es weitergemacht mit -1, -3, -5 und lief dann endlos weiter. (Genau genommen benötigt es nicht nur zuviel Zeit, sondern auch zuviel Speicher, da jeder rekursive Aufruf ein bißchen mehr Arbeitsspeicher benötigt.)

Wenn wir eine rekursive Funktion entwerfen, müssen wir vorsichtig sein, dass ihre Folge von Aufrufen nicht ewig läuft! Verändere das countdownBy2 Programm oben so, dass es korrekt bei 1 (oder 2, wenn n gerade ist) stoppt und 'Blastoff!' ausdruckt.

Rekursive Funktionen entwerfen

Eine rekursive Funktion ist lediglich eine Funktion, die sich selbst aufruft. Aber es muss einige Gelegenheiten geben, bei denen die Funktion sich nicht selbst aufruft, oder das Programm würde ewig laufen, wie wir das oben gesehen haben. Ein grundsätzlicher Fall ist der Teil einer rekursiven Funktion, wo es sich nicht selbst aufruft. Im Beispiel oben ist es so, dass der grundsätzliche Fall n<=0 war. Bei der Entwerfung einer rekursiven Funktion erfordert es, dass du vorsichtig einen grundsätzlichen Fall auswählst und sicherstellst, dass jede Funktionssequenz irgendwann einen grundsätzlichen Fall erreicht.

In der nächsten Übung wurde der grundsätzliche Fall schonmal für dich programmiert, aber du wirst den Rest der rekursiven Funktion schreiben.

Nun wirst du eine rekursive Funktion schreiben, die Quersumme als Subroutine aufruft.

Programmierübung: Einstellige Quersumme

Die einstellige Quersumme (englisch: digital root) einer nicht-negativen Ganzzahl n wird folgendermaßen berechnet. Beginne damit, die Ziffern von n aufzuaddieren. Die Ziffern der Zahl, die daraus resultiert, werden dann aufsummiert und dieser Prozess wird fortgesetzt, bis eine einstellige Zahl erreicht wird. Zum Beispiel ist die einstellige Quersumme von 2019 gleich 3 weil 2+0+1+9=12 und 1+2=3. Schreibe eine rekursive Funktion digitalRoot(n), welche die einstellige Quersumme von n ausgibt.
Nimm an, dass eine Arbeitsdefinition von digitalSum für dein Programm angegeben wird.

# Lösche diesen Kommentar und gib deinen Code hier ein

Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

Übungen

Kurzübung: GGT

Was ist die Ausgabe des folgenden rekursiven Programms?

def ggT(a, b):
  if b == 0: return a
  return ggT(b, a % b)
print(ggT(20, 12))

Deine Antwort (gib eine Zahl ein):

Korrekt! Dieses auffällig kurze Programm berechnet den größten gemeinsamen Teiler von zwei Zahlen und ist bekannt als Euklidischer Algorithmus, einer der ältesten bekannten Algorithmen.

Programmierübung: Collatz-Folge

Die Collatz-Folge, die mit einer positiven Ganzzahl n beginnt, wird erzeugt, indem man zwei einfache Regeln befolgt. Wenn n gerade ist, ist die nächste Zahl in der Folge n/2. Wenn n ungerade ist, ist die nächste Zahl in der Folge 3*n+1. Wenn wir den Prozess wiederholen, erzeugen wir die Collatz-Folge, die auf Englisch hailstone sequence heißt. Schreibe eine rekursive Funktion hailstone(n), welche die Collatz-Folge erzeugt, beginnend bei n. Höre auf, wenn die Sequenz die Zahl 1 erreicht (sonst würden wir ewig in einem 1, 4, 2, 1, 4, 2, ... loop stecken bleiben)
Zum Beispiel, wenn n=5, sollte Dein Programm die folgende Folge ausgeben:

# Lösche diesen Kommentar und gib deinen Code hier ein

Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

Mathematiker glauben, dass jede Collatz-Folge irgendwann 1 erreicht, egal, mit welchem Wert von n wir anfangen. Es hat jedoch noch keiner beweisen können.

Verschachtelte Listen

Hier ist eine interessante natürliche Anwendung von Rekursion. Eine verschachtelte Liste ist eine, wo man Listen in andere Listen verpackt, möglicherweise mehrmals. Zum Beispiel sind verschachtelte Listen von Integers [[1, 2], [9, 10]] sowie [[1], 2] und x = [[1], 2, [3, [[4]]]]. Das letzte Beispiel ist eine Liste mit drei Elementen: x[0]==[1] am Anfang, dann x[1]==2, dann x[2]==[3, [[4]]]. (So hat x, gesehen als Liste, Länge 3). Beachte, dass eine Liste wie [1, 2, 3] auch als verschachtelte Liste gilt. Können wir eine Funktion schreiben um die totale Summe jeder beliebigen verschachtelten Liste von Integern zu finden? Zum Beispiel sollte sie bei der Eingabe [[5], 2, [10, 8, [[7]]]] der Wert 32 zurückgeben.

Diese Aufgabe ist schwer für eine while- oder for-Schleife, da wir eine Funktion wollen, die mit verschachtelten Listen beliebiger Erscheinung/Form arbeitet. Allerdings haben verschachtelte Listen eine natürliche rekursive Struktur:
eine verschachtelte Liste, wo jedes ihrer Elemente entweder (a) ein Integer oder (b) eine verschachtelte Liste ist. Und sobald wir die Summe jedes Unterteils der Hauptliste berechnen, ist die Summe dieser Werte die Gesamtsumme. Wir können dies mit dem folgenden Code ausdrücken; es benutzt isinstance(x, int), das einen boolean-Wert liefert, der uns sagt ob x vom Typ Integer ist (im Gegensatz zur Liste).

Wird Rekursion benutzt um verschachtelte Listen in kleinere Teile zu spalten? Zum Beispiel macht nestedListSum([1, [3, 4], 5]) insgesamt 6 rekursive Aufrufe: den am Anfang, dann 1, dann [3, 4], dann 3, dann 4, (nach dem [3, 4] total als 7 zurückgegeben wird) und als letztes bei 5 (nach dem die Gesamtsumme 13 erreicht ist). Hier ist der gleiche Code im Visualisierer.

This Rules

Rekursion ist auch mit Fraktalen verwandt - Bilder, die mehrere kleinere Kopien ihrer selbst enthalten. Das Banner oben auf dieser Seite ist ein Beispiel. Die nächste Übung führt ein einfaches, sich wiederholendes Muster aus, indem es Rekursion verwendet.

Glückwunsch! Du bist bereit, zur nächsten Übung zu gehen!