Rekurencja vs pętla: kryteria wyboru

1. Jedno zadanie — dwie formy zapisu

Kiedy widzisz rekurencję po raz pierwszy, mózg często reaguje tak: „O, to magia”. Kiedy widzisz długą pętlę z masą zmiennych, reakcja jest inna: „O, to magia, ale zła”. W rzeczywistości obie formy to po prostu różne sposoby zapisania tego samego procesu: powtarzania kroków, aż osiągniemy warunek zatrzymania. W tym wykładzie nauczymy się wybierać formę nie według zasady „mi się tak podoba”, lecz według zasady „dla mnie to jest czytelniejsze i trudniej to zepsuć”.

Zacznijmy od uczciwego tezy: wiele zadań da się rozwiązać zarówno rekurencją, jak i pętlą. Ale kod czytają ludzie (a kompilator przynajmniej nie ocenia cię po wcięciach). Dlatego wybór formy to kwestia czytelności, przewidywalności i liczby typowych błędów.

Aby nie odpłynąć w filozofię, trzymajmy w głowie prostą wskazówkę: jeśli w wersji rekurencyjnej łatwo wyjaśnisz „co się stanie na kroku” i „jak dążymy do bazy”, to rekurencja może być dobrym kandydatem. Jeśli natomiast ciągle sprawdzasz wzrokiem, czy to nie skończy się nieskończonością, to być może pętla da bardziej przejrzysty obraz.

Mapa odpowiedności: rekurencja ↔ pętla

Gdy przepisyujesz rekurencję na pętlę (albo odwrotnie), bardzo pomaga nie pisać wszystkiego od zera, lecz dopasować części konstrukcji. To jak tłumaczenie z jednego języka na drugi: jeśli zapomniałeś słowa „stół”, możesz opisać „to, na czym stoi kubek”, ale lepiej po prostu znać słowo.

Poniżej — wygodna tabela odpowiedności. Warto ją mieć jako ściągę, ale nie jako dogmat.

Najczęstszy błąd początkującego to myśleć, że rekurencja „jakoś się optymalizuje sama” albo „sama się zatrzyma”. Nie. Rekurencja zatrzymuje się tylko dlatego, że napisałeś warunek, przy którym wywołań już nie będzie. Pętla zatrzymuje się też tylko dlatego, że napisałeś warunek i aktualizujesz zmienne tak, by warunek stał się fałszywy. Magii nie ma. Jest tylko ty i twoja zdolność, by nie zgubić -1 po drodze.

2. Przykład nr 1: silnia — dwie wersje, jedno znaczenie

Silnia to prawie oficjalny talizman rekurencji. Często pokazuje się ją pierwszą, bo wzór sam w sobie jest rekurencyjny: n! = n * (n-1)!. Ale istotne jest coś innego: silnia świetnie pokazuje, że rekurencja i pętla są tu równie naturalne — wybierać można według czytelności.

Wersja rekurencyjna

Teraz piszemy tak, by było maksymalnie jasne, gdzie jest baza i gdzie krok.

#include <iostream>

long long factorial_rec(int n) {
    if (n == 0) return 1;              // przypadek bazowy
    return n * factorial_rec(n - 1);   // krok rekurencyjny
}

Jeśli czytasz to na głos, brzmi logicznie: „jeśli zero — zwróć 1, w przeciwnym razie zwróć n pomnożone przez silnię n-1”. To rzadki przypadek, gdy matematyka i kod patrzą na siebie bez wzajemnej niechęci.

Wersja z pętlą

A teraz ta sama logika, tylko bez „nurkującego” stosu.

#include <iostream>

long long factorial_loop(int n) {
    long long result = 1;              // element neutralny mnożenia
    for (int i = 2; i <= n; ++i) {
        result *= i;
    }
    return result;
}

Dla początkującego pętla może być nawet bardziej zrozumiała: widać, że zmienna result akumuluje wynik, a i idzie od 2 do n. Żadnego „po powrocie dopiszemy” — wszystko dzieje się tutaj, w jednej płaszczyźnie rzeczywistości.

3. Przykład nr 2: wypisanie łańcucha w odwrotnej kolejności

