Einführung in die Rekursion

Teil des Abschnitts Logik & Ablauf der C++-Journey von Coddy — Lektion 45 von 56.

Rekursion ist eine Programmiertechnik, bei der eine Funktion sich selbst aufruft, um ein Problem zu lösen. Anstatt Schleifen zu verwenden, zerlegen rekursive Funktionen komplexe Probleme in kleinere, ähnliche Teilprobleme, bis sie einen einfachen Fall erreichen, der direkt gelöst werden kann.

Jede rekursive Funktion muss zwei wesentliche Komponenten haben. Der Basisfall ist eine Bedingung, die die Rekursion stoppt – ohne ihn würde sich die Funktion ewig selbst aufrufen. Der Rekursionsschritt ist der Teil, in dem die Funktion sich selbst mit geänderten Parametern aufruft und sich mit jedem Aufruf dem Basisfall nähert.

Hier ist ein einfaches Countdown-Beispiel, das Rekursion demonstriert:

void countdown(int n) {
    if (n <= 0) {           // Basisfall: Stoppen, wenn n 0 erreicht
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Rekursiver Schritt: Aufruf mit n-1
}

Wenn Sie countdown(3) aufrufen, wird 3 ausgegeben, dann countdown(2) aufgerufen, was 2 ausgibt, dann countdown(1) aufgerufen und so weiter, bis der Basisfall erreicht ist. Jeder Funktionsaufruf wartet auf den Abschluss des nächsten, bevor er beendet wird, wodurch eine Kette von Aufrufen entsteht, die schließlich zum ursprünglichen Aufrufer zurückgeführt wird.

Spickzettel

Rekursion bedeutet, dass eine Funktion sich selbst aufruft, um ein Problem zu lösen, indem sie es in kleinere Teilprobleme zerlegt.

Jede rekursive Funktion benötigt:

Basisfall: Bedingung, die die Rekursion stoppt
Rekursionsschritt: Die Funktion ruft sich selbst mit geänderten Parametern auf

Beispiel für eine Countdown-Funktion:

void countdown(int n) {
    if (n <= 0) {           // Basisfall
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Rekursionsschritt
}

Probier es selbst

Diese Lektion enthält keine Programmieraufgabe.