inf-schule | Erkundung » Fachkonzept

Fachkonzept

In den letzten beiden Kapiteln haben wir uns das Konzept der Rekursion anhand der Diagramme des RecursionTutors angeschaut. Fassen wir die daraus gewonnene Erkenntnis nochmal zusammen und versuchen, eine erste Definition zu finden.

Rekursion ist eine Strategie, um komplizierte Probleme zu lösen, deren Lösung auf dem direktesten Weg nicht ersichtlich oder zu schwer ist. Das gilt vor allem für Probleme, die von Natur aus eine Struktur haben, die sich selbst wiederholt.

Die Kernidee der rekursiven Lösungsstrategie ist also:

Anstatt ein Problem direkt zu lösen, führen wir es auf eine kleinere Version desselben Problems zurück. Das wiederholen wir so lange, bis das Problem so klein geworden ist, dass wir es direkt lösen können. Mit den Lösungen der vielen kleineren Versionen des Problems können wir dass das ursprüngliche Problem lösen.

Eine Alternative Lösungsstrategie ist die Iteration, also mithilfe von Schleifen. Oft ist die rekursive Lösung allerdings kürzer, eleganter und einfacher zu verstehen.

Aufgabe 5

Im Folgenden siehst du erneut das Diagramm der Funktion zum Aufsummieren aller Elemente einer Liste. Daneben siehst du ein Eingabefeld mit der Definition der Funktion sowie ein Feld zur Eingabe von Funktionsaufrufen wie die, die du bereits ausprobiert hast.

Spiele etwas mit der Definition der Funktion herum. Ändere zum Beispiel den Rückgabewert in Zeile 3 auf return 1 und werte das Diagramm aus. Was hat sich im Vergleich zu vorher verändert?

Evtl. hier irgendwo noch iterative Lösung des Problems um Unterschied kurz zu zeigen?

Die zwei Bausteine der Rekursion

Rekursive Programme benötigen zum Lösen von Problemen immer zwei ganz bestimmte Bausteine

1. Der Basisfall

Der Basisfall ist der Punkt, an dem das Problem so klein und einfach ist, dass wir die Lösung davon direkt kennen, ohne das Problem weiter verkleinern zu müssen. Das ist der Punkt, an dem die Rekursion aufhört. Ohne einen Basisfall würden wir nie fertig werden mit der Lösung eines Problems.

In unseren Beispiel sumList wäre der Basisfall die leere Liste, also eine Liste ohne aufzusummierende Elemente. bei der quersumme wäre der Basisfall eine Zahl mit nur einer Ziffer, bei der wir nichts aufsummieren müssen. Also die jeweils kleinste Version des Problems. Zu dieser Version sagen wir auch Instanz.

2. Der Rekursionsschritt

Der Rekursionsschritt ist der Schritt, in dem wir das Problem auf eine kleinere Version desselben Problems zurückführen. Dann versuchen wir das Problem zu lösen, aber eben die kleinere Version bzw. Instanz davon. Wir starten also unsere gesamte Lösungsstrategie komplett neu, allerdings mit einer verkleinerten Version des Problems. Das machen wir, um dem Basisfall Schritt für Schritt näher zu kommen.

Aufgabe 6

In Python können wir nicht nur Zahlen miteinander addieren, sondern auch Strings. Dabei ist die Summe zweier Strings die Aneinanderreihung oder Verkettung der beiden Strings. Dazu sagen wir auch Konkatenation.

Erneut schauen wir uns die Funktion zum Aufsummieren aller Elemente einer Liste an. Diesmal wollen wir allerdings keine Liste von Zahlen aufsummieren, sondern Strings. Klicke dich durch das Diagramm. Klicke dich durch die Funktion, bis sie einen Fehler wirft. Finde heraus wo der Fehler liegt und korrigiere ihn. Warum ist die ursprüngliche Implementierung falsch?

(Wird noch entfernt!) Fehler ist der Basisfall, da "hallo" + 0 kein gültiger Ausdruck ist. Hier soll erkannt werden, dass die Lösung der einzelnen Probleminstanzen alle den selben Typen haben müssen, und deshalb die Zahl 0 und der String "hallo" nicht kompatibel sind.

Rekursive Funktionen

Bisher haben wir gelernt was die Idee dahinter ist, rekursiv Probleme zu lösen, und du hast auch schon Funktionen gesehen. Jetzt wollen wir uns die Funktionen, die das jeweilige Problem lösen, nochmal genauer anschauen.