Zadanie: wypisać łańcuch znaków odwrotnie. Tak, można zrobić pętlę indeksową idącą w tył. Ale rekurencja daje bardzo czystą ideę: „najpierw dojść do końca, potem wypisywać”.

Kluczowy moment czytelności: robimy przed wywołaniem i przy powrocie

Tu rekurencja zaczyna pokazywać swoją supermoc (i jednocześnie pułapkę). W funkcji rekurencyjnej możesz umieścić działanie albo przed wywołaniem rekurencyjnym, albo po nim. W pętli też można, ale tam porządek jest zwykle bardziej oczywisty: idziesz naprzód w czasie w każdym kroku.

Problem polega na tym, że „po wywołaniu rekurencyjnym” oznacza: „zrobimy to, gdy zaczniemy wracać po stosie”. Czyli kolejność wykonania staje się odwrotna.

To najlepiej widać na łańcuchach.

Rekurencja: wypisujemy „przy powrocie”

#include <iostream>
#include <string>

void print_reverse_rec(const std::string& s, std::size_t i) {
    if (i == s.size()) return;     // baza: doszlismy do konca
    print_reverse_rec(s, i + 1);   // idziemy glebiej
    std::cout << s[i];             // drukujemy przy powrocie
}

Jeśli uruchomisz to tak:

int main() {
    print_reverse_rec("abcd", 0);
    std::cout << '\n';             // dcba
}

otrzymasz dcba. I to nie „magia rekurencji”, to po prostu kolejność: najpierw doszliśmy do i == size, a potem zaczęliśmy wracać: i = size-1, i = size-2 i tak dalej.

Pętla: wypisujemy indeksem wstecz

#include <iostream>
#include <string>

void print_reverse_loop(const std::string& s) {
    for (std::size_t i = s.size(); i > 0; --i) {
        std::cout << s[i - 1];
    }
}

I wywołanie:

int main() {
    print_reverse_loop("abcd");
    std::cout << '\n';             // dcba
}

Pętla tutaj też świetnie się nadaje, tylko trzeba uważnie pisać granice: i > 0 i indeks i - 1. W przeciwnym razie można złapać znany problem ze size_t: to typ bez znaku i „poniżej zera” nie potrafi zejść — zamieni się w ogromną liczbę i będzie udawać, że tak było zaplanowane.

Przepisanie rekurencji na pętlę: „zbieramy wynik od razu” i „zbieramy wynik później”

Teraz będzie myśl, którą warto sobie powiedzieć na głos: nie każda rekurencja jest równie łatwa do bezpośredniego przepisania na pętlę „jak jest”. Przykład silni i sumy zwykle przepisuje się łatwo, bo wynik można kumulować w zmiennej.

Ale jeśli w rekurencji główny efekt/działanie zachodzi „przy powrocie”, to przy tłumaczeniu na pętlę często trzeba iść w odwrotnym kierunku albo najpierw dojść do końca, a potem przetwarzać wynik w odwrotnej kolejności.

Dla łańcucha to proste: możesz iterować indeksem wstecz. Dla bardziej złożonych zadań (np. przeszukiwanie „w głąb”) zrobi się ciekawiej, ale tego dziś nie poruszamy — ważna jest zasada kolejności wykonania.

Aby to utrwalić, spójrzmy na sumę od 1 do n: tam działanie zwykle jest „przed wywołaniem” (w sensie), ale zapis wygląda jak „po” ze względu na wyrażenie n + sum_to(n - 1).

4. Przykład nr 3: suma 1..n — rekurencja i pętla

Rekurencja

#include <iostream>

int sum_to_rec(int n) {
    if (n == 0) return 0;          // baza: element neutralny sumy
    return n + sum_to_rec(n - 1);
}

Pętla

#include <iostream>

int sum_to_loop(int n) {
    int sum = 0;                   // ten sam sens, co baza w rekurencji
    for (int i = 1; i <= n; ++i) {
        sum += i;
    }
    return sum;
}

W obu wypadkach kluczowa myśl to element neutralny: dla sumy to 0, dla mnożenia to 1. Jeśli pomylisz to, kod się skompiluje i nawet zadziała, ale będzie dawał „kreatywny” wynik. Czasem kompilator też chce być artystą, ale zwykle mu nie wychodzi.

