Polowanie na czarownice - czyli zabawy z rekurencją (część 1)

Rozpocznijmy branżowym humorem

Okres średniowiecza, kobieta winna uprawiania magii, kara straszna - spalenie na stosie! Nadszedł dzień, tłum gawiedzi, czarownica na stosie, płomienie, wiedźma krzyczy - więcej drewna! Więcej drewna! Tłum zdziwiony, mimo wszystko spełnia ostatnie życzenie opętanej. Wiedźma nie przerywa - jeszcze więcej drewna! Więcej drewna! Z oddali dobiega nagły i stanowczy sprzeciw - STOP! Czarownica chce przepełnić stos!

🙂

Czym jest rekurencja?

Zazwyczaj o rekurencji myślimy jako o procesie podziału zadania na mniejsze, następnie podziału na jeszcze mniejsze, i jeszcze mniejsze ... dochodząc do zadań, dla których rozwiązanie jest znane. Od tego momentu zaczyna się składanie "mniejszych" rozwiązań w "większe", następnie tych większych w jeszcze większe, ... i w jeszcze większe ... kończąc na rozwiązaniu zadania początkowego. Dla przykładu zapiszmy funkcję n! w postaci rekurencyjnej.

n!=\begin{cases}n\cdot(n-1)!&\text{dla}\quad n>0\\1,&\text{dla}\quad n=0\end{cases}

W celu zobrazowania reprezentacja powyższego podana w mXparser:

/* Definicja funkcji rekurencyjnej */
Function silnia = new Function("s(n) = if( n>0, n*s(n-1), 1 )");

/* Obliczenia i wyświetlenie wyniku */
System.out.println( "n = 0, s(n) = " + silnia.calculate(0) );
System.out.println( "n = 1, s(n) = " + silnia.calculate(1) );
System.out.println( "n = 2, s(n) = " + silnia.calculate(2) );
System.out.println( "n = 3, s(n) = " + silnia.calculate(3) );
System.out.println( "n = 4, s(n) = " + silnia.calculate(4) );
System.out.println( "n = 5, s(n) = " + silnia.calculate(5) );

+ wynik:

n = 0, s(n) = 1.0
n = 1, s(n) = 1.0
n = 2, s(n) = 2.0
n = 3, s(n) = 6.0
n = 4, s(n) = 24.0
n = 5, s(n) = 120.0

Wynik jest zgodny z oczekiwanym. Innym przykład rekurencji to iterowany operator sumowania, niech

A_n=a_1+a_2+\ldots+a_n=\sum_{i=1}^n a_i

Łatwo zauważyć, że

A_n=\begin{cases}a_n+A_{n-1},&\text{dla}\quad n>1\\a_1,&\text{dla}\quad n=1\end{cases}

Jak więc widzicie, rekurencja jest powszechna, często będąc nieco innym sposobem patrzenia na iteracje.

Formalna definicja rekurencji

O rekurencji mówimy jeśli metoda (funkcja, zachowanie, obiekt) może być opisana przez:

  1. elementy bazowe / rozwiązania bazowe;
  2. zestaw reguł, które redukuję (sprowadzają) każdy inny przypadek do (w kierunku) elementów bazowych.

Rekurencja
Powyższe określenie jest szerokie, ale takie być musi, bo i typów rekurencji jest wiele.

Rekurencja jako złożenie funkcji

Jednym (ale nie jedynym) sposobem zapisu ogólnych równań rekurencyjnych jest złożenie funkcji:

f_n=\begin{cases}F\big(f_{n-1},f_{n-2},\ldots,f_{n-k}\big)&\text{dla}\quad n>k\\f_1,f_2,\ldots,f_k&\text{el. baz. dla}\quad n<=k\end{cases}

Dobrą ilustracją powyższego jest ciąg Fibonacciego:

f_n=\begin{cases}0&\text{dla}\quad n=0\\1&\text{dla}\quad n=1\\f_{n-1}+f_{n-2}&\text{dla}\quad n>1\end{cases}

