Beide Ansätze lösen das gleiche Problem — aber auf ganz unterschiedliche Weise. Hier entdeckst du, wie der Computer „denkt" wenn er ein Fraktal zeichnet.
Eine Funktion ruft sich selbst auf, bis ein Basisfall erreicht wird. Das Problem wird in immer kleinere Teilprobleme zerlegt.
function sierpinski(tiefe, ax, ay, bx, by, cx, cy) {
if (tiefe === 0) {
zeichneDreieck(ax, ay, bx, by, cx, cy);
return; // ← Basisfall
}
// Mittelpunkte berechnen
let mx_ab = (ax+bx)/2, my_ab = (ay+by)/2;
let mx_bc = (bx+cx)/2, my_bc = (by+cy)/2;
let mx_ca = (cx+ax)/2, my_ca = (cy+ay)/2;
sierpinski(tiefe-1, ax, ay, mx_ab, my_ab, mx_ca, my_ca);
sierpinski(tiefe-1, mx_ab, my_ab, bx, by, mx_bc, my_bc);
sierpinski(tiefe-1, mx_ca, my_ca, mx_bc, my_bc, cx, cy);
}
Statt sich selbst aufzurufen, verwendet die Funktion eine Schleife und einen eigenen Stapel (Stack), um die Teilprobleme abzuarbeiten.
function sierpinskiIterativ(tiefe, ax, ay, bx, by, cx, cy) {
let stack = [{t: tiefe, ax, ay, bx, by, cx, cy}];
while (stack.length > 0) {
let {t, ax, ay, bx, by, cx, cy} = stack.pop();
if (t === 0) {
zeichneDreieck(ax, ay, bx, by, cx, cy);
continue; // ← Basisfall
}
let mx_ab = (ax+bx)/2, my_ab = (ay+by)/2;
let mx_bc = (bx+cx)/2, my_bc = (by+cy)/2;
let mx_ca = (cx+ax)/2, my_ca = (cy+ay)/2;
stack.push({t:t-1, ax:mx_ca, ay:my_ca, bx:mx_bc, by:my_bc, cx, cy});
stack.push({t:t-1, ax:mx_ab, ay:my_ab, bx, by, cx:mx_bc, cy:my_bc});
stack.push({t:t-1, ax, ay, bx:mx_ab, by:my_ab, cx:mx_ca, cy:my_ca});
}
}
Beobachte, wie der Call-Stack bei der Rekursion wächst und schrumpft. Jedes farbige Kästchen ist ein Funktionsaufruf. Drücke „Start", um die Animation zu sehen.
Beide erzeugen das gleiche Bild — der Weg dahin ist verschieden. Links: Rekursion (violett). Rechts: Iteration mit eigenem Stack (cyan).
Fraktale sind das perfekte Anschauungsobjekt für Rekursion: Jeder Teil ist eine kleinere Kopie des Ganzen. Dieses Prinzip der Selbstähnlichkeit ist genau das, was eine rekursive Funktion tut — sie löst ein großes Problem, indem sie kleinere Versionen von sich selbst löst.
Ob in der Natur (Bäume, Farne, Küstenlinien, Blumenkohl) oder in der Informatik (Sortieralgorithmen, Dateisysteme, Compiler) — Rekursion ist überall!