Ausführbare C-Docs: Rekursion

Q: Was ist Rekursion in C?

Eine Funktion, die sich selbst aufruft, um eine kleinere Fassung desselben Problems zu lösen. Jede rekursive Funktion braucht zwei Dinge: einen Basisfall, der ohne Rekursion zurückkehrt, und einen Rekursionsfall, der messbar näher an ihn heranrückt. Ohne den Basisfall hören die Aufrufe nie auf und das Programm stürzt mit einem Stacküberlauf ab.

Q: Wie schreibt man in C eine Fakultätsfunktion?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Der Basisfall behandelt 0 und 1, und jeder rekursive Aufruf verringert n um eins, bis er ihn erreicht. Beachte, dass int bei 13! überläuft - nimm für größere Werte unsigned long long.

Q: Warum ist rekursives Fibonacci in C so langsam?

Weil fib(n) sowohl fib(n-1) als auch fib(n-2) aufruft, die dieselben Teilprobleme immer wieder neu berechnen - die Anzahl der Aufrufe wächst exponentiell, fib(50) würde also Jahre dauern. Es als Schleife zu schreiben, die die letzten zwei Werte behält, macht es linear und sofortig.

Q: Was verursacht einen Stacküberlauf bei Rekursion in C?

Jeder Aufruf nimmt einen Rahmen Stackspeicher für seine Parameter und lokalen Variablen, und der Stack ist nur ein paar Megabyte groß. Ein fehlender oder unerreichbarer Basisfall bedeutet unendliche Rekursion und einen sofortigen Absturz; selbst korrekte Rekursion, die Hunderttausende Ebenen tief geht, kann den Stack erschöpfen.

Eine Funktion, die sich selbst aufruft

Nichts hindert eine C-Funktion daran, sich selbst aufzurufen. Ihr eigener Name ist in ihrem Rumpf sichtbar, das hier ist also erlaubt:

void countdown(int n) {
    printf("%d\n", n);
    countdown(n - 1);      /* ruft sich selbst auf - hört aber nie auf! */
}

Es ist auch kaputt. Es gibt ewig aus, bis in negative Zahlen hinein, bis das Programm abstürzt. Was fehlt, ist ein Basisfall: eine Bedingung, unter der die Funktion zurückkehrt, ohne sich selbst aufzurufen.

#include <stdio.h>

