MISSION 13 · DOPPELREKURSION

Ein Ruf wird
zum Echo.

Du musst Rekursion noch nicht „im Kopf können“. Klappe einfach jeden Aufruf in seine zwei Kinder auf.

13 / 17

Deine Mission

Erzeuge den Aufrufbaum für N=4. Lies ihn danach auf zwei Arten und bestimme die gesamte Aufrufzahl.

30-Sekunden-Start: Klicke unten nur auf die Wurzel 4. Mehr musst du noch nicht wissen.

fun1(N):                 fun2(N):
  falls N == 1:           falls N == 1:
    gib N aus               gib N aus
  sonst:                  sonst:
    gib N aus               fun2(N-1)
    fun1(N-1)               gib N aus
    fun1(N-1)               fun2(N-1)

DIREKTE MANIPULATION

Baue alle echten Aufrufe

1 sichtbarer Aufruf

Jeder Knoten mit N > 1 startet zweimal N−1. Klicke offene Knoten auf. Ein 1-Knoten stoppt.

Wann wird gedruckt?

Der Baum ist derselbe. Nur der Zeitpunkt von cout ändert die Ausgabereihenfolge.

fun1

cout steht vor beiden Kindern.

fun2

cout steht zwischen beiden Kindern.

Setze einen kleinen Stift direkt an die cout-Zeile. Folge dem Code. Sobald der Stift diese Zeile erreicht, notierst du den aktuellen Knoten.
fun1 liest den Aufrufbaum in Preorder, fun2 in Inorder. Die Namen sind weniger wichtig als die Position der Ausgabezeile.

Die Tiefen-Falle entschärfen

Wie viele Funktionsaufrufe gibt es bei fun1(4) insgesamt — inklusive des ersten Aufrufs?

Tiefe 11Tiefe 22Tiefe 34Tiefe 48
Tiefe sagt nur, wie lang ein Weg ist. Die Aufrufzahl zählt jeden Knoten auf allen Wegen: 1 + 2 + 4 + 8.

Prüfungsabschluss

Liefere genau die vier Ergebnisse der Originalaufgabe. Leerzeichen oder Kommas zwischen Ausgaben sind beide okay.

Der Musterweg öffnet nach deinem ersten Prüfungsversuch. Ohne Versuch: zweimal bewusst auf „Musterweg“ klicken.

Wie steht Aufgabe 13?

Würdest du morgen wieder alle Knoten zählen — nicht nur die Tiefe?

Noch nicht markiert.

Aufgabe und Musterlösung: Probeklausur.pdf, Aufgabe 13. Lernführung: lokale Problemnotizen und ADS-Lernpräferenzen.