Materialien zum Unterricht
Arten von Funktionen
Iterative Funktionen
Iterative Funktionen - Definition
Eine iterative Funktion wiederholt einen Codeblock mit einer Schleife, bis eine festgelegte Bedingung erreicht ist.
Iterative Funktionen - Merkmale
- Ansatz: Verwendung von Schleifen
-
Speicherverbrauch: Zustand wird in Variablen gespeichert
→ konstante Speicherplatznutzung
- Besser für große
n
Iterative Funktionen - Beispiel
Rekursive Funktionen
Rekursive Funktionen - Definition
Eine rekursive Funktion ruft sich selbst auf, bis eine Abbruchbedingung erreicht ist
– dann löst sie die Aufrufe rückwärts auf.
Rekursive Funktionen - Merkmale
- Ansatz: Funktion ruft sich selbst auf
-
Speicherverbrauch: Pro Funktionsaufruf wird ein Wert gespeichert
→ Call Stack (höherer Speicherverbrauch)
- benötigt optimierung für gute Effizienz
Rekursive Funktionen - Anwendung
- Baumstrukturen (z.B. Datei-Explorer, HTML-Dokumente, Stammbäume)
- Divide-and-Conquer-Algorithmen (z.B. Mergesort, Quicksort)
- Mathematischen Funktionen (z.B. Fibonacci-Zahlen, Fakultät)
Rekursive Funktionen - Beispiel
Rekursive Funktionen - Ablauf am Beispiel
Die Funktion summe_rekursiv(n) wird mit einer Zahl n aufgerufen.
Innerhalb dieser Funktion ruft sich die Funktion selbst mit n - 1 auf.
Dieser Prozess wiederholt sich, bis sie die Abbruchbedingung erreicht wird:
summe_rekursiv(5) → 5 + summe_rekursiv(4)
summe_rekursiv(4) → 4 + summe_rekursiv(3)
summe_rekursiv(3) → 3 + summe_rekursiv(2)
summe_rekursiv(2) → 2 + summe_rekursiv(1)
summe_rekursiv(1) → 1 + summe_rekursiv(0)
summe_rekursiv(0) → 0 (Abbruchbedingung erreicht)
Nachdem die Abbruchbedingung erreicht wurde, werden die Rückgaben von unten nach oben aufgelöst:
summe_rekursiv(0) → 0
summe_rekursiv(1) → 1 + 0 = 1
summe_rekursiv(2) → 2 + 1 = 3
summe_rekursiv(3) → 3 + 3 = 6
summe_rekursiv(4) → 4 + 6 = 10
summe_rekursiv(5) → 5 + 10 = 15
Rekursive Funktionen - Übungen
-
Fibonacci-Zahlen
Implementiere eine rekursive Funktion, die die n-te Fibonacci-Zahl berechnet.
-
Potenz berechnen
Implementiere eine rekursive Funktion, um a^b zu berechnen.
-
Umkehren eines Strings (Profis)
Schreibe eine rekursive Funktion, die einen gegebenen String umkehrt.
Abschlussaufgabe
Schreibe eine rekursive Funktion, die die Fakultät einer Zahl n berechnet.
Die Zahl soll zu Beginn von der Konsole eingelesen werden.
Das Ergebnis soll auf der Kosnole ausgegeben werden.
Bei Sonderfällen soll das Programm vorher abbrechen.