void countdown(int n) {
    if (n <= 0) {              /* Basisfall: stoppen */
        printf("Start!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);          /* Rekursionsfall: ein kleineres Problem */
}

int main(void) {
    countdown(5);
    return 0;
}

Jede rekursive Funktion hat genau diese zwei Teile:

Einen Basisfall - die kleinste Eingabe, direkt beantwortet, ohne weiteren Aufruf.
Einen Rekursionsfall - löst das Problem mithilfe einer echt kleineren Fassung seiner selbst.

„Echt kleiner" ist der Teil, den man falsch macht. countdown(n - 1) rückt bei jedem Aufruf auf 0 zu. countdown(n) täte es nicht, und countdown(n / 2) auch nicht, wenn n für immer 1 sein könnte. Jeder Pfad muss das Problem schrumpfen lassen, sonst wird der Basisfall nie erreicht.

Fakultät

Das übliche erste Beispiel. n! ist n × (n-1) × ... × 1, und 0! ist als 1 definiert. Diese Definition ist bereits rekursiv: n! = n × (n-1)!.

#include <stdio.h>

unsigned long long factorial(int n) {
    if (n <= 1) {                       /* Basisfall: 0! und 1! sind beide 1 */
        return 1;
    }
    return n * factorial(n - 1);        /* Rekursionsfall */
}

int main(void) {
    for (int i = 0; i <= 10; i++) {
        printf("%2d! = %llu\n", i, factorial(i));
    }
    printf("20! = %llu\n", factorial(20));
    return 0;
}

Verfolge factorial(4), um zu sehen, wie die Antwort zusammengesetzt wird. Die Aufrufe gehen hinunter, und die Multiplikationen passieren auf dem Rückweg:

factorial(4)  -> 4 * factorial(3)
                      factorial(3) -> 3 * factorial(2)
                                           factorial(2) -> 2 * factorial(1)
                                                                factorial(1) -> 1   (Basisfall)
                                           factorial(2) = 2 * 1  = 2
                      factorial(3) = 3 * 2  = 6
factorial(4)  = 4 * 6  = 24

Es wird nichts multipliziert, bis der Basisfall zurückkehrt. Jeder ausstehende Aufruf wartet und hält sein eigenes n, und das ist der Punkt, den man verinnerlichen sollte: Diese wartenden Aufrufe belegen Speicher.

Beachte den Rückgabetyp. int läuft um 13! herum über und erzeugt stillschweigend eine falsche Zahl - C prüft nichts. unsigned long long bringt dich bis 20! und nicht weiter, denn 21! überschreitet 64 Bit. Die Rekursion ist hier nicht der begrenzende Faktor; der Typ ist es.

Der Basisfall benutzt bewusst n <= 1 statt n == 1: factorial(0) sollte 1 sein, und <= behandelt das. Mit n == 1 würde factorial(0) zu -1, -2 rekursieren und nie terminieren - eine gute Veranschaulichung dafür, wie ein „offensichtlich korrekter" Basisfall eine Eingabe verpassen kann.

Fibonacci, und warum die naive Fassung eine Falle ist

Fibonacci ist der andere Klassiker: Jede Zahl ist die Summe der beiden davor, beginnend bei 0 und 1. Die rekursive Definition schreibt sich von selbst.

#include <stdio.h>

long long calls = 0;

int fib(int n) {
    calls++;
    if (n < 2) {
        return n;                       /* fib(0) = 0, fib(1) = 1 */
    }
    return fib(n - 1) + fib(n - 2);
}

int main(void) {
    for (int n = 10; n <= 35; n += 5) {
        calls = 0;
        int result = fib(n);
        printf("fib(%2d) = %-8d (%lld Aufrufe)\n", n, result, calls);
    }
    return 0;
}

Sieh dir die Aufrufzahlen an. fib(10) braucht 177 Aufrufe; fib(35) braucht fast 30 Millionen. Jeder Schritt von 5 vervielfacht die Arbeit um etwa elf.

Der Grund ist im Aufrufbaum sichtbar. fib(5) ruft fib(4) und fib(3) auf; fib(4) ruft fib(3) erneut auf; und jeder davon berechnet fib(2) von Grund auf neu. Nichts wird gemerkt, dieselben Teilprobleme werden also immer wieder gelöst, und die Anzahl der Aufrufe wächst etwa wie 1,6ⁿ. fib(50) würde so tagelang laufen; fib(100) würde das Universum überdauern.

Die Schleifenfassung behält die letzten zwei Werte und ist linear:

#include <stdio.h>

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

int main(void) {
    for (int n = 10; n <= 90; n += 10) {
        printf("fib(%2d) = %lld\n", n, fibFast(n));
    }
    return 0;
}

fib(90) liefert sofort. Die Lehre ist nicht „Rekursion ist langsam" - sie ist, dass Rekursion mit überlappenden Teilproblemen langsam ist, sofern du dir die Antworten nicht merkst. Speichere Ergebnisse beim Berechnen in einem Array (Memoisierung), und die rekursive Fassung wird ebenfalls linear.

Der Aufrufstapel und der Stacküberlauf

Jeder Funktionsaufruf braucht irgendwo Platz für seine Parameter, seine lokalen Variablen und die Rücksprungadresse. Dieser Speicher ist ein Stackrahmen, der beim Aufruf abgelegt und beim Zurückkehren entfernt wird. Rekursion stapelt Rahmen übereinander - factorial(1000) hat tausend Rahmen gleichzeitig am Leben, jeder mit seinem eigenen n.

Der Stack ist nicht groß. Ein typischer Standardwert liegt bei 1 bis 8 MB, ein paar Zehntausend Rahmen sind also die realistische Grenze, und deutlich weniger, wenn jeder Rahmen ein großes lokales Array hält. Überschreite sie, und das Programm stirbt:

Segmentation fault (core dumped)

Das ist ein Stacküberlauf, und es gibt zwei Wege, einen zu bekommen:

Unendliche Rekursion - ein fehlender oder unerreichbarer Basisfall. Das ist ein Bug, und der Absturz kommt sofort:

int bad(int n) {
    return bad(n - 1);      /* kein Basisfall - stürzt im Bruchteil einer Sekunde ab */
}

Korrekt, aber zu tief - einmal pro Element über eine Liste mit einer Million Einträgen rekursieren. Die Logik stimmt; der Ansatz passt nicht in den Stack. Schreibe es als Schleife oder strukturiere so um, dass die Tiefe logarithmisch ist (auf Hälften zu rekursieren, wie es binäre Suche und Mergesort tun, ergibt bei einer Million Elementen eine Tiefe von etwa 20).

Manche Compiler können Endrekursion - bei der der rekursive Aufruf das Allerletzte ist, was die Funktion tut, ohne ausstehende Arbeit danach - in eine Schleife verwandeln und einen Rahmen wiederverwenden. countdown oben ist endrekursiv; factorial ist es nicht, weil die Multiplikation noch passieren muss, nachdem der Aufruf zurückgekehrt ist. Aber C verlangt diese Optimierung nicht, sie kann also je nach Compiler und Flags stattfinden oder nicht. Schreibe nie C, das nur funktioniert, weil der Optimierer einen Endaufruf beseitigt hat.

Wo Rekursion wirklich gewinnt

Jede rekursive Funktion lässt sich als Schleife schreiben, und beim schlichten Zählen ist die Schleife eindeutig besser. Rekursion verdient ihren Platz, wenn die Daten selbst rekursiv sind - wenn eine Struktur kleinere Kopien ihrer selbst enthält.

Die binäre Suche ist ein sauberes Beispiel: die Hälfte durchsuchen, dann deren Hälfte.

#include <stdio.h>

/* liefert den Index von target oder -1 */
int binarySearch(const int a[], int low, int high, int target) {
    if (low > high) {
        return -1;                          /* Basisfall: nichts mehr uebrig */
    }
    int mid = low + (high - low) / 2;       /* vermeidet Ueberlauf bei grossen Indizes */

    if (a[mid] == target) {
        return mid;                         /* Basisfall: gefunden */
    }
    if (a[mid] < target) {
        return binarySearch(a, mid + 1, high, target);
    }
    return binarySearch(a, low, mid - 1, target);
}

int main(void) {
    int sorted[] = {2, 5, 8, 12, 16, 23, 38, 56, 72, 91};
    int n = sizeof(sorted) / sizeof(sorted[0]);

    int targets[] = {23, 2, 91, 50};
    for (int i = 0; i < 4; i++) {
        printf("%2d -> Index %d\n", targets[i], binarySearch(sorted, 0, n - 1, targets[i]));
    }
    return 0;
}

Hier gibt es zwei Basisfälle, was normal ist: einen für den Erfolg und einen für das Erschöpfen. Die Tiefe liegt bei etwa log₂(n), selbst eine Milliarde Elemente brauchen also nur dreißig Rahmen.

Weitere Orte, an denen Rekursion natürlich passt: einen Baum oder eine verkettete Liste durchlaufen, Verzeichnisse durchwandern, verschachtelte Ausdrücke parsen und Teile-und-herrsche-Sortierverfahren wie Quicksort und Mergesort. Bei allen ist der rekursive Code kürzer und klarer als die Schleife mit einem ausdrücklichen Stapel, die ihn ersetzen würde.

Rekursion oder Schleife?

Nimm eine Schleife, wenn   das Problem linear ist - zählen, summieren, durchsuchen
Nimm Rekursion, wenn       die Daten verschachtelt sind - Bäume, verschachtelte Strukturen, teile und herrsche
Schreibe Rekursion um,     wenn die Tiefe unbegrenzt mit der Eingabegröße wachsen kann
Nimm nie Rekursion,        wenn Teilprobleme sich überlappen, außer du memoisierst

Zwei praktische Anmerkungen. Rekursive Aufrufe kosten etwas mehr als eine Schleifeniteration - ein Rahmen zum Ablegen und Entfernen jedes Mal -, für heiße, einfache Schleifen gewinnt die iterative Fassung also auch beim Tempo, nicht nur beim Speicher. Und das Debuggen ist anders: Eine Aufrufkette aus tiefer Rekursion sind Hunderte gleich aussehender Rahmen, gib also beim Eintritt den Parameter aus (wie es der calls-Zähler oben tut), wenn etwas nicht terminiert.

Eine rekursive Funktion schreiben: eine Checkliste

Finde zuerst den Basisfall. Was ist die kleinste Eingabe, und was ist ihre Antwort? Wenn du sie nicht benennen kannst, lässt sich die Funktion nicht schreiben.
Nimm an, dass der rekursive Aufruf funktioniert. Verfolge ihn nicht im Kopf durch - vertraue darauf, dass factorial(n - 1) den Wert (n-1)! liefert, und schreibe den einen Schritt, der daraus die Antwort macht.
Prüfe, dass jeder Pfad schrumpft. Jeder rekursive Aufruf muss für jede mögliche Eingabe näher an den Basisfall heranrücken, auch für 0 und negative Werte.
Prüfe die Tiefe. Wie viele Rahmen tief geht das auf echten Daten ungefähr? Tausende sind in Ordnung; Millionen nicht.
Prüfe auf Überlappung. Wenn dasselbe Teilproblem zweimal berechnet wird, brauchst du Memoisierung oder eine Schleife.

Häufig gestellte Fragen

Was ist Rekursion in C?

Eine Funktion, die sich selbst aufruft, um eine kleinere Fassung desselben Problems zu lösen. Jede rekursive Funktion braucht zwei Dinge: einen Basisfall, der ohne Rekursion zurückkehrt, und einen Rekursionsfall, der messbar näher an ihn heranrückt. Ohne den Basisfall hören die Aufrufe nie auf und das Programm stürzt mit einem Stacküberlauf ab.

Wie schreibt man in C eine Fakultätsfunktion?

int factorial(int n) { if (n <= 1) return 1; return n * factorial(n - 1); }. Der Basisfall behandelt 0 und 1, und jeder rekursive Aufruf verringert n um eins, bis er ihn erreicht. Beachte, dass int bei 13! überläuft - nimm für größere Werte unsigned long long.

Warum ist rekursives Fibonacci in C so langsam?

Weil fib(n) sowohl fib(n-1) als auch fib(n-2) aufruft, die dieselben Teilprobleme immer wieder neu berechnen - die Anzahl der Aufrufe wächst exponentiell, fib(50) würde also Jahre dauern. Es als Schleife zu schreiben, die die letzten zwei Werte behält, macht es linear und sofortig.

Was verursacht einen Stacküberlauf bei Rekursion in C?

Jeder Aufruf nimmt einen Rahmen Stackspeicher für seine Parameter und lokalen Variablen, und der Stack ist nur ein paar Megabyte groß. Ein fehlender oder unerreichbarer Basisfall bedeutet unendliche Rekursion und einen sofortigen Absturz; selbst korrekte Rekursion, die Hunderttausende Ebenen tief geht, kann den Stack erschöpfen.

Verwandte Konzepte