C Academy · Lekcja

Rekurencja a iteracja

Dowiedzą się Państwo, kiedy wybrać każdą z nich.

Rekurencja a iteracja to bezpłatna lekcja C Academy na CoddyKit. To lekcja 3 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej C Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs C Academy zawiera 4 lekcji w sumie.

Dwa sposoby powtarzania

Wiele problemów można rozwiązać zarówno za pomocą rekurencji, jak i iteracji. Iteracja korzysta z pętli, a rekurencja z wywołań funkcji.

Oba podejścia mogą dać ten sam wynik, ale różnią się stylem, zużyciem pamięci i szybkością.

Silnia za pomocą pętli

Oto silnia zapisana iteracyjnie za pomocą pętli for. Funkcja nie wywołuje samej siebie; pojedyncza zmienna przechowuje narastający iloczyn.

#include <stdio.h>

long factorial(int n) {
    long result = 1;
    for (int i = 2; i <= n; i++)
        result *= i;
    return result;
}

int main(void) {
    printf("%ld\n", factorial(6));
    return 0;
}

Silnia za pomocą rekurencji

Wersja rekurencyjna jest krótsza i bezpośrednio odzwierciedla definicję matematyczną.

Obie wersje wypisują 720 dla factorial(6), ale korzystają z innego mechanizmu.

long factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

Różnice w zużyciu pamięci

Iteracja zwykle wykorzystuje stałą, niewielką ilość pamięci: zaledwie kilka zmiennych lokalnych.

Rekurencja dodaje ramkę stosu przy każdym wywołaniu, dlatego głęboka rekurencja zużywa więcej pamięci i może wyczerpać miejsce na stosie.

Różnice w szybkości

Każde wywołanie rekurencyjne wiąże się z niewielkim kosztem: utworzeniem ramki i powrotem z niej.

W przypadku prostych zadań polegających na zliczaniu pętle są często nieco szybsze, ponieważ unikają tego narzutu wywołania.

Kiedy rekurencja wygrywa

Rekurencja sprawdza się szczególnie dobrze, gdy problem ma naturalnie rekurencyjną strukturę, na przykład w przypadku drzew, struktur zagnieżdżonych lub algorytmów dziel i zwyciężaj.

W takich sytuacjach kod rekurencyjny jest krótszy i czytelniejszy niż równoważna pętla z ręcznie zarządzanym stosem.

Kiedy iteracja wygrywa

W przypadku prostego, liniowego powtarzania, takiego jak sumowanie tablicy lub zliczanie, pętla jest prostsza i wykorzystuje stałą ilość pamięci.

Eliminuje również ryzyko przepełnienia stosu dla dużych danych wejściowych.

int sum_array(int a[], int n) {
    int total = 0;
    for (int i = 0; i < n; i++)
        total += a[i];
    return total;
}

To samo zadanie w obu stylach

Sumowanie liczb od 1 do n można wykonać na oba sposoby. Oto wersja iteracyjna zwracająca taki sam wynik jak rekurencja.

#include <stdio.h>

int sum_to(int n) {
    int total = 0;
    for (int i = 1; i <= n; i++)
        total += i;
    return total;
}

int main(void) {
    printf("%d\n", sum_to(100));
    return 0;
}

Zamiana rekurencji na pętlę

Każdą rekurencję można przepisać iteracyjnie, czasami korzystając z własnego, jawnego stosu.

Prostą rekurencję liniową, taką jak obliczanie silni lub sumy, można zamienić na zwykłą pętlę ze zmienną akumulującą wynik.

#include <stdio.h>

int main(void) {
    int n = 5, result = 1;
    while (n > 1) { result *= n; n--; }
    printf("%d\n", result);
    return 0;
}

Uwaga dotycząca rekurencji ogonowej

Wywołanie rekurencyjne ogonowo jest ostatnią operacją w funkcji. Niektóre kompilatory optymalizują je do postaci pętli, ponownie wykorzystując jedną ramkę.

Język C tego nie gwarantuje, dlatego nie należy polegać na tym w przypadku głębokiej rekurencji.

int sum_tail(int n, int acc) {
    if (n == 0) return acc;
    return sum_tail(n - 1, acc + n);
}

Wybór podejścia

Proszę zadać sobie pytanie: czy problem ma naturalnie zagnieżdżoną strukturę lub charakter dziel i zwyciężaj? W takim przypadku odpowiednia będzie rekurencja.

Czy chodzi o proste, liniowe powtarzanie przy potencjalnie bardzo dużych danych wejściowych? Wtedy iteracja jest bezpieczniejsza i często szybsza.

Szybkie sprawdzenie

Proszę porównać oba podejścia.

Podsumowanie

Rekurencja i iteracja mogą rozwiązywać te same problemy. Pętle wykorzystują stałą ilość pamięci i świetnie nadają się do zadań liniowych; rekurencja jest czytelniejsza w przypadku problemów zagnieżdżonych oraz typu dziel i zwyciężaj, ale każdemu wywołaniu przypisuje ramkę stosu.

Często zadawane pytania

Czy lekcja „Rekurencja a iteracja” jest bezpłatna?

Tak — pełny tekst „Rekurencja a iteracja” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu C Academy, przejdź na CoddyKit PRO. Kurs C Academy zawiera 4 lekcji w sumie.

Co nauczysz się w „Rekurencja a iteracja”?

Dowiedzą się Państwo, kiedy wybrać każdą z nich. Ćwiczysz C Academy z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.

Czy potrzebuję doświadczenia, aby zacząć C Academy?

Nie wymagamy żadnego doświadczenia. C Academy w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 3 z 4.

Ile czasu zajmuje lekcja „Rekurencja a iteracja”?

Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.

Czy mogę pisać i uruchamiać kod w tej lekcji C Academy?

Tak. Każda lekcja C Academy zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.

Wszystkie lekcje w tym kursie

← Powrót do C Academy