Einordnung Rekursive Funktionen
Bisher haben wir gelernt, was die Idee dahinter ist, rekursiv Probleme zu lösen, und eben hast du hast auch sowohl eine iterative als auch rekursive Lösung des selben Problems gesehen. Jetzt wollen wir den Begriff rekursive Funktion endlich definieren.
def sum_list (l):
if (len(l) == 0):
return 0
else:
return l[0] + sum_list(l[1:])
Bei der Funktion oben siehst du, dass in der letzten Zeile die Funktion sum_list in ihrer eigenen Definition aufgerufen wird, allerdings mit einem anderen Argument. Das ist der Rekursionsschritt, den du bereits kennengelernt hast. Damit wir dem Basisfall näher kommen, müssen wir das ursprüngliche Argument (und damit das Problem) verkleinern.
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 heißt, wenn wir die Fakultätsfunktion rekursiv programmieren, muss auch ein Aufruf der Funktion in ihrer Definition auftauchen.
Aufgabe 6
Als nächstes wollen wir uns ein weiteres mathematisches Problem anschauen und programmieren: die Fibonacci-Reihe. Hier gibt es nochmal neue spannende Dinge zu entdecken.
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.
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
Aufgabe 7
- Schau dir die obigen Beispiele an und vergleiche sie mit denen für die Fakultät. Nenne Unterschiede in Bezug auf die beiden Bausteine der Rekursion.
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.
- Versuche jetzt, die Fibonacci Funktion in Python zu schreiben. Denk dabei daran was dir bei der letzten Aufgabe aufgefallen ist.
- Die Fibonacci Funktion hat noch eine weitere interessante Eigenschaft. Gib die Funktion im RecursionTutor ein und schaue dir an, wie das Diagramm aussieht.
- Nenne Unterschiede den Diagrammen davor von z.B.
facodersum_list. - Spielt es eine Rolle, in welcher Reihenfolge du die Knoten anklickst?
- Nenne Unterschiede den Diagrammen davor von z.B.
Erklärung
Die rekursiven Aufrufe bei der Fibonacci Funktion sind unabhängig voneinander und können deshalb in beliebiger Reihenfolge ausgeführt werden.
