Rekurencja

strict warning: Only variables should be passed by reference in /usr/share/drupal6/modules/book/book.module on line 559.

Definicje rekurencyjne


Definicja rekurencyjna (indukcyjna):

  • nieformalnie - taka definicja, która odwołuje się do samej siebie - ale trzeba tu uważać, by odwołanie było do instancji o mniejszej komplikacji,
  • zwykle chodzi o ciąg \( \langle a_0, a_1, a_2, a_3, \ldots \rangle \), - dla którego przepis na element \( a_n \) wykorzystuje jakieś poprzednie elementy: \( a_{n-1}, a_{n-2}, \ldots \) itp.,
  • początkowy element (lub kilka początkowych) muszą być zadane konkretnie - żeby było od czego zacząć,
  • zwykle definicja rekurencyjna odwołuje się do jednego lub kilku poprzednich elementów, ale może też odwoływać się do wszystkich poprzednich.

Przykład

Silnia liczby \( n \) (zapisywana jako \( n! \)) to iloczyn kolejnych liczb naturalnych od \( 1 \) do \( n \), czyli

\( n!=n(n-1)\cdot\ldots\cdot2\cdot1. \)

Przyjmuje się że \( 0!=1 \). Oto wartości silni dla kilku początkowych liczb naturalnych


\( \begin{array} {|c|c|c|c|c|c|c|c|c|c|c} \hline n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & \cdots \\ \hline n! & 1 & 1 & 2 & 6 & 24 & 120 & 720 & 5040 & 40320 & \cdots \\ \hline \end{array} \)

Ciąg \( 0!, 1!, 2!, 3!, 4!,\ldots \) aby mógł być precyzyjnie rozumiany np. przez komputer, powinien być zadany rekurencyjnie jako:

\( \begin{align*} s_0 & = 1 \\ s_{n} & = n \cdot s_{n-1} \quad dla \quad n\geq 1. \end{align*} \)

Ponieważ pierwszy wyraz jest zadany, to możemy kolejno obliczać:

\( \begin{align*} s_0 & = 1 \\ s_1 & = 1 \cdot s_{0} = 1 \cdot 1 = 1 \\ s_2 & = 2 \cdot s_{1} = 2 \cdot 1 = 2 \\ s_3 & = 3 \cdot s_{2} = 3 \cdot 2 = 6 \\ s_4 & = 4 \cdot s_{3} = 4 \cdot 6 = 24 \\ \ldots \end{align*} \)

Przykład

Jaki ciąg jest zdefiniowany poprzez małą modyfikację w definicji silni?

\( \begin{align*} s_0 & = 0 \\ s_{n} & = n \cdot s_{n-1}\quad {dla}\quad n\geq 1 \end{align*} \)

A co definiują następujące określenia:

\( \begin{align*} s_0 & =\frac{1}{2} \\ s_{n} & = n \cdot s_{n-1} \quad {dla}\quad n\geq 1 \end{align*} \)

oraz

\( \begin{align*} s_0 & = 1 \\ s_{n} & = n \cdot s_{n-2} \quad {dla}\quad n\geq 2. \end{align*} \)

W ostatnim przypadku widać, że ponieważ odwołanie jest dwa wyrazy wstecz, to już wyliczenie pierwszego wyrazu \( s_1 \) staje się niemożliwe.

Ciąg arytmetyczny

Przykład

W ciągu zadanym poprzez równania:

\( \begin{align*} s_0 & = 0 \\ s_{n} & = s_{n-1}+2 \quad {dla}\quad n\geq 1 \end{align*} \)

łatwo rozpoznać kolejne liczby parzyste:

\( s_n = 2n. \)

Ogólnie ciąg zadany poprzez ustalenie \( a_0 \) oraz

\( a_n = a_{n-1} + r \)

to tzw. ciąg arytmetyczny.
Jego \( n \)-ty wyraz dany jest wzorem:

