Rekurencja na maturze z informatyki: jak ją zapisać

Rekurencja na maturze z informatyki pojawia się w dwóch rolach: jako technika, którą trzeba zastosować w zadaniu programistycznym, i jako zapis, który trzeba prześledzić na kartce i podać wynik. W obu przypadkach ocenia się to samo, czyli czy algorytm ma poprawnie dobrany warunek stopu i czy każde kolejne wywołanie rzeczywiście zmniejsza problem.

Z czego składa się poprawna funkcja rekurencyjna

Funkcja rekurencyjna składa się z trzech części i brak którejkolwiek z nich zmienia poprawny pomysł w niedziałający kod.

Pierwsza to przypadek bazowy, czyli warunek, przy którym funkcja zwraca wynik bez dalszych wywołań. Druga to wywołanie samej siebie na danych mniejszych od wejściowych, przy czym słowo „mniejszych" trzeba rozumieć dosłownie: każde wywołanie ma zbliżać do przypadku bazowego. Trzecia to złożenie, czyli sposób, w jaki wynik wywołania podrzędnego przekłada się na wynik wywołania bieżącego.

Przy silni złożenie jest mnożeniem wyniku podrzędnego przez bieżący argument, a przypadkiem bazowym silnia zera. Przy algorytmie Euklidesa złożeniem jest samo przekazanie wyniku wyżej, a przypadkiem bazowym reszta z dzielenia równa zeru. Jeśli w zapisie na kartce widać wszystkie trzy elementy, rozwiązanie jest czytelne również dla egzaminatora, który nie zna twojego stylu pisania.

Warunek stopu jest najczęstszą przyczyną zera

Rekurencja bez warunku stopu albo z warunkiem, którego argumenty nigdy nie spełnią, wywołuje się w nieskończoność i kończy przepełnieniem stosu. To jest najczęstszy błąd w tym temacie i wychodzi przy pierwszym uruchomieniu, więc w części praktycznej egzaminu da się go złapać samodzielnie.

Trudniejszy wariant tego samego błędu polega na tym, że warunek stopu istnieje, ale nie obejmuje wszystkich dróg dojścia. Funkcja działa dla przykładu z treści zadania i zawiesza się dla wartości granicznej, na przykład dla zera, dla listy jednoelementowej albo dla wejścia pustego. Sprawdzenie wartości granicznych zajmuje chwilę i wyłapuje większość takich przypadków.

Wieże Hanoi, czyli rekurencja, którą da się prześledzić

Wieże Hanoi są w tym temacie standardowym przykładem, bo cały algorytm mieści się w jednym zdaniu: przenieś wieżę o jeden krążek mniejszą na słupek pomocniczy, przenieś największy krążek na docelowy, przenieś mniejszą wieżę z pomocniczego na docelowy. Przypadkiem bazowym jest wieża pusta albo jednokrążkowa.

Z tego zapisu wynika liczba ruchów potrzebna do przeniesienia wieży o n krążkach, równa 2 do potęgi n minus jeden. Zadania na kartce często pytają właśnie o liczbę wywołań albo ruchów przy zadanym n, a nie o kod. Warunkiem poprawnej odpowiedzi jest prześledzenie zależności rekurencyjnej, a nie wyliczanie kolejnych ruchów po kolei.

Fraktale, czyli ta sama zasada na rysunku

Fraktale rekurencyjne, jak trójkąt Sierpińskiego czy drzewo binarne, działają dokładnie tak samo, tylko złożeniem wyniku jest narysowanie figury. Procedura rysuje element, po czym wywołuje samą siebie dla mniejszych fragmentów, aż rozmiar albo licznik poziomów spadnie do wartości granicznej. Ten licznik poziomów pełni rolę warunku stopu i jego pominięcie jest w tych zadaniach najczęstszą usterką.

Kiedy rekurencja jest pułapką

Rekurencja opisuje problem zwięźle, ale nie zawsze liczy go efektywnie. Klasycznym przykładem jest wyznaczanie wyrazów ciągu Fibonacciego wprost z definicji: każde wywołanie rozgałęzia się na dwa, a te same wyrazy liczone są wielokrotnie od zera. Liczba wywołań rośnie wtedy wykładniczo i dla większych argumentów program przestaje kończyć pracę w rozsądnym czasie.

