Co to jest wzór rekurencyjny? Wyjaśnienie i przykłady
Wzór rekurencyjny to sposób definiowania ciągu, w którym kolejny wyraz oblicza się na podstawie jednego lub kilku wyrazów poprzednich. Aby taki zapis działał, trzeba podać zarówno regułę przejścia, jak i wyrazy początkowe.
Czym jest wzór rekurencyjny?
Ciąg liczbowy można opisać na różne sposoby. Wzór rekurencyjny działa jak instrukcja budowania kolejnych wyrazów. Nie oblicza od razu wyrazu o numerze n na podstawie samego n, lecz mówi, jak przejść od znanych wyrazów do następnego.
Można porównać to do budowania wieży z klocków. Najpierw trzeba postawić pierwszy klocek, a każdy kolejny układa się na poprzednim. W ciągu rekurencyjnym punktem startowym jest wyraz początkowy, a wzór określa sposób tworzenia dalszych wyrazów.
Przykładowy zapis
a1 = 2, an = an−1 + 3
oznacza, że pierwszy wyraz ma wartość 2, a każdy następny powstaje przez dodanie 3 do wyrazu poprzedniego.
Co musi zawierać wzór rekurencyjny?
Poprawna definicja rekurencyjna ciągu składa się z dwóch elementów:
- Wyrazy początkowe – określają punkt startowy, na przykład a1 = 2. Bez nich nie wiadomo, od czego rozpocząć obliczenia.
- Relacja rekurencyjna – opisuje, jak wyznaczyć kolejny wyraz na podstawie poprzedniego lub kilku wcześniejszych, na przykład an = an−1 + 3.
Jeżeli kolejny wyraz zależy od dwóch poprzednich, trzeba podać dwa wyrazy początkowe. Tak jest między innymi w ciągu Fibonacciego, gdzie każdy wyraz, począwszy od trzeciego, jest sumą dwóch wcześniejszych:
F0 = 0, F1 = 1, Fn = Fn−1 + Fn−2.
Jak obliczać wyrazy ciągu rekurencyjnego?
Rozważmy ciąg zdefiniowany następująco:
a1 = 2, an = an−1 + 3.
Aby znaleźć kolejne wyrazy, zawsze korzystamy z wartości obliczonej krok wcześniej:
- Wyraz pierwszy jest podany w definicji: a1 = 2.
- Wyraz drugi obliczamy ze wzoru: a2 = a1 + 3 = 2 + 3 = 5.
- Wyraz trzeci wyznaczamy na podstawie drugiego: a3 = a2 + 3 = 5 + 3 = 8.
- Wyraz czwarty obliczamy z użyciem trzeciego: a4 = a3 + 3 = 8 + 3 = 11.
Początkowe wyrazy tego ciągu to więc:
2, 5, 8, 11, …
Mechanizm jest zawsze taki sam. Najpierw odczytujesz wyraz początkowy, potem podstawiasz go do relacji rekurencyjnej i otrzymujesz następny wyraz. Ten nowy wynik staje się podstawą kolejnego obliczenia.
Wzór rekurencyjny a wzór ogólny
Wzór ogólny, nazywany też jawnym, pozwala obliczyć dowolny wyraz bez wyznaczania wszystkich wcześniejszych. Dla ciągu z przykładu wzór ogólny ma postać an = 3n − 1. Dzięki niemu od razu otrzymujemy na przykład a10 = 29.
Oba zapisy opisują ten sam ciąg, ale służą nieco innym celom:
| Cecha | Wzór rekurencyjny | Wzór ogólny |
|---|---|---|
| Sposób wyznaczania wyrazu | Na podstawie wyrazu lub wyrazów poprzednich | Na podstawie numeru wyrazu n |
| Wygoda dla dużych indeksów | Zwykle wymaga obliczenia wcześniejszych wyrazów | Pozwala obliczyć wybrany wyraz bezpośrednio |
| Łatwość zapisu | Często łatwo opisać regułę przejścia | Nie zawsze łatwo go wyprowadzić |
Wzór rekurencyjny jest więc wygodny, gdy chcemy opisać sam proces tworzenia ciągu. Wzór ogólny lepiej sprawdza się wtedy, gdy interesuje nas konkretny, odległy wyraz.
Po co stosuje się wzory rekurencyjne?
Rekurencja dobrze opisuje sytuacje, w których każdy etap wynika bezpośrednio z wcześniejszego. Dlatego stosuje się ją między innymi do opisu ciągu Fibonacciego, ciągów arytmetycznych i geometrycznych oraz innych ciągów, dla których naturalna jest reguła przejścia.
Najważniejsze zalety i ograniczenia takiego zapisu to:
- Intuicyjność – łatwo pokazać, jak powstaje następny wyraz.
- Prosty opis zależności – nie trzeba od razu znać wzoru jawnego.
- Konieczność znajomości punktu startowego – bez wyrazów początkowych obliczenia nie mogą się rozpocząć.
- Mniejsza wygoda przy dużych indeksach – aby znaleźć odległy wyraz, często trzeba wyznaczyć wiele wcześniejszych.
Najprościej zapamiętać, że wzór rekurencyjny jest przepisem na kolejny krok. Podajesz początek ciągu, stosujesz regułę do poprzednich wyrazów i w ten sposób budujesz następne wartości.
