Myślenie rekurencyjne: baza i rekurencja
Rozbijanie problemu na mniejsze kopie
Myślenie rekurencyjne: baza i rekurencja to bezpłatna lekcja Coding Interview Prep 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 Coding Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs Coding Interview Prep 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. 🎯
Ucz się Coding Interview Prep dzięki korepetycjom AI — za darmo
Pisz i uruchamiaj kod w przeglądarce, otrzymuj natychmiastową pomoc od korepetytora AI dostępnego 24/7 i kontynuuj naukę w sieci lub w aplikacji.
- Kursy
- 90
- Lekcje
- 360
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 Coding Interview Prep, przejdź na CoddyKit PRO. Kurs Coding Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Myślenie rekurencyjne: baza i rekurencja”?
Rozbijanie problemu na mniejsze kopie Ćwiczysz Coding Interview Prep 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ąć Coding Interview Prep?
Nie wymagamy żadnego doświadczenia. Coding Interview Prep 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 Coding Interview Prep?
Tak. Każda lekcja Coding Interview Prep 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