5. Kryteria wyboru: jak zdecydować, co napisać — rekurencję czy pętlę

Chciałoby się podać „uniwersalną regułę”, ale uczciwiej będzie przyznać: uniwersalnej reguły nie ma. Są za to praktyczne kryteria, które niemal zawsze pomagają początkującemu dokonać dobrego wyboru.

Pierwszy kryterium — przejrzystość zatrzymania. W pętli zazwyczaj widzisz warunek zatrzymania w nagłówku for/while. W rekurencji zatrzymanie ukryte jest w przypadku bazowym, i jeśli go nie zauważysz lub nie jest osiągalny, funkcja będzie wywoływać siebie, aż program fizycznie padnie. Dlatego gdy piszesz rekurencję, przypadek bazowy powinien rzucać się w oczy jak czerwony znak „STOP”.

Drugi kryterium — kolejność działań. Jeśli naturalnie myślisz „najpierw zagłębiamy się, potem robimy akcję przy powrocie”, rekurencja często jest czytelniejsza. Przykład z łańcuchem jest właśnie taki. Jeśli jednak łatwiej myślisz „w każdym kroku pętli robię kawałek pracy”, pętla zazwyczaj jest czytelniejsza, szczególnie gdy jest zmienna akumulująca.

Trzeci kryterium — liczba ruchomych części. Czasem wersja rekurencyjna wygląda krótko i „matematycznie”, a wersja z pętlą obrośnie indeksami, granicami, sprawdzeniami i zacznie przypominać tamagotchi, którego nie można zostawić samego. Czasem odwrotnie: rekurencja wymaga przekazywania kilku parametrów, starannej bazy i uważnego zrozumienia, gdzie „przed”, a gdzie „po”, a pętla wygląda jak uczciwe 6 linii. Wybierz to, gdzie jest mniejsze ryzyko pomyłki właśnie dla ciebie, na twoim aktualnym poziomie.

Czwarty kryterium — lokalność zrozumienia. Pętla zazwyczaj czyta się „z góry na dół” jako jeden przepływ. Rekurencja wymaga mentalnego „rozwinięcia” wywołań, czyli musisz umieć wyobrazić sobie kilka poziomów. To umiejętność, którą się rozwija, ale na początku jest kosztowna. Dlatego na starcie warto częściej wybierać pętle, jeśli rekurencja nie daje wyraźnej korzyści w czytelności.

Aby to utrwalić nie tylko słowami, sformułujmy „ściągę wyboru” w małej tabeli. Nie chodzi tu o szybkość i pamięć (to osobny wykład), lecz o czytelność i ryzyko błędów.

6. Komenda reverse w naszej aplikacji konsolowej

Aby nie przeradzać wykładu w zbiór oddzielnych „zabawek”, kontynuujmy pomysł prostego programu konsolowego, który przyjmuje komendy i wykonuje małe operacje na łańcuchach. Nie budujemy pełnego produktu (jeszcze za wcześnie), ale ćwiczymy główną umiejętność: pisać małe funkcje i podłączać je w main.

Załóżmy, że mamy tryb: użytkownik wpisuje komendę, potem łańcuch, a program wypisuje wynik. Dodajmy komendę reverse i pozwólmy użytkownikowi wybrać implementację (czysto edukacyjny przełącznik).

Oto szkielet handlera komendy:

#include <iostream>
#include <string>

void run_reverse_command() {
    std::string s;
    std::getline(std::cin, s);

    // Na razie tylko wypisujemy, później można rozbudować.
    // Implementację wybierzemy poniżej.
}

Teraz dodajmy dwie funkcje wypisujące (już je widzieliśmy, ale złożymy obok, żeby łatwiej je podłączyć).

#include <iostream>
#include <string>

void print_reverse_rec(const std::string& s, std::size_t i) {
    if (i == s.size()) return;
    print_reverse_rec(s, i + 1);
    std::cout << s[i];
}

I wersję z pętlą:

#include <iostream>
#include <string>

void print_reverse_loop(const std::string& s) {
    for (std::size_t i = s.size(); i > 0; --i) {
        std::cout << s[i - 1];
    }
}