Zapiszmy ciąg Fibonacciego w mXparser:

/* Definicja funkcji rekurencyjnej */
Function fib = new Function("fib(n) = if( n>1, fib(n-1)+fib(n-2), if(n=1,1,0) )");

/* Obliczenia i wyświetlenie wyniku */
System.out.println( "fib(0) = " + fib.calculate(0) );
System.out.println( "fib(1) = " + fib.calculate(1) );
System.out.println( "fib(2) = " + fib.calculate(2) );
System.out.println( "fib(3) = " + fib.calculate(3) );
System.out.println( "fib(4) = " + fib.calculate(4) );
System.out.println( "fib(5) = " + fib.calculate(5) );

+ rezultat:

fib(0) = 0.0
fib(1) = 1.0
fib(2) = 1.0
fib(3) = 2.0
fib(4) = 3.0
fib(5) = 5.0

Rekurencja w roli pętli "For"

Podane wyżej przykłady zapisów rekurencyjnych (n!, suma n-pierwszych wyrazów ciągu, ciąg Fibonacciego) są tak naprawdę rekurencyjną realizacją pętli "for" - znamy przecież dokładnie liczbę niezbędnych operacji do wykonania, a i same operacje są raczej łatwe oraz czytelne - zatem zagnieżdżenie ich w pętli "for" nie powinno spowodować utraty przejrzystości kodu.

Poszukiwanie rozwiązania - czyli rekurencja w roli pętli "While/Until"

W metodach numerycznych często stosuje się strategie rekurencyjne - w takiej sytuacji, będąc w kroku n, weryfikujemy czy propozycja rozwiązania n spełnia kryterium stopu (np. jakość oszacowania), jeśli tak - kończymy z rozwiązaniem n, jeśli nie - przechodzimy do badania propozycji rozwiązania n+1. Procedurę rozpoczynamy od kroku 0 (zerowego).

Przykład: znając definicję silni chcemy znaleźć pierwsze n, dla którego n! >= 100 - takie zadanie formalnie możemy zapisać jako:

S_n=\begin{cases}S_{n+1},&\text{dla}\quad n!<100\\n,&\text{dla}\quad n!>=100\end{cases}

n_{100} = S(0)

Reprezentacja w mXparser:

/* Definicja funkcji rekurencyjnej */
Function S = new Function("S(n) = if( n! < 100, S(n+1), n )"); /* Obliczenia i wyświetlenie wyniku */ System.out.println( "Pierwsze n, że n! >= 100 to n = " + S.calculate(0) );

+ wynik:

Pierwsze n, że n! >= 100 to n = 5.0

Rekurencja bezpośrednia

Wszystkie omawiane wyżej typy rekurencji polegają na wywołaniu z ciała funkcji "siebie samej", dlatego należą do bardziej ogólnej klasy nazywanej rekurencją bezpośrednią.

Wydajność

Implementacje na bazie rekurencji są bardzo czytelne, o często minimalnym rozmiarze kodu. Jednak coś za coś - tracimy bardzo dużo na złożoności obliczeniowej (powtarzane operacje, dzielenie zadań, operacje na stosie) oraz wymogach pamięci (głównie struktura stosu) - to właśnie dlatego czarownica błagała o drewno - licząc na przerwanie procesu z tytułu przepełnienia stosu 🙂

Cdn 🙂

Pozdrowienia,

Mariusz Gromada

BTW: jeśli planujecie uruchamiać kody mXparsera nie zapomnijcie o dodaniu

import org.mariuszgromada.math.mxparser.*;

Zobacz również:

  1. Prędkość ucieczki do nieskończoności - czyli zabawy z rekurencją (część 2)
  2. Naiwny test pierwszości - czyli zabawy z rekurencją (część 3)
  3. Rekurencja pośrednia - czyli zabawy z rekurencją (część 4)

 

Views All Time
Views All Time
562
Views Today
Views Today
1

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *