C Academy · Lekcja

Jak działa rekurencja

Przypadki bazowe i stos wywołań.

Jak działa rekurencja to bezpłatna lekcja C Academy na CoddyKit. To lekcja 1 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.

Czym jest rekurencja?

Rekurencja ma miejsce wtedy, gdy funkcja wywołuje samą siebie, aby rozwiązać problem. Każde wywołanie pracuje na mniejszej części pierwotnego problemu.

W języku C każda funkcja może wywoływać samą siebie, o ile istnieje sposób, aby wywołania w końcu się zatrzymały.

Przypadek bazowy

Każda funkcja rekurencyjna potrzebuje przypadku bazowego, czyli warunku, po którego spełnieniu przestaje wywoływać samą siebie i bezpośrednio zwraca wynik.

Bez przypadku bazowego funkcja wywoływałaby się bez końca i doprowadziłaby do awarii programu.

int countdown(int n) {
    if (n == 0) return 0; /* base case */
    return countdown(n - 1);
}

Przypadek rekurencyjny

Przypadek rekurencyjny to część, w której funkcja wywołuje samą siebie ze zmienionym argumentem.

Ten argument musi przybliżać wywołanie do przypadku bazowego, w przeciwnym razie rekurencja nigdy się nie zakończy.

int sum_to(int n) {
    if (n == 0) return 0;       /* base case */
    return n + sum_to(n - 1);   /* recursive case */
}

Pierwszy kompletny program

Uruchommy kompletny program, który za pomocą rekurencji sumuje liczby od 1 do 5.

Wynik powinien wynosić 15.

#include <stdio.h>

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

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

Śledzenie wywołań

Warto prześledzić rekurencję ręcznie. Dla sum_to(3):

sum_to(3) = 3 + sum_to(2)
sum_to(2) = 2 + sum_to(1)
sum_to(1) = 1 + sum_to(0)
sum_to(0) = 0

Następnie wywołania zwracają wyniki w górę: najpierw 1, potem 3, a na końcu 6.

Stos wywołań

Każde wywołanie funkcji otrzymuje własne miejsce na stosie wywołań, w którym przechowywane są jego parametry i zmienne lokalne.

Podczas schodzenia coraz głębiej kolejne ramki są odkładane na stos. Gdy wywołanie zwraca wynik, jego ramka jest usuwana, a sterowanie wraca do funkcji wywołującej.

Rozwijanie i zwijanie

Rekurencja ma dwie fazy. Rozwijanie następuje wtedy, gdy wywołania schodzą coraz głębiej w kierunku przypadku bazowego.

Zwijanie następuje wtedy, gdy przypadek bazowy zwraca wynik, a każde wywołanie kończy swoją pracę, korzystając ze zwróconej wartości.

#include <stdio.h>

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

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

Wartości zwracane wracają

Wartość zwrócona przez głębsze wywołanie jest używana przez wywołanie, które je utworzyło.

Dlatego kolejność ma znaczenie: najgłębsze wywołanie kończy się jako pierwsze, a następnie wyniki są łączone podczas powrotu w górę stosu.

int power(int base, int exp) {
    if (exp == 0) return 1;
    return base * power(base, exp - 1);
}

Wyświetlanie podczas rekurencji

Można wyświetlać wartości przed wywołaniem rekurencyjnym lub po nim. Wyświetlanie przed wywołaniem pokazuje liczby podczas schodzenia w dół, a wyświetlanie po wywołaniu — podczas powrotu w górę.

#include <stdio.h>

void down(int n) {
    if (n == 0) return;
    printf("%d ", n);
    down(n - 1);
}

int main(void) {
    down(5);
    printf("\n");
    return 0;
}

Wyświetlanie podczas powrotu

Przenieś printf za wywołanie rekurencyjne, a kolejność się odwróci. Najgłębsze wywołanie wyświetli wynik jako pierwsze.

Program wyświetli 1 2 3 4 5 zamiast 5 4 3 2 1.

#include <stdio.h>

void up(int n) {
    if (n == 0) return;
    up(n - 1);
    printf("%d ", n);
}

int main(void) {
    up(5);
    printf("\n");
    return 0;
}

Dwie zasady do zapamiętania

Poprawna funkcja rekurencyjna przestrzega dwóch zasad:

1. Ma co najmniej jeden przypadek bazowy, który zwraca wynik bez rekurencji.
2. Każde wywołanie rekurencyjne przybliża argument do przypadku bazowego.

Naruszenie którejkolwiek z tych zasad powoduje nieskończoną pętlę programu.

Szybkie sprawdzenie

Sprawdź swoją znajomość podstaw rekurencji.

Podsumowanie

Rekurencja rozwiązuje problem, wywołując samą siebie dla mniejszych danych wejściowych. Zawsze potrzebujesz przypadku bazowego, który zatrzyma rekurencję, oraz przypadku rekurencyjnego, który do niego przybliża.

Każde wywołanie korzysta z ramki stosu, a wyniki wracają podczas zwijania wywołań.

Często zadawane pytania

Czy lekcja „Jak działa rekurencja” jest bezpłatna?

Tak — pełny tekst „Jak działa rekurencja” 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 „Jak działa rekurencja”?

Przypadki bazowe i stos wywołań. Ć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 1 z 4.

Ile czasu zajmuje lekcja „Jak działa rekurencja”?

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