Przeczytaj

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 $f$ określona wzorem rekurencyjnym:

f (1) = 4

f (n + 1) = \frac{1}{1 - f (n)} dla n \geq 1

Wtedy:

L.p	Funkcja	Czy prawda	Czy fałsz
1.	$f (8) = \frac{1}{3}$	P	F
2.	$f (9) = \frac{3}{4}$	P	F
3.	$f (10) = 4$	P	F
4.	$f (100) = - \frac{1}{3}$	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 $f$ zwraca wartość 4.

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

Przypadek 1: $f(8)$

f (8) = \frac{1}{1 - f (7)}

f (7) = \frac{1}{1 - f (6)}

f (6) = \frac{1}{1 - f (5)}

f (5) = \frac{1}{1 - f (4)}

f (4) = \frac{1}{1 - f (3)}

f (3) = \frac{1}{1 - f (2)}

f (2) = \frac{1}{1 - f (1)}

f (1) = 4

f (2) = \frac{1}{1 - 4} = \frac{1}{- 3} = - \frac{1}{3}

f (3) = \frac{1}{1 - (- \frac{1}{3})} = \frac{1}{1 \frac{1}{3}} = \frac{3}{4}

f (4) = \frac{1}{1 - \frac{3}{4}} = \frac{1}{\frac{1}{4}} = 4

f (5) = \frac{1}{1 - 4} = \frac{1}{- 3} = - \frac{1}{3}

f (6) = \frac{1}{1 - (- \frac{1}{3})} = \frac{1}{1 \frac{1}{3}} = \frac{3}{4}

f (7) = \frac{1}{1 - \frac{3}{4}} = \frac{1}{\frac{1}{4}} = 4

f (8) = \frac{1}{1 - 4} = \frac{1}{- 3} = - \frac{1}{3}

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

Przypadek 2: $f(9)$

f (9) = \frac{1}{1 - (- \frac{1}{3})} = \frac{1}{1 \frac{1}{3}} = \frac{3}{4}

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

Przypadek 3: $f(10)$

f (10) = \frac{1}{1 - \frac{3}{4}} = \frac{1}{\frac{1}{4}} = 4

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

Przypadek 4: $f(100)$

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 $f(1)$ ) jest $4$ , drugim $- \frac{1}{3}$ , trzecim $\frac{3}{4}$ , a czwartym ponownie $4$ . Dla kolejnych wyników występuje ten sam schemat – każda wartość powtarza się co 3 wyniki.

Obliczmy zatem wartość $f(100)$ . Pierwszym wynikiem jest liczba 4. Powtarza się ona co 3, więc taki wynik będzie kolejno dla $f(4)$ , $f(7)$ , $f(10), ..., f(100).$

Dochodzimy w ten sposób do funkcji $f(100)$ , 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 $x = x \text{ mod } 3$ . 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 $s k l e j (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 \cdot s k l e j (n : 2)$ .

Krok 3. Jeśli $n$ jest nieparzysta, to wynikiem jest $n - 1 + s k l e j ((n - 1) : 2) + s k l e j ((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.

s k l e j (3) = 3 - 1 + s k l e j (\frac{(3 - 1)}{2}) + s k l e j (\frac{(3 + 1)}{2}) =

= 2 + s k l e j (1) + s k l e j (2) = 2 + 0 + 1 = 3

s k l e j (4) = 4 - 1 + 2 \cdot s k l e j (\frac{4}{2}) = 3 + 2 \cdot s k l e j (2) =

= 3 + 2 \cdot 1 = 3 + 2 = 5

s k l e j (5) = 5 - 1 + s k l e j (\frac{(5 - 1)}{2}) + s k l e j (\frac{(5 + 1)}{2}) =

4 + s k l e j (2) + s k l e j (3) = 4 + 1 + 3 = 8

s k l e j (6) = 6 - 1 + 2 \cdot s k l e j (\frac{6}{2}) = 5 + 2 \cdot s k l e j (3) =

= 5 + 2 \cdot 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
5	8
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 odwołująca się do samej siebie w celu rozwiązania problemu aż do napotkania przypadku podstawowego

przypadek podstawowy

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

Wprowadzenie

Prezentacja multimedialna

Przykładowe zadania maturalne

Zadanie 1

Zadanie 1.1

Przykładowe rozwiązanie

Schemat oceniania

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

Treść zadania

Przykładowe rozwiązanie:

Schemat oceniania

Słownik