Definition

Rekursion ist eine Programmiertechnik, bei der eine Funktion sich selbst aufruft.

Zwei wichtige Teile

1. Basisfall:
   Die Bedingung, die die Rekursion beendet
2. Rekursionsfall:
   Der Selbstaufruf mit verkleinertem Problem

Schritt fur Schritt:

Was ist der Stack?

Der Call Stack ist wie ein Stapel Teller:

• Jeder Funktionsaufruf legt einen "Teller" oben drauf
• Die Funktion muss warten, bis der Aufruf daruber fertig ist
• Erst wenn eine Funktion return macht, wird ihr "Teller" entfernt

Stell dir Telefonanrufe vor:

So ist es bei countdown():

void countdown(int n) {
    if (n == 0) {
        printf("Start!\n");
        return;
    }
    printf("%d...\n", n);
    countdown(n - 1);  // ⏳ WARTET HIER!
    // Erst wenn countdown(n-1)
    // fertig ist, geht es weiter
}

Phase 1: Abtauchen (Stack fullt sich)

Jeder rekursive Aufruf wird im Speicher gestapelt. Die Funktionen warten alle!

Phase 2: Auftauchen (Stack leert sich)

Jetzt werden die wartenden Funktionen ruckwarts abgearbeitet:

Der Stack wächst und wächst...

Wie viel ist zu viel?

Mathematische Definition

n! = n × (n-1) × (n-2) × ... × 1

5! = 5 × 4 × 3 × 2 × 1 = 120

Der Code:

int fakultaet(int n) {
    if (n == 0) {
        return 1;
    }
    return n * fakultaet(n - 1);
}

printf("%d", fakultaet(5));

Löst es Schritt für Schritt:

Was ist der Call Stack?

Ein Stapel (Stack) im Speicher, der für jeden Funktionsaufruf speichert:

• Lokale Variablen
• Parameter
• Rücksprungadresse

Die Folge

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

Warum passiert das?

Fibonacci ruft sich zweimal pro Aufruf auf:

fib(n) = fib(n-1) + fib(n-2)

Das erzeugt einen Baum, keinen Stapel!

Wie schlimm ist es?

Losung 1: Iteration (Schleife)

int fib_iter(int n) {
    if (n <= 1) return n;

    int prev = 0, curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

Losung 2: Memoization (Caching)

int cache[100] = {0};  // Speicher

int fib_memo(int n) {
    if (n <= 1) return n;
    if (cache[n] != 0)
        return cache[n]; // Schon berechnet!

    cache[n] = fib_memo(n-1) + fib_memo(n-2);
    return cache[n];
}

Die Fibonacci-Folge:

Lösung Schritt für Schritt:

Schritt für Schritt:

Diese Funktion berechnet die Summe von 1 bis n!

Mathematisch:

1 + 2 + 3 + 4 = 10

Rekursiv: Von oben nach unten

int fak_rek(int n) {
    if (n == 0) return 1;
    return n * fak_rek(n-1);
}

Iterativ: Schritt für Schritt

int fak_iter(int n) {
    int erg = 1;
    for(int i=1; i<=n; i++)
        erg *= i;
    return erg;
}

Rekursiv: Natürlich!

Einfach wie im echten Leben!

Iterativ: Kompliziert!

Rekursion ist ideal für:

Iteration ist besser für:

1. Fehlender Basisfall

// FALSCH!
int falsch(int n) {
    return n * falsch(n-1);
}

2. Kein Fortschritt zum Ziel

// FALSCH!
int falsch2(int n) {
    if (n == 0) return 1;
    return n * falsch2(n); // n-1 vergessen!
}

Tipp 1: printf am Anfang

int fak(int n) {
    printf("fak(%d) aufgerufen\n", n);

    if (n == 0) return 1;
    return n * fak(n-1);
}

Tipp 2: printf mit Ergebnis

int fak(int n) {
    if (n == 0) return 1;
    int erg = n * fak(n-1);
    printf("fak(%d) = %d\n", n, erg);
    return erg;
}

Code A: printf VOR Rekursion

void test(int n) {
    if (n > 0) {
        printf("%d ", n);  // ← ZUERST drucken
        test(n - 1);       // ← DANN abtauchen
    }
}
test(4);

Code B: printf NACH Rekursion

void test(int n) {
    if (n > 0) {
        test(n - 1);       // ← ZUERST abtauchen
        printf("%d ", n);  // ← DANN drucken
    }
}
test(4);

Problem: Es fehlt der Basisfall!

So wäre es richtig:

int summe(int n) {
    if (n == 0) return 0;  // ← Basisfall!
    return n + summe(n - 1);
}

Diese Funktion berechnet basis^exp = 2⁴!

Mathematisch:

2⁴ = 2 × 2 × 2 × 2 = 16

Jede Rekursion braucht:

Das Wichtigste: