Mission 14 · Code komprimieren

Was bleibt übrig?

14 / 17

Deine Mission

Du musst nicht „Rekursion können“. Lass zwei konkrete Eingaben laufen, erkenne die wiederholte Operation und ersetze sie durch eine Zeile.

Prüfungsauftrag: Bedeutung beider Funktionen nennen und jeweils einfach, nicht-rekursiv implementieren.

double F1(double x, unsigned int n) {
  if (n == 0) return 0;
  return x + F1(x, n - 1);
}

double F2(int n) {
  if (n < 2) return 0;
  return 1 + F2(n / 2);
}

Zieh F1 durch die Maschine

F1(3, 4): Tippe auf „Nächster Aufruf“. Was bleibt am Ende als Rechnung stehen?

x = 3

F1(3, 4)

Jetzt das Muster, nicht nur den Trace:

Zähle, wie oft x nach dem vollständigen Aufklappen vorkommt.

x + x + x + … ist eine bekannte Grundrechenart.

Öffnet sich nach deinem F1-Versuch.

Halbiere F2 sichtbar

Wähle für F2(13) nacheinander den nächsten ganzzahligen Wert. Jeder richtige Zug erzeugt ein +1.

Was zählt die Funktion insgesamt?

13 → 6 → 3 → 1. Wie oft konntest du durch 2 teilen?

Der Zweierlogarithmus beantwortet „Wie oft halbieren?“; bei ganzen Zahlen wird abgerundet.

Öffnet sich nach deinem F2-Versuch.

Prüfungsabschluss

Schreibe beide nicht-rekursiven Rückgabezeilen. Es zählt die Bedeutung, nicht perfektes Tippen.

F1: eine direkte Zeile F2: eine direkte Zeile

Musterweg

F1: x wird n-mal addiert, also n * x.

double F1sol(double x, unsigned int n) {
  return n * x;
}

double F2sol(int n) {
  return (int)log2(n);
}

Für positive ganze n gilt: F2 = ⌊log₂(n)⌋. Der Basisfall liefert auch für n = 0 den Wert 0; die Logarithmusform ist dort nicht definiert.

Wie sitzt Aufgabe 14?

Noch nicht markiert.