Vertiefung - rekursive Folgendarstellung
Zur Orientierung
Im letzten Abschnitt wurde gezeigt, dass eine Zahlenfolge eine Funktion ist. Die Zuordnungen der Folge können dabei mit einer expliziten Berechnungsformel (als Funktionsgleichung) festgelegt werden. Alternativ hierzu ist auch eine Festlegung mit einer rekursiven Berechnungsformel möglich. Wir betrachten solche rekursiven Festlegungen hier genauer.
Eine Folge rekursiv festlegen
Wir betrachten die rekursive Darstellung der Begrüßungsfolge genauer. Sie besteht aus zwei Gleichungen.
| $a_1 = 0$ | (Rekursionsanfang) |
| $a_n = a_{n-1} + (n-1)$ für $n = 2, 3, ...$ | (Rekursionsschritt) |
Die Rolle dieser Gleichungen erkennt man, wenn man sich eine rekursive Berechnung von Folgengliedern mit diesen rekursiven Gleichungen anschaut.
| rekursiver Abstieg | rekursiver Aufstieg | ||
|---|---|---|---|
| $\downarrow$ | $a_4 = a_3 + 3$ | $a_4 = 3 + 3 = 6$ | |
| $\downarrow$ | $a_3 = a_2 + 2$ | $a_3 = 1 + 2 = 3$ | $\uparrow$ |
| $\downarrow$ | $a_2 = a_1 + 1$ | $a_2 = 0 + 1 = 1$ | $\uparrow$ |
| $a_1 = 0$ | $a_1 = 0$ | $\uparrow$ |
Aufgabe 1
(a) Rekursive Festlegungen führen zu zurücklaufenden Berechnungen. Erkläre die Rolle des Rekursionsanfangs und des Rekursionsschritts bei der Ausführung einer Berechnung am gezeigten Beispiel.
(b) Begründe, warum eine rekursive Berechnung eines Folgenglieds recht aufwendig ist. Betrachte hierzu die rekursive Berechnung von $a_{100}$. Wie viele Rechnenschritte sind hier erforderlich? Vergleiche mit der Berechnung mit der expliziten Berechnungsformel $a_n = \dfrac{n \cdot (n-1)}{2}$.
Aufgabe 2
Betrachte die rekursive Darstellung der Türme-von-Hanoi-Folge:
$a_1 = 1$
$a_n = 2 \cdot a_n + 1$ für $n = 2, 3, ...$
Verdeutliche in einer Übersicht (wie oben), wie die rekursive Berechnung von $a_5$ funktioniert.
Aufgabe 3
Betrachte die Sparschwein-Folge: Bei einem Sparschwein werden jeden Tag 0.50 € eingeworfen. Das Sparschwein ist zu Beginn leer. Die Folge $a_0; a_1; a_2; \dots$ beschreibt, wieviel Geld sich nach $0; 1; 2; \dots$ Tagen im Sparschwein befindet.
Entwickle eine rekursive Berechnungsformel (bestehend aus einem Rekursionsanfang und einem Rekursionsschritt) für diese Folge.
Rekursive Folgendefinitionen
Wir fassen die Ergebnisse zusammen.
Eine rekursive Folgendefinition besteht aus einer oder mehreren Gleichungen, die den Rekursionsanfang festlegen, sowie einer oder mehreren Gleichungen, die den Rekursionsschritt festlegen.
Beachte, dass im Rekursionsschritt vorangehende Folgenglieder bei der Festlegung des aktuellen Folgenglieds benutzt werden. Beachte auch, dass man einen Rekursionsanfang benötigt, damit die rücklaufenden Berechnungen zu einem Ende kommen.
Bei der rekursiven Berechnung von Folgengliedern wird der Rekursionsschritt absteigend solange wiederholt, bis man den Rekursionsanfang benutzen kann, um aufsteigend den Wert des Folgenglieds zu bestimmen.
