Baza wiedzyCentrum egzaminacyjne
PLPolski
Wybierz język13

CKTIS / C++

Rekurencja

Rekurencja polega na wywoływaniu funkcji przez nią samą, bezpośrednio lub przez inne funkcje. Aby obliczenie się zakończyło, potrzebuje osiągalnego przypadku bazowego i kroków prowadzących do niego.

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

Składnia

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

Rekurencja (recursion) to technika, w której funkcja wywołuje samą siebie bezpośrednio albo pośrednio przez inne funkcje. Nie wymaga specjalnego słowa kluczowego: używa zwykłej składni wywołania funkcji. C++ dopuszcza wywołania rekurencyjne, ale nie wolno rekurencyjnie wywoływać main.

Typowy algorytm ma przypadek bazowy, który zwraca wynik bez kolejnego wywołania, oraz krok rekurencyjny, który zmniejsza problem. Dla danych, które mają zakończyć obliczenie, każdy łańcuch wywołań musi dotrzeć do przypadku bazowego. Sam warunek zakończenia nie wystarcza, jeśli argumenty nigdy go nie spełnią.

W przykładzie sum_to(5) oblicza sumę od 1 do 5. Wywołania zmniejszają n aż do 0, a następnie kolejne powroty dodają oczekujące wartości, dając 15. Każde wywołanie ma własny parametr n; nie jest to jedna wspólna zmienna. Dla n <= 0 funkcja zwraca 0.

Nie traktuj przykładu jako rozwiązania dla dowolnie dużych danych: głęboka rekurencja może wyczerpać zasoby wykonania, a suma przekraczająca zakres int powoduje niezdefiniowane zachowanie. Dla dużych danych rozważ pętlę i kontrolę zakresu. Wskazane źródło jest rozwijanym szkicem standardu, a nie zamrożoną publikacją C++23; przykład używa składni zgodnej z C++23.

Przykłady

#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';
}

Wynik

15

Wyświetlony kod i zadeklarowany wynik zweryfikowano w odizolowanym środowisku metodą zapisaną w dowodzie weryfikacji tej dokładnej wersji.

Źródła