Im Folgenden betrachten wir die Fakultätsfunktion als eines der bekanntesten Beispiele für eine rekursive Funktion. Die Fakultät kennst du vielleicht noch aus dem Mathe-Unterricht. Die Fakultät einer Zahl n ist definiert als das Produkt aller natürlichen Zahlen von 1 bis n, oder als Formel:

$n! := \prod_{k=1}^{n} k = 1 \cdot 2 \cdot 3 \cdot\ ...\ \cdot n$

Wir können die Fakultät aber auch rekursiv definieren:

$n! := n \cdot (n-1)!$

Zusätzlich ist definiert, dass $0! = 1$ ist. Dieser Fall bildet gleichzeitig unseren Basisfall, da die 0 die kleinste natürliche Zahl und damit die kleinste Instanz des Problems ist.

Beispiele:

$0! = 1$
$1! = 1$
$2! = 2 \cdot 1! = 2 \cdot 1 = 2$
$3! = 3 \cdot 2! = 3 \cdot 2 \cdot 1! = 3 \cdot 2 \cdot 1 = 6$
$4! = 4 \cdot 3! = 4 \cdot 3 \cdot 2! = 4 \cdot 3 \cdot 2 \cdot 1! = 4 \cdot 3 \cdot 2 \cdot 1 = 24$

Die Fakultät, erkennbar an dem !, taucht also auch auf der rechten Seite der Definition auf. Das müssen wir jetzt auch irgendwie in den Programmcode übertragen, in dem wir die Funktion selbst in ihrer Definition aufrufen. Damit machen wir eine Funktion zu einer rekursiven Funktion.

Definition: Rekursive Funktionen sind Funktionen, die sich selbst aufrufen. Das bedeutet, dass innerhalb der Funktion ein Aufruf der Funktion selbst stattfindet.

In anderen Programmiersprachen müssen wir die Funktion, damit sie sich selbst aufrufen darf, auf eine bestimmte Weise definieren. In Python müssen wir das nicht, hier darf jede Funktion sich automatisch selbst aufrufen. Wie praktisch!

Aufgabe 7

Im Folgenden findest du die Fakultätsfunktion (engl. factorial) als Lückentext in Python. Es fehlen noch die zwei Bausteine der Rekursion, der Basisfall und der Rekursionsschritt. Versuche die Lücken zu füllen und mithilfe des Diagramms zu verifizieren.

Als nächstes wollen wir uns ein weiteres mathematisches Problem anschauen: die Fibonacci-Reihe.

Aufgabe 8

Die Fibonacci-Folge ist rekursiv definiert durch:

Erste Fibonacci-Zahl: fib(0) = 0
Zweite Fibonacci-Zahl: fib(1) = 1
n+1-te Fibonacci-Zahl: fib(n) = fib(n-1) + fib(n-2) für n > 1

Das hießt die n+1-te Fibonacci-Zahl ist die Summe der beiden vorherigen Fibonacci-Zahlen. Schau dir die folgenden Beispiele an und vergleiche sie mit der Fakultät. Was ist diesmal anders in Bezug auf die beiden Bausteine der Rekursion.

Beispiele:

fib(2) = fib(1) + fib(0) = 1 + 0 = 1
fib(3) = fib(2) + fib(1) = fib(1) + fib(0) + 1 = 1 + 0 + 1 = 2
fib(4) = fib(3) + fib(2) = fib(2) + fib(1) + fib(1) + fib(0) = fib(1) + fib(0) + 1 + 0 + 1 = 1 + 0 + 1 + 1 = 3

Erklärung

Wir sehen also: eine Funktion kann auch mehr als einen rekursiven Aufrufe haben. Rekursive Funktionen mit maximal einem rekursiven Aufruf nennen wir "linear rekursiv", solche mit zwei rekursiven Aufrufen, nennen wir "binär rekursiv". Außerdem fällt auf, dass die Fibonacci-Funktion zwei Basisfälle hat, also zwei Instanzen des Problems, die keinen rekursiven Aufruf erfordern. Das liegt daran, wie die Fibonacci-Zahlen definiert sind.

Aufgabe 9

Versuche jetzt, die Fibonacci Funktion in Python zu schreiben. Denk dabei daran was dir bei der letzten Aufgabe aufgefallen ist.

Aufgabe 10

Die Fibonacci Funktion hat noch eine weitere interessante Eigenschaft. Gib die Funktion im RecursionTutor ein und schaue dir an, wie das Diagramm aussieht.

Welche Unterschiede fallen dir zu den Diagrammen davor auf?
Spielt es eine Rolle, in welcher Reihenfolge du die Knoten anklickst?