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 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\left(1\right)=4$

$f(n+1)=\frac{1}{1-f\left(n\right)}dlan\ge 1$

Wtedy:

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\left(8\right)=\frac{1}{1-f\left(7\right)}$

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

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

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

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

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

$f\left(2\right)=\frac{1}{1-f\left(1\right)}$

$f\left(1\right)=4$

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

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

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

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

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

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

$f\left(8\right)=\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\left(9\right)=\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\left(10\right)=\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\left(x\right) = 4$.

Schemat oceniania

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

Słownik