Schemat rekurencji: przypadek bazowy, zaufanie, budowa
Zastosują Państwo trzyetapową metodę do pisania poprawnych rozwiązań rekurencyjnych dla silni, potęgowania i sumy cyfr bez śledzenia każdego wywołania.
Schemat rekurencji: przypadek bazowy, zaufanie, budowa 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.
Dlaczego rekurencja wydaje się trudna
Większość początkujących próbuje śledzić w myślach każde wywołanie rekurencyjne, co szybko staje się przytłaczające nawet przy rekurencji o głębokości pięciu poziomów. Profesjonalne podejście polega na użyciu trzystopniowego schematu — przypadku bazowego, zaufania i budowania — który pozwala pisać poprawne funkcje rekurencyjne bez mentalnego symulowania całego drzewa wywołań.
Ten schemat bywa nazywany skokiem wiary: zakłada się, że funkcja działa dla mniejszych danych wejściowych, a następnie wykorzystuje to założenie do zbudowania rozwiązania dla większych danych.
Krok 1: Zdefiniuj przypadek bazowy
Przypadek bazowy to najprostsze dane wejściowe, dla których odpowiedź jest znana bez dalszej rekurencji. Każda funkcja rekurencyjna musi mieć co najmniej jeden przypadek bazowy; w przeciwnym razie będzie wywoływać samą siebie w nieskończoność (przepełnienie stosu). Dobrymi przypadkami bazowymi są: pusta lista, pojedynczy element, n == 0, n == 1 lub sytuacja, w której problem sprowadza się do trywialnej tożsamości.
Najpierw należy zapisać przypadek bazowy, przed jakąkolwiek logiką rekurencyjną. Można go zidentyfikować, zadając sobie pytanie: „Jaka jest najmniejsza wersja tego problemu, na którą mogę odpowiedzieć od razu?”
# Base cases for common problems
def factorial(n):
if n == 0: # base case: 0! = 1
return 1
# ... recursive step below
def sum_list(lst):
if not lst: # base case: sum of empty list is 0
return 0
# ...
def height(node):
if node is None: # base case: height of null node is 0
return 0
# ...
print('Base cases identified')Krok 2: Zaufaj wywołaniu rekurencyjnemu
Krok zaufania polega na przyjęciu założenia: należy założyć, że funkcja działa już poprawnie dla dowolnych danych wejściowych ściśle mniejszych od bieżących. Nie trzeba teraz dowodzić tego dla każdego mniejszego wejścia — gwarantuje to dowód indukcyjny. Wystarczy wywołać funkcję dla mniejszego podproblemu i zaufać, że zwróci poprawny wynik.
To właśnie ten krok początkujący często pomijają, próbując zamiast tego prześledzić wszystko w pamięci. Nie należy ulegać tej pokusie; po przyswojeniu tego schematu można stosować go do rekurencji o dowolnej głębokości.
# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11 (we TRUST this, don't trace it)
# Build: 3 + 11 = 14
# So:
def sum_list(lst):
if not lst:
return 0
# Trust that sum_list(lst[1:]) returns sum of the rest
return lst[0] + sum_list(lst[1:])
print(sum_list([3, 1, 4, 1, 5])) # 14Krok 3: Zbuduj rozwiązanie
Krok budowania łączy wynik zaufanego podproblemu z wkładem bieżącego elementu, aby uzyskać odpowiedź dla całych danych wejściowych. Zwykle jest to pojedynczy wiersz: zastosowanie operacji do bieżącego elementu i wyniku wywołania rekurencyjnego. Typowe sposoby budowania to: dodanie do sumy, dodanie elementu na początku listy, zwiększenie licznika lub połączenie dwóch wyników podproblemów.
def factorial(n):
if n == 0:
return 1
# Trust: factorial(n-1) gives (n-1)!
# Build: n * (n-1)! = n!
return n * factorial(n - 1)
def power(base, exp):
if exp == 0:
return 1
# Trust: power(base, exp-1) gives base^(exp-1)
# Build: base * base^(exp-1) = base^exp
return base * power(base, exp - 1)
print(factorial(6)) # 720
print(power(2, 10)) # 1024Zastosowanie schematu do sumy cyfr
Problem: obliczyć sumę cyfr nieujemnej liczby całkowitej. Przypadek bazowy: n == 0 → suma wynosi 0 (lub n < 10 → sama wartość n). Zaufanie: sumDigits(n // 10) zwraca sumę wszystkich cyfr oprócz ostatniej. Budowanie: dodać ostatnią cyfrę n % 10 do zaufanego wyniku. Schemat prowadzi do rozwiązania w trzech deklaratywnych krokach.
def sumDigits(n):
if n < 10:
return n # base case: single digit
# Trust: sumDigits(n // 10) gives sum of all digits except last
# Build: add the last digit
return n % 10 + sumDigits(n // 10)
print(sumDigits(0)) # 0
print(sumDigits(7)) # 7
print(sumDigits(123)) # 6
print(sumDigits(9999)) # 36Fibonacci: dwa podproblemy
Fibonacci wymaga dwóch wywołań rekurencyjnych: fib(n-1) i fib(n-2). Zastosowanie schematu wygląda następująco: przypadki bazowe to fib(0) = 0 i fib(1) = 1. Zaufanie: oba mniejsze wywołania zwracają poprawne wartości Fibonacciego. Budowanie: zwrócić ich sumę. Ta naiwna implementacja ma złożoność czasową O(2^n) — naprawimy to w lekcji o memoizacji.
def fib(n):
if n <= 1:
return n # base cases: fib(0)=0, fib(1)=1
# Trust both smaller sub-problems
return fib(n - 1) + fib(n - 2)
for i in range(8):
print(f'fib({i}) = {fib(i)}') # 0,1,1,2,3,5,8,13Odwracanie ciągu znaków rekurencyjnie
Problem: rekurencyjnie odwrócić ciąg znaków. Przypadek bazowy: pusty ciąg lub pojedynczy znak — jest już odwrócony. Zaufanie: reverse(s[1:]) zwraca odwrócenie wszystkiego po pierwszym znaku. Budowanie: dodać pierwszy znak na końcu odwróconego sufiksu. Schemat daje rozwiązanie w trzech wierszach.
def reverse_str(s):
if len(s) <= 1:
return s # base case
# Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
# Build: append first character at end
return reverse_str(s[1:]) + s[0]
print(reverse_str('')) # ''
print(reverse_str('a')) # 'a'
print(reverse_str('hello')) # 'olleh'
print(reverse_str('racecar')) # 'racecar'Rekurencyjne zliczanie wystąpień
Problem: rekurencyjnie zliczyć wystąpienia wartości docelowej na liście. Przypadek bazowy: pusta lista — liczba wystąpień wynosi 0. Zaufanie: count(lst[1:], target) zwraca liczbę wystąpień w ogonie listy. Budowanie: dodać 1, jeśli pierwszy element jest zgodny z wartością docelową, a w przeciwnym razie dodać 0. Każdy krok rekurencji przybliża rozwiązanie do przypadku bazowego, zmniejszając rozmiar listy o 1.
def count_occurrences(lst, target):
if not lst:
return 0
# Trust: count in rest of list is handled recursively
# Build: add 1 if first element matches, else 0
return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)
print(count_occurrences([1, 2, 3, 2, 4, 2], 2)) # 3
print(count_occurrences([], 5)) # 0
print(count_occurrences([7, 7, 7], 7)) # 3Sprawdzanie, czy lista jest posortowana
Problem: rekurencyjnie sprawdzić, czy lista jest posortowana rosnąco. Przypadek bazowy: lista zawierająca 0 lub 1 element jest zawsze posortowana. Zaufanie: is_sorted(lst[1:]) informuje, czy ogon listy jest posortowany. Budowanie: lista jest posortowana, jeśli pierwszy element jest <= drugiego ORAZ ogon jest posortowany. To przejrzysty przykład, w którym krok budowania wykorzystuje logiczną koniunkcję dwóch warunków.
def is_sorted(lst):
if len(lst) <= 1:
return True
# Trust: is_sorted(lst[1:]) tells us if tail is sorted
# Build: head <= second element AND tail is sorted
return lst[0] <= lst[1] and is_sorted(lst[1:])
print(is_sorted([])) # True
print(is_sorted([1])) # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # FalseWyszukiwanie binarne rekurencyjnie (powtórzenie)
Wyszukiwanie binarne wyrażone rekurencyjnie za pomocą tego schematu: przypadek bazowy: lo > hi → nie znaleziono elementu (zwrócić -1). Zaufanie: wywołanie rekurencyjne dla właściwej połowy znajdzie wartość docelową albo zwróci -1. Budowanie: obliczyć mid, porównać wartości i wywołać funkcję dla odpowiedniej połowy. Postać rekurencyjna wyraźnie pokazuje strukturę dziel i zwyciężaj, choć w środowisku produkcyjnym preferowana jest postać iteracyjna ze względu na stałą złożoność pamięciową O(1).
def binary_search(arr, target, lo, hi):
if lo > hi: # base case: search space exhausted
return -1
mid = lo + (hi - lo) // 2
if arr[mid] == target:
return mid
# Trust both halves return correct results
if arr[mid] < target:
return binary_search(arr, target, mid + 1, hi)
else:
return binary_search(arr, target, lo, mid - 1)
arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1)) # 3
print(binary_search(arr, 4, 0, len(arr) - 1)) # -1Kiedy używać rekurencji, a kiedy iteracji
Rekurencja sprawdza się doskonale, gdy problem w naturalny sposób dzieli się na mniejsze podproblemy tego samego typu (drzewa, algorytmy dziel i zwyciężaj, przeszukiwanie z nawrotami). Iteracja jest preferowana, gdy: głębokość rekurencji jest duża (co grozi przepełnieniem stosu w Pythonie, którego domyślny limit wynosi około 1000), wersje rekurencyjna i iteracyjna są równie przejrzyste lub problem jest prostą pętlą (silnia, Fibonacci bez memoizacji).
Dobrą regułą praktyczną jest: jeśli narysowanie drzewa rekurencji wydaje się naturalne, należy użyć rekurencji. Jeśli drzewo jest prostą linią (rekurencja ogonowa), należy przejść na iterację.
import sys
# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit()) # 1000
# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
total = 0
for x in lst:
total += x
return total
big = list(range(2000))
print(sum_list_iter(big)) # 1999000 — no stack overflowSzybki test
Sprawdź swoje rozumienie zagadnień z kursu Data Structures & Algorithms — Coding Interview Prep omówionych w tej lekcji.
Podsumowanie lekcji
W tej lekcji poznano: trzyetapowy schemat obejmujący przypadek bazowy (najprostsza znana odpowiedź), zaufanie (założenie, że podproblem jest rozwiązany) i budowanie (połączenie bieżącego elementu z zaufanym wynikiem), konieczność zapisywania przypadków bazowych w pierwszej kolejności i unikania odtwarzania w pamięci całych drzew wywołań oraz stosowanie iteracji, gdy głębokość rekurencji grozi przepełnieniem stosu lub gdy postacie rekurencyjna i iteracyjna są równie przejrzyste. W następnej części szczegółowo zwizualizujemy stos wywołań.
Często zadawane pytania
Czy lekcja „Schemat rekurencji: przypadek bazowy, zaufanie, budowa” jest bezpłatna?
Tak — pełny tekst „Schemat rekurencji: przypadek bazowy, zaufanie, budowa” 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 „Schemat rekurencji: przypadek bazowy, zaufanie, budowa”?
Zastosują Państwo trzyetapową metodę do pisania poprawnych rozwiązań rekurencyjnych dla silni, potęgowania i sumy cyfr bez śledzenia każdego wywołania. Ć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 „Schemat rekurencji: przypadek bazowy, zaufanie, budowa”?
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
- Schemat rekurencji: przypadek bazowy, zaufanie, budowa
- Wizualizacja stosu wywołań
- Kompromisy między rekurencją a iteracją
- Memoizacja: buforowanie wyników rekurencji