WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

CKTIS / C++

Rekursion

Bei der Rekursion ruft eine Funktion sich selbst auf, direkt oder über andere Funktionen. Damit die Berechnung endet, braucht sie einen erreichbaren Basisfall und rekursive Schritte, die sich diesem Fall annähern.

Version: C++23; repository compiler flag, production runtime not attested

Syntax

ReturnType function(Parameters) {
    if (base_condition) return base_value;
    return combine(function(smaller_arguments));
}

Rekursion (recursion) ist eine Technik, bei der eine Funktion sich direkt oder indirekt über andere Funktionen selbst aufruft. Dafür ist kein besonderes Schlüsselwort nötig: Es wird die gewöhnliche Syntax für Funktionsaufrufe verwendet. C++ erlaubt rekursive Aufrufe, aber main darf nicht rekursiv aufgerufen werden.

Ein typischer Algorithmus hat einen Basisfall, der ein Ergebnis ohne einen weiteren Aufruf zurückgibt, und einen Rekursionsschritt, der das Problem verkleinert. Bei Eingaben, für die die Berechnung enden soll, muss jede Aufrufkette einen Basisfall erreichen. Eine Abbruchbedingung allein reicht nicht aus, wenn die Argumente sie nie erfüllen.

Im Beispiel berechnet sum_to(5) die Summe von 1 bis einschließlich 5. Die Aufrufe verringern n, bis es 0 erreicht; bei den anschließenden Rückgaben werden die ausstehenden Werte addiert, sodass 15 entsteht. Jeder Aufruf hat einen eigenen Parameter n; es handelt sich nicht um eine gemeinsame Variable. Für n <= 0 gibt die Funktion 0 zurück.

Betrachte das Beispiel nicht als Lösung für beliebig große Eingaben: Tiefe Rekursion kann Ausführungsressourcen erschöpfen, und eine Summe außerhalb des Wertebereichs von int führt zu undefiniertem Verhalten. Bei großen Eingaben solltest du eine Schleife und Bereichsprüfungen in Betracht ziehen. Die angegebene Quelle ist ein fortlaufend weiterentwickelter Standardentwurf und keine unveränderliche C++23-Veröffentlichung; das Beispiel verwendet mit C++23 kompatible Syntax.

Beispiele

#include <iostream>

int sum_to(int n) {
    if (n <= 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main() {
    std::cout << sum_to(5) << '\n';
}

Ergebnis

15

Der angezeigte Code und das angegebene Ergebnis wurden in einer isolierten Umgebung mit der im Prüfnachweis für genau diese Version dokumentierten Methode verifiziert.

Quellen