16: Rekursion

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.

Beispiel
Ein Countdown, der Rekursion verwendet.

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.

Beispiel
Ein Countdown, der Rekursion verwendet.
Du kannst die Eingabe für das Programm in die Box unten eingeben.

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.

Programmierübung: Blast Up
Schreibe eine rekursive Funktion countup(n), die 'Blastoff!' ausgibt, und im Anschluss die Zahlen 1 bis n in eigenen Zeilen. Tipp
Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

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?

Beispiel
Versuche, in Zweierschritten herunterzuzählen

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.

Programmierübung: Double Time
Verändere dieses rekursive Programm so, dass es korrekt in Zweierschritten herunter zählt.
Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

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.

Programmierübung: Quersumme
Die Quersumme (englisch: digital sum) einer Zahl n ist die Summe der Ziffern, aus denen sie besteht. Schreibe eine rekursive Funktion digitalSum(n), die eine positive Ganzzahl n nimmt und ihre Quersumme ausgibt. Zum Beispiel sollte digitalSum(2019) 12 ausgeben, weil 2+0+1+9=12. Tipp #1 Tipp #2
Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

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.
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))
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:

5
16
8
4
2
1
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).

Beispiel: Summing a Nested List
Berechnen der Summe der Elemente in einer verschachtelten Liste. Wenn du Run drückst, wirst du seine Werte an einigen Tests sehen.
Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

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.

Programmierübung: Searching a Nested List
Indem du etwas ähnliches wie nestedListSum schreibst, definiere eine rekursive Funktion

nestedListContains(NL, target)
die eine verschachtelte Liste NL von Integern und einen Integer target einließt und angibt, ob target irgendwo in der verschachtelten Liste enthalten ist. Dein Code sollte den boolean-Wert True zurückgeben, wenn es enthalten ist, wenn nicht, dann False.
Zum Beispiel sollte nestedListContains([1, [2, [3], 4]], 3) sTrue ergeben und nestedListContains([1, [2, [3], 4]], 5) False.
Gib Testbefehle wie print(meinefunktion("Test-Argument")) unten ein.

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.

Sortierübung: Fractal Ruler
Entwirre die Zeilen, um ein Programm zu schaffen, das ein rekursives linealartiges Programm hervorbringt. Zum Beispiel, wenn n=3, sollte das Programm das folgende Design ausgeben.

-
--
-
---
-
--
-
  • print(n * '-')
  • ruler(n - 1)
  • print('-')
  • ruler(n - 1)
  • def ruler(n):
  • if n == 1:
  • else:

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