Myślenie rekurencyjne: baza i rekurencja
Rozbijanie problemu na mniejsze kopie
Myślenie rekurencyjne: baza i rekurencja to bezpłatna lekcja Competitive Programming 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 Competitive Programming Academy, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Na czym polega rekurencja
Rekurencja to funkcja, która rozwiązuje problem, wywołując samą siebie dla mniejszego fragmentu, aż fragment będzie wystarczająco mały, aby odpowiedzieć bezpośrednio. 🌀
Zaufaj mniejszej wersji
Najważniejsze podejście to skok wiary: załóż, że wywołanie rekurencyjne działa już dla mniejszych danych, a następnie zbuduj na nim swoją odpowiedź.
Każda rekurencja potrzebuje przypadku bazowego
Przypadek bazowy to najmniejsze dane wejściowe, dla których udzielasz odpowiedzi bez rekurencji. Bez niego funkcja wywołuje samą siebie bez końca i kończy się błędem.
Przypadek rekurencyjny
Przypadek rekurencyjny zmniejsza problem i wywołuje funkcję dla mniejszej wersji. Każde wywołanie musi przybliżać rozwiązanie do przypadku bazowego.
Silnia jako pierwszy przykład
Tutaj silnia pokazuje obie części: przypadek bazowy dla zera i wywołanie rekurencyjne dla n pomniejszonego o jeden.
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)Jak działa stos wywołań
Każde wywołanie czeka na stosie wywołań, aż zakończy się jego wewnętrzne wywołanie. Najgłębsze wywołanie kończy się jako pierwsze, a następnie wyniki wracają po kolei w górę.
Kontrolowanie głębokości rekurencji
Python domyślnie ogranicza głębokość rekurencji do około 1000. Głęboka rekurencja w zadaniach konkursowych wymaga użycia sys.setrecursionlimit, aby uniknąć błędu wykonania.
import sys
sys.setrecursionlimit(300000)Postęp przy każdym wywołaniu
Poprawna rekurencja zawsze zmniejsza dane wejściowe, zbliżając je do przypadku bazowego. Jeśli kiedykolwiek ponownie przetworzy dane o tym samym rozmiarze, zapętli się na zawsze. ⚠️
Rekurencyjne sumowanie listy
Ta suma rekurencyjna odłącza pierwszy element, a następnie polega na wywołaniu, które doda resztę listy.
def total(a):
if not a:
return 0
return a[0] + total(a[1:])Drzewa rekurencji pokazują rozgałęzienia
Gdy funkcja wykonuje więcej niż jedno wywołanie, powstaje drzewo rekurencji. Jego rozmiar określa całkowity koszt obliczeń.
Powtarzanie obliczeń może spowalniać program
Naiwna wersja algorytmu Fibonacciego wielokrotnie oblicza te same wartości, co prowadzi do wykładniczej złożoności czasowej. Zapamiętywanie tych wyników natychmiast rozwiązuje problem.
Szybkie sprawdzenie
Co się stanie, jeśli funkcja rekurencyjna nie będzie miała przypadku bazowego?
Podsumowanie: dwie części, jedna idea
Dowiedzieli się Państwo, że rekurencja potrzebuje przypadku bazowego, który ją zatrzyma, oraz przypadku rekurencyjnego, który zmniejsza dane wejściowe. Wystarczy zaufać mniejszemu wywołaniu, a reszta wyniknie sama. 🎯
Często zadawane pytania
Czy lekcja „Myślenie rekurencyjne: baza i rekurencja” jest bezpłatna?
Tak — pełny tekst „Myślenie rekurencyjne: baza i 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 Competitive Programming Academy, przejdź na CoddyKit PRO. Kurs Competitive Programming Academy zawiera 4 lekcji w sumie.
Co nauczysz się w „Myślenie rekurencyjne: baza i rekurencja”?
Rozbijanie problemu na mniejsze kopie Ćwiczysz Competitive Programming 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ąć Competitive Programming Academy?
Nie wymagamy żadnego doświadczenia. Competitive Programming 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 „Myślenie rekurencyjne: baza i 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 Competitive Programming Academy?
Tak. Każda lekcja Competitive Programming 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
- Myślenie rekurencyjne: baza i rekurencja
- Generowanie wszystkich podzbiorów
- Permutacje i idea N hetmanów
- Przycinanie, aby zmieścić się w limicie czasu