\( a_n = a_0 + n\cdot r. \)

Aby to uzasadnić, pokazujemy indukcyjnie, że:

\( a_0 + 0\cdot r = a_0 \quad\textrm{jest rzeczywiście zerowym wyrazem ciągu} \)

oraz

\( a_0 + n\cdot r = (a_0 + (n-1)r) + r = a_{n-1}+r = a_n \)

Ciąg geometryczny

Przykład

W ciągu zadanym poprzez równania:

\( \begin{align*} s_0 & = 1 \\ s_{n} & = 2\cdot s_{n-1} \quad {dla}\quad n\geq 1 \end{align*} \)

łatwo rozpoznać kolejne potęgi liczby \( 2 \):


\( s_n = 2^n. \)

Ogólnie ciąg zadany poprzez ustalenie \( a_0 \) oraz zadanie

\( a_n = q\cdot a_{n-1} \)

to tzw. ciąg geometryczny.
Jego \( n \)-ty wyraz dany jest wzorem:

\( a_n = a_0 \cdot q^n. \)

Aby to uzasadnić, pokazujemy indukcyjnie, że:


\( a_0 \cdot q^0 = a_0 \cdot 1 = a_0 \quad\textrm{jest rzeczywiście zerowym wyrazem ciągu} \)

oraz

\( a_0 \cdot q^n = (a_0 \cdot q^{n-1})\cdot q = a_{n-1}\cdot q = a_n. \)

Wieże Hanoi

U zarania czasu Bóg umieścił 64 złote krążki na jednej z trzech diamentowych iglic tak, że krążki wyżej umieszczone miały mniejsze promienie.

Następnie Bóg polecił grupie mnichów przełożenie tych krążków na trzecią iglicę \( (C) \), ale tak by:

  • w jednym ruchu przenosić tylko jeden krążek,
  • krążek większy nigdy nie może leżeć na krążku mniejszym,
  • można posługiwać się iglicą \( B \).

Mnisi pracują od zarania dziejów dzień i noc ... .Ile czasu im to zajmie?

Wieże Hanoi - analiza

Przykład (E.Lucas, 1883)

By obliczyć ilość potrzebnych do wykonania ruchów, przeanalizujmy najpierw małe przypadki:
Łatwo zauważyć, że dla 1 krążka potrzebny jest jeden ruch: \( A \to C \)
Podobnie dla dwu krążków możemy postąpić: \( A \to B, \ \ A \to C, \ \ B \to C \)
Przy 3 krążkach postępujemy tak:

  • najpierw przenosimy dwa górne krążki na iglicę \( B \) posługując się iglicą \( C \):

\( A \to C, \ \ A \to B, \ \ C \to B \)

  • przenosimy największy krążek z \( A \) na \( C \):

\( A \to C \)

  • przenosimy krążki z \( B \) na \( C \) posługując się iglicą \( A \):

\( B \to A, \ \ B \to C, \ \ A \to C \)

co pokazuje, że potrzeba tu 7 ruchów.
Czy już wiesz jak rozwiązać to zadanie w ogólności (dla \( n \) krążków)?
Oznaczmy przez \( H_n \) liczbę ruchów potrzebnych do przeniesienia \( n \) krążków z jednej iglicy na drugą. Wiemy już, że:

\( \begin{align*} H_1 & = 1 \\ H_2 & =3 \\ H_3 & =7 \end{align*} \)

Aby przenieść \( n \) krążków z \( A \) na \( C \) możemy postąpić podobnie jak w przypadku 3 krążków, redukując zadanie do:

  • przenosimy \( n-1 \) górnych krążków na iglicę \( B \) posługując się iglicą \( C \) - potrzeba na to \( H_{n-1} \) ruchów
  • przenosimy największy krążek z \( A \) na \( C \) - to tylko jeden ruch
  • przenosimy \( n-1 \) krążków z \( B \) na \( C \) posługując się iglicą \( A \) - znów potrzeba na to \( H_{n-1} \) ruchów