Lekarstwem jest zapamiętywanie wyników już policzonych podproblemów albo przejście na obliczenie iteracyjne od najmniejszych wyrazów w górę. To jest właśnie granica między rekurencją a programowaniem dynamicznym: rekurencja opłaca się tam, gdzie podproblemy są rozłączne, a zapamiętywanie wyników tam, gdzie się powtarzają.

Metoda połowienia, nazywana też strategią dziel i zwyciężaj, jest przykładem tego pierwszego przypadku. Wyszukiwanie binarne w każdym kroku odrzuca połowę zbioru, a sortowanie przez scalanie dzieli tablicę na dwie rozłączne części, więc żaden podproblem nie jest liczony dwa razy.

Rekurencja czy iteracja w zadaniu egzaminacyjnym

Jeśli polecenie nie wymaga konkretnej techniki, wybór należy do zdającego i ocenia się poprawność algorytmu, nie formę. Rekurencja wygrywa czytelnością tam, gdzie problem sam ma budowę rekurencyjną, czyli przy fraktalach, wieżach Hanoi i przechodzeniu drzew. Iteracja wygrywa tam, gdzie pętla jest prostsza do prześledzenia i nie grozi przepełnieniem stosu przy dużych danych.

Przy zapisie na kartce obowiązują te same konwencje co przy każdym innym algorytmie, opisane we wpisie o zasadach zapisu pseudokodu. Przy zadaniu praktycznym w Pythonie przydaje się wcześniejsze sprawdzenie, jak zachowuje się interpreter przy głębokiej rekurencji, o czym szerzej we wpisie o Pythonie na maturze.

Najczęstsze pytania

Czy każdą rekurencję da się zapisać iteracyjnie?

Tak. Każdy algorytm rekurencyjny ma odpowiednik iteracyjny, choć w trudniejszych przypadkach wymaga on własnego stosu przechowującego stan odłożonych wywołań. Dla silni, algorytmu Euklidesa czy ciągu Fibonacciego zamiana na pętlę jest prosta i zwykle daje szybszy program.

Po czym poznać, że warunek stopu jest zły?

Po tym, że program nie kończy pracy albo przerywa się komunikatem o przepełnieniu stosu. Przy śledzeniu na kartce widać to jako ciąg wywołań, w którym argument nie zbliża się do wartości granicznej. Sprawdzenie wejścia pustego i najmniejszego dopuszczalnego wyłapuje większość takich usterek.

Czy rekurencja jest zawsze wolniejsza od pętli?

Nie zawsze, ale każde wywołanie kosztuje odłożenie stanu na stosie, więc przy tym samym algorytmie wersja iteracyjna bywa szybsza. Realny problem pojawia się dopiero wtedy, gdy rekurencja liczy te same podproblemy wielokrotnie. Wtedy różnica nie dotyczy stałej, tylko rzędu liczby operacji.

Jak liczyć liczbę wywołań w zadaniu na kartce?

Zapisując zależność rekurencyjną wiążącą liczbę wywołań dla argumentu n z liczbą wywołań dla argumentów mniejszych, a potem rozwijając ją od przypadku bazowego. Wypisywanie wszystkich wywołań po kolei działa dla małych n i przestaje działać dokładnie wtedy, gdy zadanie robi się punktowane.

Które algorytmy rekurencyjne pojawiają się najczęściej?

Algorytm Euklidesa, szybkie potęgowanie, wyszukiwanie binarne, sortowanie przez scalanie, fraktale rekurencyjne oraz przechodzenie struktur drzewiastych. Wszystkie mieszczą się w kanonie algorytmów wymaganych na poziomie rozszerzonym i wszystkie warto umieć zapisać w obu wersjach.

Jak to sprawdzisz w zdawce

W zdawce zadanie algorytmiczne oceniane jest po elementach rubryki, więc osobno punktowany jest przypadek bazowy, osobno wywołanie zmniejszające problem i osobno złożenie wyniku. Kod uruchamiany jest w izolowanym środowisku, a zapis na kartce ocenia model wedle tej samej rubryki, z sumą punktów ograniczoną do liczby przewidzianej dla zadania. Ocenę możesz zgłosić do sprawdzenia, jeśli się z nią nie zgadzasz. Metodę opisuje strona o zasadach oceniania.

Sprawdź to na własnym zapisie: rozpisz dowolny algorytm rekurencyjny i zobacz, czy punkt zabrakł przy warunku stopu, przy zmniejszaniu argumentu, czy dopiero przy złożeniu wyników.