C Academy · Lekcja

Klasyczne problemy rekurencyjne

Silnia i ciąg Fibonacciego.

Klasyczne problemy rekurencyjne to bezpłatna lekcja C Academy na CoddyKit. To lekcja 2 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.

Klasyczne problemy

Niektóre problemy w naturalny sposób pasują do rekurencji. Poznanie klasycznych przykładów daje wzorce, które można ponownie wykorzystać.

W tej lekcji omówimy silnię, ciąg Fibonacciego, sumę cyfr, największy wspólny dzielnik oraz odwracanie kolejności wyświetlanych elementów.

Silnia

Silnia liczby n to n pomnożone przez silnię liczby n minus 1, przy czym 1! jest równe 1.

To podręcznikowy przykład rekurencji: ma jasny przypadek bazowy i jedno wywołanie rekurencyjne.

#include <stdio.h>

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

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

Liczby Fibonacciego

Każda liczba Fibonacciego jest sumą dwóch poprzednich. Rekurencyjna definicja wymaga dwóch przypadków bazowych: fib(0)=0 i fib(1)=1.

W tej wersji na każdym etapie wykonywane są dwa wywołania.

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

Uruchamianie ciągu Fibonacciego

Oto kompletny program. fib(10) powinno wyświetlić 55.

Pamiętaj, że ta naiwna wersja wielokrotnie wykonuje tę samą pracę, więc dla dużych wartości n działa wolno.

#include <stdio.h>

int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}

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

Suma cyfr

Aby dodać cyfry liczby, pobierz ostatnią cyfrę za pomocą n % 10, a następnie wykonaj rekurencję dla pozostałej części za pomocą n / 10.

Przypadkiem bazowym jest osiągnięcie przez n wartości 0.

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

Suma cyfr w praktyce

Dla 1234 suma wynosi 1+2+3+4 = 10. Potwierdźmy to za pomocą kompletnego programu.

#include <stdio.h>

int digit_sum(int n) {
    if (n == 0) return 0;
    return (n % 10) + digit_sum(n / 10);
}

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

Największy wspólny dzielnik

Algorytm Euklidesa w naturalny sposób nadaje się do implementacji rekurencyjnej. NWD liczb a i b jest równy NWD liczb b i a % b.

Gdy b osiągnie wartość 0, odpowiedzią jest a.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Kompletny program NWD

NWD liczb 48 i 18 wynosi 6. Ten program go wyświetla.

#include <stdio.h>

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

int main(void) {
    printf("%d\n", gcd(48, 18));
    return 0;
}

Odwracanie liczby

Rekurencja może również sterować wyświetlaniem. Wyświetlanie ostatniej cyfry po wykonaniu rekurencji w naturalny sposób odwraca kolejność przetwarzania.

Ta funkcja pomocnicza wyświetla każdą cyfrę liczby osobno, korzystając z rekurencji.

#include <stdio.h>

void print_digits(int n) {
    if (n == 0) return;
    print_digits(n / 10);
    printf("%d ", n % 10);
}

int main(void) {
    print_digits(729);
    printf("\n");
    return 0;
}

Funkcja potęgowa

Potęgowanie podstawy do wykładnika również można zdefiniować rekurencyjnie: base^exp jest równe base pomnożonemu przez base^(exp-1).

Przypadkiem bazowym jest wykładnik 0, dla którego wynikiem jest 1.

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

Wzorce, które można ponownie wykorzystać

Proszę zwrócić uwagę na wspólną strukturę: sprawdzamy przypadek bazowy, a następnie łączymy bieżący krok z wynikiem mniejszego wywołania.

Gdy dostrzegą Państwo ten wzorzec, wiele problemów można rozwiązać za pomocą krótkich funkcji rekurencyjnych.

Szybkie sprawdzenie

Proszę wybrać poprawne przypadki bazowe.

Podsumowanie

Silnia, ciąg Fibonacciego, suma cyfr, NWD i potęgowanie mają wspólny wzorzec rekurencyjny: obsłużyć przypadek bazowy, a następnie połączyć bieżącą wartość z mniejszym podproblemem.

Te schematy można zastosować także w wielu innych zadaniach.

Często zadawane pytania

Czy lekcja „Klasyczne problemy rekurencyjne” jest bezpłatna?

Tak — pełny tekst „Klasyczne problemy rekurencyjne” 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 „Klasyczne problemy rekurencyjne”?

Silnia i ciąg Fibonacciego. Ć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 2 z 4.

Ile czasu zajmuje lekcja „Klasyczne problemy rekurencyjne”?

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