A zatem

\( H_n = H_{n-1} +1 + H_{n-1} = 2\cdot H_{n-1} +1 \)

Ile wobec tego wynosi \( H_{64} \)?

Mamy więc równanie rekurencyjne

\( \begin{align*} H_1 & = 1 \\ H_{n} & = 2\cdot H_{n-1}+1 \quad \textrm{dla}\quad n\geq 2 \end{align*} \)

bardzo podobne do ciągu geometrycznego.
Możemy policzyć kilka jego wyrazów:


\( 1, \ \ 3, \ \ 7, \ \ 15, \ \ 31, \ \ 63, \ \ 127, \ldots \)

i rozpoznać w nim ciąg potęg dwójki zmniejszonych o 1.

Ale czy rzeczywiście \( H_n = 2^n -1 \)?

I znów, aby się upewnić, że nasze odgadnięcie było poprawne, sprawdzamy indukcyjnie, że

\( 2 \cdot H_{n-1} + 1= 2 \cdot (2^{n-1}-1) +1 = 2\cdot 2^{n-1} -2 +1 = 2^n -1 = H_n \)

co oznacza, że rzeczywiście ciąg \( 2^n-1 \) spełnia równanie rekurencyjne, którym zadany jest ciąg \( H_n \).
A wiec \( H_{64} =2^{64}-1 \approx 100~000~000~000~000~000~000 \), co przy przenoszeniu jednego krążka na sekundę zajmie ponad \( 3~000~000~000~000 \) lat, a przenosząc te krążki "komputerem" 3GHz potrzeba będzie... i tak ponad tysiąc lat!

Przykład

Znajdź postać zwartą zadanych ciągów rozwijając równanie rekurencyjne:

\( \begin{align*} a_0 & =2, \\ a_{n+1} & =a_n^2. \end{align*} \)

Wskazówka:
Policz kilka pierwszych wyrazów ciągu:

\( a_n = a_{n-1}^2=a_{n-2}^4=a_{n-3}^8= \ldots =a_0^{2^n}=2^{2^n}. \)

Przykład

Jaka jest największa możliwa liczba \( l_n \) obszarów wyznaczonych przez \( n \) prostych na płaszczyźnie?

Sprawdźmy najpierw kilka pierwszych wartości.

  • Gdy nie ma żadnej prostej obszar jest jeden.
  • Jedna prosta tworzy zawsze dwa różne obszary.
  • Kładąc drugą prostą (byle nie równoległą do pierwszej) otrzymujemy \( 4 \) obszary.

W tym momencie możemy pokusić się o zgadywanie i przypuścić, że \( l_n=2^n \). Jednakże

  • Dla trzech prostych jest to \( 7 \).

Zauważmy, że nowa prosta zwiększa ilość obszarów o \( k \) jeśli przecina dokładnie \( k-1 \) z poprzednich prostych i to w nowych punktach przecięć. Z drugiej strony dwie proste mogą się przeciąć w co najwyżej jednym punkcie i przecinają się o ile nie są równolegle. Widzimy zatem, że najwięcej obszarów dostaniemy kładąc kolejne proste w ten sposób aby żadne dwie nie były równoległe i żadne trzy nie przecinały się w jednym punkcie. Otrzymujemy następujące równanie rekurencyjne:

\( \begin{align*} l_0 & =1, \\ l_{n+1} & =l_n+n. \end{align*} \)

Ponownie rozwiążemy równanie rozwijając je:

\( \begin{align*} l_n & =l_{n-1}+n=l_{n-2}+(n-1)+n=l_{n-3}+(n-2)+(n-1)+n=\ldots \\ & =l_0+1+2+\ldots+n=1+\frac{n(n+1)}{2}, \end{align*} \)

gdzie ostatnia równość wynika z - już udowodnionego - wzoru na sumę kolejnych liczb naturalnych.