Wprowadzenie do rekurencji

Rekurencja to technika programowania, w której funkcja wywołuje samą siebie, aby rozwiązać problem. Zamiast używać pętli, funkcje rekurencyjne dzielą złożone problemy na mniejsze, podobne podproblemy, aż dotrą do prostego przypadku, który można rozwiązać bezpośrednio.

Każda funkcja rekurencyjna musi mieć dwa niezbędne elementy. Przypadek bazowy to warunek, który zatrzymuje rekurencję - bez niego funkcja wywoływałaby samą siebie w nieskończoność. Krok rekurencyjny to miejsce, w którym funkcja wywołuje samą siebie ze zmodyfikowanymi parametrami, przybliżając się do przypadku bazowego przy każdym wywołaniu.

Oto prosty przykład odliczania, który demonstruje rekurencję:

void countdown(int n) {
    if (n <= 0) {           // Przypadek bazowy: zakończ, gdy n osiągnie 0
        std::cout << "Done!" << std::endl;
        return;
    }
    
    std::cout << n << std::endl;
    countdown(n - 1);       // Krok rekurencyjny: wywołaj z n-1
}

Gdy wywołasz countdown(3), wypisze 3, a następnie wywoła countdown(2), które wypisze 2, po czym wywoła countdown(1) i tak dalej, aż osiągnie przypadek bazowy. Każde wywołanie funkcji czeka na zakończenie kolejnego wywołania, zanim samo się zakończy, tworząc łańcuch wywołań, który ostatecznie rozwija się z powrotem do pierwotnego wywołującego.