Zadanie z rekurencją sprowadza się zwykle do jednego z dwóch poleceń: podaj wartość zwróconą przez wywołanie albo policz, ile razy funkcja się wywoła. Za każdym razem robisz to samo — znajdujesz warunek początkowy, rozpisujesz wywołania schodkowo w dół i dopiero potem zwijasz wyniki. Kiedy w zadaniu pojawia się Fibonacci, pytanie prawie zawsze dotyczy tego, dlaczego program działa wolno. Sama rekurencja bywa na starcie ciężka, zwłaszcza gdy trzeba ją napisać samodzielnie. Skoro jednak komputer jest do dyspozycji przez cały egzamin, uczymy przepisywać taką funkcję do środowiska i po prostu sprawdzać wynik — zliczanie wywołań przestaje wtedy być zgadywanką.

1. Każda rekurencja ma dwie części

Niezależnie od tego, czy patrzysz na silnię, Fibonacciego czy Euklidesa, rekurencja zawsze składa się z tych samych dwóch elementów. Jeśli zabraknie któregokolwiek, program zapętla się w nieskończoność.

Warunek początkowy — sytuacja, w której funkcja zwraca wynik bez wywoływania siebie.
Wywołanie rekurencyjne — krok, który zbliża argument do warunku początkowego.

def silnia(n):
  if n <= 1:          # warunek początkowy
      return 1
  return n * silnia(n - 1)   # krok rekurencyjny

2. Rozwijanie wywołań na kartce

Najczęstsze polecenie brzmi: „podaj wartość zwróconą przez wywołanie" albo „ile razy wykona się instrukcja". Trzeba wtedy rozpisać drzewo wywołań. Rób to schodkowo, od góry w dół, i dopiero potem zwijaj wyniki z powrotem.

silnia(4) = 4 · silnia(3)

silnia(3) = 3 · silnia(2)

silnia(2) = 2 · silnia(1)

silnia(1) = 1 ← warunek początkowy

zwijamy: 2 · 1 = 2, potem 3 · 2 = 6, na koniec 4 · 6 = 24

Wyniki zwijaj dopiero po dojściu do warunku początkowego. Próba liczenia „w locie", w trakcie schodzenia w dół, to najczęstsze źródło błędów w tym zadaniu.

3. Fibonacci i pułapka wykładnicza

Naiwny Fibonacci wywołuje się dwa razy w każdym kroku, przez co liczba wywołań rośnie wykładniczo — złożoność rzędu $O(2^n)$ . To ulubiony materiał na pytanie „dlaczego program działa wolno".

def fib(n):
  if n <= 1:
      return n
  return fib(n-1) + fib(n-2)   # dwa wywolania - drzewo sie rozgalezia

Rozwiązaniem jest zapamiętywanie wyników albo wersja iteracyjna, która schodzi do $O(n)$ . Jeśli w zadaniu pada słowo „usprawnij", chodzi właśnie o to.

Ile dokładnie wywołań

Naiwne fib(n) wykonuje $2 \cdot Fib(n+1) - 1$ wywołań. Dla $n = 10$ to 177 wywołań, dla $n = 30$ już ponad 2,7 miliona, a dla $n = 50$ — liczba dwunastocyfrowa. Jeśli polecenie prosi o uzasadnienie „dlaczego program nie kończy pracy”, wystarczy pokazać tę zależność, nie trzeba mierzyć czasu.

4. Dwa sposoby na usprawnienie

Oba są na egzaminie akceptowane, oba schodzą do $O(n)$ . Wybierz ten, który szybciej napiszesz bez błędu.

# 1. spamietywanie - zachowuje zapis rekurencyjny
pamiec = {}

def fib(n):
  if n <= 1:
      return n
  if n in pamiec:
      return pamiec[n]
  pamiec[n] = fib(n-1) + fib(n-2)
  return pamiec[n]


# 2. wersja iteracyjna - najpewniejsza, bez ryzyka przepelnienia stosu
def fib_iter(n):
  a, b = 0, 1
  for _ in range(n):
      a, b = b, a + b
  return a

Każde wywołanie zajmuje miejsce na stosie wywołań, a ten jest ograniczony — w Pythonie domyślnie do około tysiąca zagnieżdżeń. Rekurencyjna suma miliona elementów przerwie się komunikatem o przekroczeniu maksymalnej głębokości. W takim zadaniu wersja z pętlą to nie kwestia gustu, tylko jedyne rozwiązanie, które zadziała.

5. Rekurencje, które naprawdę wracają w arkuszach

Wbrew pozorom repertuar CKE jest wąski. Te cztery warto umieć napisać z pamięci — razem z liczbą kroków, bo o nią zwykle pada drugie pytanie.

# NWD algorytmem Euklidesa - bardzo szybki, ok. log(n) krokow
def nwd(a, b):
  if b == 0:
      return a
  return nwd(b, a % b)


# szybkie potegowanie - O(log n) zamiast O(n)
def potega(a, n):
  if n == 0:
      return 1
  if n % 2 == 0:
      polowa = potega(a, n // 2)
      return polowa * polowa
  return a * potega(a, n - 1)


# zamiana na system dwojkowy - reszty czytane "przy powrocie"
def na_bin(n):
  if n < 2:
      return str(n)
  return na_bin(n // 2) + str(n % 2)


# suma cyfr liczby
def suma_cyfr(n):
  if n == 0:
      return 0
  return n % 10 + suma_cyfr(n // 10)

Wieże Hanoi — przeniesienie $n$ krążków wymaga dokładnie $2^n - 1$ ruchów. To najczęstsze pytanie „ile operacji” w całym dziale.
Wyszukiwanie binarne w wersji rekurencyjnej robi najwyżej $\log_2 n$ wywołań — i wymaga posortowanej tablicy, co trzeba w odpowiedzi napisać.
Szybkie potęgowanie liczy $a^{20}$ w pięciu mnożeniach zamiast dwudziestu, bo połowę pracy zastępuje podniesieniem do kwadratu.

6. Zliczanie wywołań bez zgadywania

Komputer stoi na stanowisku przez całe 150 minut części praktycznej i nic nie stoi na przeszkodzie, żeby użyć go do sprawdzenia odpowiedzi z części teoretycznej. Dopisz licznik, uruchom, porównaj z tym, co wyszło ci na kartce.

licznik = 0

def fib(n):
  global licznik
  licznik += 1
  if n <= 1:
      return n
  return fib(n-1) + fib(n-2)

print(fib(10), licznik)   # 55 177

Ta sama sztuczka działa przy pytaniach o liczbę porównań w sortowaniu i o liczbę obrotów pętli. Wynik z kartki traktuj jako właściwą odpowiedź, a wydruk — jako kontrolę. Jeśli się różnią, błąd prawie zawsze siedzi w policzeniu wywołania początkowego.

7. Co sprawdza egzaminator

Brak warunku początkowego — program nigdy się nie zatrzyma, a zadanie idzie na zero.
Krok, który nie zbliża do końca. Wywołanie f(n) wewnątrz f(n) to ta sama pętla bez końca.
Mylenie liczby wywołań z wynikiem. Czytaj uważnie, o co pytają.
Nieuwzględnienie wywołania początkowego przy zliczaniu — to klasyczna pomyłka o jeden.

Przeczytaj też

Najczęstsze błędy na maturze z informatyki

Lista pomyłek, które kosztują punkty mimo poprawnego rozumowania — i sposoby, żeby ich uniknąć.

Uczysz się w technikum informatycznym? Prowadzimy też przygotowanie do kwalifikacji INF.02, INF.03 i INF.04. Zobacz egzaminy zawodowe →

Rekurencja i Jej Rozwijanie