Rekurencja to technika rozwiązywania problemów, będąca alternatywą dla metody iteracyjnej. W podejściu rekurencyjnym funkcja rozwiązująca problem wywołuje samą siebie, aż do napotkania tzw. przypadku podstawowegoprzypadek podstawowyprzypadku podstawowego.

Przykładowe zadania maturalne

Zadanie 1

Oceń, czy przedstawione zdania są prawdziwe. Zaznacz P, jeśli zdanie jest prawdziwe, albo F – jeśli zdanie jest fałszywe.

Zadanie 1.1

Dana jest funkcja  określona wzorem rekurencyjnym:

f(1)=4
f(n+1)=11f(n)dlan1

Wtedy:

L.p

Funkcja

Czy prawda

Czy fałsz

1.

f(8)=13

P

F

2.

f(9)=34

P

F

3.

f(10)=4

P

F

4.

f(100)=-13

P

F

Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i pojawiło się na egzaminie maturalnym z informatyki w 2016 roku (poziom rozszerzony, egzamin w tzw. starej formule). Cały arkusz można znaleźć na stronie internetowej CKE.

Przykładowe rozwiązanie

To zadanie sprawdza umiejętności czytania i rozumienia algorytmów rekurencyjnych. Przypadkiem podstawowym jest tu wartość x = 1, dla której funkcja  zwraca wartość 4.

Przeanalizujmy działanie tego algorytmu dla każdego z czterech przypadków.

Przypadek 1

f(8)=11f(7)
f(7)=11f(6)
f(6)=11f(5)
f(5)=11f(4)
f(4)=11f(3)
f(3)=11f(2)
f(2)=11f(1)
f(1)=4
f(2)=114=13=13
f(3)=11(13)=1113=34
f(4)=1134=114=4
f(5)=114=13=13
f(6)=11(13)=1113=34
f(7)=1134=114=4
f(8)=114=13=13

Otrzymany wynik jest inny niż podany, więc odpowiedzią jest F.

Przypadek 2

f(9)=11(13)=1113=34

Otrzymany wynik jest taki sam jak podany, więc odpowiedzią jest P.

Przypadek 3

f(10)=1134=114=4

Otrzymany wynik jest taki sam jak podany, więc odpowiedzią jest P.

Przypadek 4

Tego przykładu nie będziemy rozpisywać. Jest on zbyt obszerny, a rozwiązanie można podać o wiele szybciej. Zauważmy bowiem, że w wynikach powtarza się pewien schemat występowania liczb. Pierwszym wynikiem (dla ) jest , drugim -13, trzecim 34, a czwartym ponownie . Dla kolejnych wyników występuje ten sam schemat – każda wartość powtarza się co 3 wyniki.

Obliczmy zatem wartość . Pierwszym wynikiem jest liczba 4. Powtarza się ona co 3, więc taki wynik będzie kolejno dla , ,

Dochodzimy w ten sposób do funkcji , której wartość jest równa 4.

Otrzymany wynik jest inny niż podany, więc odpowiedzią jest F.

Drugi sposób: wystarczy obliczyć resztę z dzielenia . W omawianym przypadku x = 100, wynik dzielenia z resztą to x = 1 czyli f(x) = 4.

Schemat oceniania

I. Wiadomości i rozumienie

Zdający zna techniki algorytmiczne (rekurencja)

Schemat punktowania

1 pkt – za wszystkie cztery poprawne odpowiedzi

0 pkt – za odpowiedź niepełną lub błędną albo brak odpowiedzi

Poprawna odpowiedź

F, P, P, F

Schemat oceniania pochodzi z arkusza odpowiedzi wykorzystywanego podczas egzaminu maturalnego z informatyki w 2016 roku (na poziomie rozszerzonym). Cały arkusz można znaleźć na stronie internetowej Centralnej Komisji Egzaminacyjnej.

Praca domowa

Napisz implementację omówionej funkcji rekurencyjnejfunkcja rekurencyjnafunkcji rekurencyjnej w wybranym języku programowania.

Zadanie 2. Długość napisów binarnych (7 pkt.)

Treść zadania

Opisana poniżej funkcja rekurencyjna wyznacza dla liczby naturalnej n>0 długość napisu uzyskanego przez sklejenie binarnych reprezentacji liczb naturalnych od 1 do n-1.

Funkcja sklej(n)

Krok 1. Jeśli n=1, to podaj 0 jako wynik i zakończ działanie.

Krok 2. Jeśli n parzysta, to wynikiem jest n-1+2·sklej(n:2).

Krok 3. Jeśli n jest nieparzysta, to wynikiem jest n-1+sklej((n-1):2)+sklej((n+1):2).

b) Uzupełnij tabelę, podając wartości funkcji sklej dla wskazanych argumentów.

n

sklej(n)

1

0

2

1

3

4

5

6

Zadanie zostało opracowane przez Centralną Komisję Egzaminacyjną i pojawiło się na egzaminie maturalnym z informatyki w 2011 roku (poziom rozszerzony). Cały arkusz można znaleźć na stronie internetowej CKE.

Rozwiązanie podpunktu a) tego zadania zostało omówione w sekcji „Prezentacja multimedialna”.

Przykładowe rozwiązanie:

Obliczmy kolejne wartości podane w tabeli.

sklej(3)=31+sklej((31)2)+sklej((3+1)2)=
=2+sklej(1)+sklej(2)=2+0+1=3
sklej(4)=41+2·sklej(42)=3+2·sklej(2)=
=3+2·1=3+2=5
sklej(5)=51+sklej((51)2)+sklej((5+1)2)=
4+sklej(2)+sklej(3)=4+1+3=8
sklej(6)=61+2·sklej(62)=5+2·sklej(3)=
=5+2·3=5+6=11

Schemat oceniania

Korzystanie z informacji

Obliczenie kolejnych wartości funkcji dla wskazanych argumentów

Poprawna odpowiedź

n

sklej(n)

1

0

2

1

3

3

4

5

6

11 

2 pkt – za poprawne uzupełnienie wartości funkcji w tabeli

1 pkt – za uzupełnienie wartości funkcji w tabeli z jednym błędem

0 pkt – za wypełnioną tabelę z więcej niż jednym błędem albo brak odpowiedzi

Schemat oceniania pochodzi z arkusza odpowiedzi wykorzystywanego podczas egzaminu maturalnego z informatyki w 2011 roku (na poziomie rozszerzonym). Cały arkusz można znaleźć na stronie internetowej Centralnej Komisji Egzaminacyjnej.

Zwróćmy uwagę na schemat oceniania w tym zadaniu. Za prawidłowo wypełnioną tabelę uzyskamy 2 punkty. Gdy jedna z wartości będzie błędna, otrzymamy 1 punkt. Z tego powodu zawsze warto sprawdzić poprawność otrzymywanych wyników.

Słownik

funkcja rekurencyjna
funkcja rekurencyjna

funkcja odwołująca się do samej siebie w celu rozwiązania problemu aż do napotkania przypadku podstawowego

przypadek podstawowy
przypadek podstawowy

przypadek, w którym funkcja rekurencyjna zwraca konkretną wartość, a nie wywołanie samej siebie