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.

4. 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

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

2. Rozwijanie wywołań na kartce

3. Fibonacci i pułapka wykładnicza

4. Co sprawdza egzaminator

Zdajesz maturę rozszerzoną z informatyki?

Nadal czujesz się niepewnie?