Antwort.

Geschichte der Frage:

Rekursion wird in C seit seiner Entstehung unterstützt – sie fügt sich natürlich in die Paradigmen der Sprache ein und ermöglicht kompakte Lösungen, insbesondere bei Aufgaben, die mit Bäumen, Listen und komplexen Zerlegungsalgorithmen arbeiten.

Problem:

Die Hauptgefahren beim Einsatz von Rekursion sind übermäßiger Speicherverbrauch des Stacks, die Möglichkeit eines Stack-Überlaufs (stack overflow) sowie unerwartete Auswirkungen auf die Leistung (im Vergleich zu einer zyklischen Implementierung). In C gibt es keinen standardisierten Weg, um automatisch die Tiefe der Aufrufverschachtelung zu kontrollieren.

Lösung:

Vor dem Einsatz von Rekursion sollte die maximal mögliche Verschachtelungstiefe eingeschätzt werden, die Verwendung von Tail-Rekursion sollte in Betracht gezogen werden (zur Optimierung durch den Compiler) und es sollte ein Schutz gegen Überlauf eingeführt werden, zum Beispiel ein expliziter Zähler für die Rekursionstiefe. Eine alternative Methode besteht darin, rekursive Aufrufe durch zyklische zu ersetzen, wenn dies möglich ist.

Beispielcode:

#include <stdio.h>
#define MAX_DEPTH 1000

int factorial(int n, int depth) {
    if (depth > MAX_DEPTH) {
        printf("Error: maximale Rekursionstiefe überschritten!\n");
        return -1;
    }
    if (n == 0) return 1;
    return n * factorial(n - 1, depth + 1);
}

int main() {
    printf("%d\n", factorial(5, 0)); // 120
    return 0;
}

Wesentliche Merkmale:

Keine Garantie für eine automatische Begrenzung der Rekursionstiefe
Rekursion verbraucht Stapelspeicher, der begrenzt sein kann
Tail-Rekursion kann vom Compiler optimiert werden, aber nicht immer

Trickfragen.

Wird der Stack freigegeben, wenn man innerhalb einer rekursiven Funktion ein return vor dem Abschluss aller Aufrufe ausführt?

Ja, der Stack wird beim Verlassen der aktuellen Funktion freigegeben. Es bleiben keine „hängenden“ Daten im Stack, sofern kein Stack-Überlauf aufgetreten ist.

Kann man innerhalb des Körpers einer rekursiven Funktion statische lokale Variablen deklarieren und wie werden sie sich verhalten?

Ja, solche Variablen werden für alle rekursiven Aufrufe gemeinsam sein, ihr Wert bleibt zwischen den Aufrufen erhalten, was häufig zu Fehlern führt, wenn dieses Verhalten nicht berücksichtigt wird.

Beeinflusst der C-Compiler die Rekursionstiefe und kann er sie begrenzen?

Der Compiler begrenzt die Rekursion nicht direkt. Die Rekursionstiefe ist durch die Größe des Stacks des Betriebssystems oder durch äußere Faktoren begrenzt.

Typische Fehler und Anti-Muster

Unbegrenzte Rekursion ohne Überprüfung der Tiefe
Uninitialisierte oder statische lokale Variablen im Körper der rekursiven Funktion
Verwendung von Rekursion, wo eine Schleife einfacher und effizienter ist

Beispiel aus dem wirklichen Leben

Ein rekursiver Durchlauf eines Suchbaums wurde ohne Tiefenbegrenzung implementiert:

Vorteile:

Der Code ist prägnant und gut lesbar

Nachteile:

Bei großer Baumtiefe stürzte das Programm mit einem Stack-Überlauf-Fehler ab.

In der verbesserten Version wurde ein Tiefenzähler eingeführt und bei großen Baumgrößen auf einen stackbasierten Durchlauf umgeschaltet: