Dein Fortschritt:
0 / 0 Aufgaben
1
Aufgabenblock — AFB I
Zehn Standardaufgaben zum Reproduzieren: rekursive Methoden auswerten, Aufrufe zählen, Aufrufbäume zeichnen, Mischen und Zerlegen von Hand ausführen. Das sind die sicheren Punkte in jeder Klausur zu Rekursion.
A1
Rekursion auswerten
AFB IDie Methode aus dem Unterricht berechnet die Anzahl der Dosen einer Pyramide mit n Reihen:
static int dosen(int n) {
if (n == 0) {
return 0;
}
return n + dosen(n - 1);
}Geben Sie den Wert von dosen(5) und die Anzahl aller Aufrufe von dosen an.
Abbruchbedingung und Rekursionsschritt: Jeder Aufruf mit
n > 0 wartet auf dosen(n − 1); erst dosen(0) liefert ohne Selbstaufruf 0.Lösung anzeigen
5 + 4 + 3 + 2 + 1 + 0 = 15; Aufrufe mit n = 5, 4, 3, 2, 1, 0 → 15 und 6 Aufrufe
A2
Der Aufrufstapel
AFB Istatic long fakultaet(int n) {
if (n <= 1) {
return 1;
}
return n * fakultaet(n - 1);
}Nennen Sie den Rückgabewert von fakultaet(5) und die Rekursionstiefe, also die größte Zahl gleichzeitig offener Aufrufe.
Rekursionstiefe: Beim Abstieg kommt für jeden Aufruf ein Rahmen auf den Stapel; der letzte ist
fakultaet(1).Lösung anzeigen
Abstieg f(5) → f(4) → f(3) → f(2) → f(1); Aufstieg 1 → 2 → 6 → 24 → 120 → 120, Tiefe 5
A3
Der Aufrufbaum von fib
AFB Istatic int fib(int n) {
if (n <= 1) {
return n;
}
return fib(n - 1) + fib(n - 2);
}Stellen Sie den Aufrufbaum von fib(5) dar und geben Sie den Rückgabewert sowie die Anzahl der Knoten (Aufrufe) an.
Aufrufe zählen: \(A(n) = 1 + A(n-1) + A(n-2)\) mit \(A(0) = A(1) = 1\).
Lösung anzeigen
A(2) = 3, A(3) = 5, A(4) = 9, A(5) = 1 + 9 + 5 = 15; fib: 0, 1, 1, 2, 3, 5 → fib(5) = 5 mit 15 Aufrufen