Teraz wewnątrz komendy można tymczasowo „przełączać” implementację, żeby porównać czytelność:

#include <iostream>
#include <string>

void run_reverse_command() {
    std::string s;
    std::getline(std::cin, s);

    const bool use_recursion = true; // edukacyjny flaga

    if (use_recursion) {
        print_reverse_rec(s, 0);
    } else {
        print_reverse_loop(s);
    }

    std::cout << '\n';
}

Zauważ, że nie mieszamy całej logiki w jednej funkcji. W prawdziwym kodzie to oszczędza nerwy: main pozostaje „dyrygentem”, a nie „orkiestrą grającą sama na sobie”.

Mini-schemat: co się dzieje przy rekurencyjnym wypisywaniu odwrotnie

Czasami warto dosłownie zobaczyć porządek: najpierw zagłębienie, potem powrót. To nie jest konieczne do rozwiązania, ale bardzo przydatne jako „wewnętrzny debugger w głowie”.

flowchart TD
    A["print_reverse_rec(i=0)"] --> B["print_reverse_rec(i=1)"]
    B --> C["print_reverse_rec(i=2)"]
    C --> D["print_reverse_rec(i=3)"]
    D --> E["i==size -> return"]
    E --> D2["drukuj s[2]"]
    D2 --> C2["drukuj s[1]"]
    C2 --> B2["drukuj s[0]"]

Ten obrazek dokładnie pokazuje to, o czym mówiliśmy: akcja jest po wywołaniu rekurencyjnym, więc wykonuje się przy powrocie.

7. Typowe błędy

Błąd nr 1: pomylenie „co odpowiada bazie” i złe zainicjalizowanie akumulatora.
W rekurencji zwracasz poprawną wartość w przypadku bazowym (0 dla sumy, 1 dla iloczynu). W pętli to zamienia się w wartość początkową zmiennej-akumulatora. Jeśli z przyzwyczajenia ustawisz 0 wszędzie, silnia zawsze będzie równa zero i uzyskasz idealny model „jak szybko zniszczyć matematykę”.

Błąd nr 2: utrata kolejności działań przy przepisaniu rekurencji na pętlę.
Jeśli w rekurencji działanie wykonywało się przy powrocie (po wywołaniu rekurencyjnym), to prosty „do przodu” w pętli może dać inną kolejność. Dla łańcucha to szczególnie widoczne: zamiast dcba otrzymasz abcd. W takich przypadkach albo wykonaj przejście w odwrotną stronę, albo szczerze zostaw rekurencję, jeśli rzeczywiście jest czytelniejsza.

Błąd nr 3: błędne granice w pętli (off-by-one) po przepisaniu.
Rekurencyjny warunek if (i == s.size()) return jest bardzo konkretny: doszliśmy do końca — stop. Przy przepisywaniu łatwo napisać i <= s.size() i przypadkowo sięgnąć do s[s.size()], co jest już wyjściem poza granice. Lekarstwo proste i nudne: starannie dopasowuj przypadek bazowy i granice pętli, zwłaszcza < i <=.

Błąd nr 4: pętla wsteczna po std::size_t z „zejściem poniżej zera”.
Wzorzec for (std::size_t i = s.size() - 1; i >= 0; --i) wygląda logicznie tylko dla człowieka. Kompilator zaś wie, że size_t nie może być ujemny i warunek i >= 0 jest praktycznie zawsze prawdziwy. W rezultacie pętla staje się nieskończona (albo prawie nieskończona) i wypisujesz śmieci. Bezpieczna forma to for (std::size_t i = s.size(); i > 0; --i) i drukowanie s[i - 1].

Błąd nr 5: wybierać „rekurencję czy pętlę” ze względu na długość kodu, a nie jasność.
Czasem rekurencja w 3 linijkach wygląda ładnie, ale sam po tygodniu nie będziesz wiedział, gdzie tam baza i dlaczego to nie pada. Czasem pętla w 7 liniach jest dłuższa, ale bardziej czytelna. Cel nie jest „wygrać konkurs na zwięzłość”, tylko napisać kod, który można utrzymać bez wróżenia z fusów.