Uvedené definici faktoriálu v předcházejícím článku odpovídá rekurzivní metoda f( ) ve třídě Faktorial na obr..
Jaký je čas výpočtu rekurzivní metody f( )? Obvyklou analýzou zjistíme, že čas výpočtu je
T(n) = cpor pro n ≤ 1
T(n) = cpor + cnas + T(n-1) pro n > 1
kde cpor je čas porovnání n > 1 a cnas je čas násobení. Postupným rozepsáním je
T(n) = cpor + cnas + T(n-1) = cpor + cnas + (cpor + cnas + T(n-2)) =
cpor + cnas + (cpor + cnas + ... + (cpor + cnas + T(1)) =
(n-1) (cnas + cpor ) + cpor = n cpor + (n-1) cnas
Čas výpočtu tedy je O(n). Uvedený postup je obecný, ale součet na pravé straně nebývá tak jednoduše vyčíslitelný jako v tomto případě.
Rekurze je elegantním vyjádřením výpočtu, ale rekurzivní volání metody je časově i paměťově náročné. Její přímočaré použití může být velice nevhodné.
Fibonacciho čísla jsou definovány rekurentními vztahy
F0 = 0,
F1 = 1,
Fn = Fn-1 + Fn-2 pro n ≥ 2
a tvoří následující posloupnost
0, 1, 1, 2, 3, 5, 8, …
Použití rekurze na jejich výpočet vede na rekurzivní metodu
static int fib(int n) {
if (n < 1) return 0;
if (n == 1) return 1;
return fib(n-1) + fib(n-2);
}
Rekurzivní volání pro F6 = 8 jsou na obr.. Počet rekurzivních volání pro výpočet Fn postupně je
F2 : 2
F3: 2 + 1 = 3
F4: (2 + 1) + (2) = 5
F5: (2 + 1 + 2) + (2 + 1) = 8
…
kde v závorkách je vyjádřen počet volání pro Fn-1 a Fn-2 . Indukcí, lze ukázat, že počet rekurzivních volání pro výpočet Fn je Fn+1. Zůstává vyjádřit Fn pomocí n. Analýzou Fibonacciho čísel lze ukázat, že hodnota Fn je φn/√5 zaokrouhlená na celé číslo, kde φ je zlatý poměr 1.618… . Počet rekurzivních volání pro uvedený výpočet Fibonacciho čísel tedy roste exponenciálně.
Rekurzivní definice hodnot datového typu umožňuje rekurzivní vyjádření práce s těmito hodnotami.
Častým úkolem je průchod všemi prvky datové struktury. V případě seznamu, jeho přímý průchod s tiskem hodnot procházených prvků můžeme napsat
void pruchod(Prvek x) {
if (x == null)
return;
x.tiskPrvku( );
pruchod(x.dalsi);
}
Tisk prvků seznamu v obráceném pořadí, tedy obrácený průchod seznamem, můžeme rekurzivně napsat
void pruchodR(Prvek x) {
if (x == null)
return;
pruchodR(x.dalsi);
x.tiskPrvku ( );
}
Řekli jsme již, že rekurzivní volání je náročná operace. V případě rekurzivního výpočtu faktoriálu a přímého průchodu seznamem bylo rekurzivní volání metody poslední akcí. Takovou situaci nazýváme koncová rekurze.
Obecně, je-li posledním krokem volání m(x) rekurzivní metody m( ), volání m(y), můžeme volání m(y) nahradit přiřazením x = y a opakovaným výpočtem metody m( ). Opakování skončí dosáhnutím základního případu. Tímto postupem převedeme rekurzivní algoritmus na iterační.
Program pro faktoriál lze pak přímočaře přepsat tak, jak je uvedeno na obr.. V případě přímého průchodu seznamem dostaneme cyklus metody tiskSeznamu( ) třídy Seznam z článku 3.3, obr.
.
Poznamenejme, že metoda pruchodR není takto přímočaře transformovatelná na iterační program.
Dále zkoumejme programové vyjádření kreslení Hilbertových křivek. Označíme-li spojované čtyři části A, B, C, D můžeme nakreslit Hilbertovu křivku Hi voláním metody A(i), kde šipky vyjadřují samotné kreslení spojování čtveřice křivek nižší úrovně. Pro i = 0 kreslení přestane (základní případ, kdy Hilbertova křivka H0 je bod), právě tak jako v programu Pisnicka po x opakováních program skončí prázdným řetězcem.. Schema metody volání metody A(i) je následující
A(i) ≡ if (i > 0) {
D(i-1) ← A(i-1) ↓ A(i-1) → B(i-1)
}
Stručně ho zapíšeme ve tvaru
A ≡ D ← A ↓ A → B
a dále
B ≡ C ↑ B → B ↓ A
C ≡ B → C ↑ C ← D
D ≡ A ↓ D ← D ↑ C
V tomto schématu metoda A nevolá jenom sama sebe, nýbrž i metody D a B, které opět volají metodu A. Říkáme, že v takovém případě jde o nepřímou rekurzi, na rozdíl od situace, kdy metoda volá sama sebe, kdy mluvíme o rekurzi přímé.
Program pro kreslení Hilbertových křivek je na obr. a
. Na obr.
jsou metody pro kreslení spojování křivek. Okamžitá pozice na ploše je dána souřadnicemi x,y a metoda drawLine( ) třídy Graphics vykreslí úsečku mezi tímto bodem a novou pozicí, která je určena podle "směru" úsečky. Její délka je daná hodnotou proměnné h. Na obr.
jsou metody a( ), b( ), c( ), d( ) implementující uvedené rekurzivní schéma a metoda paint( ), která na plochu nakreslí n Hilbertových křivek H1, ..., Hn. Strana křivky H1 má délku h0, přičemž požadujeme, aby h0 = 2k, n ≤ k. Pomocí metod getWidth( ) a getHeight( ) získáme velikost plochy, nalezneme její střed a vzhledem k němu určíme začáteční bod kreslení x0,y0 pro hilbertovu křivku Hi , i = 1, 2, ..., n a voláme metodu a(i, ...). Začátek souřadnicového systému je přitom v levém horním rohu. Poznamenejme, že šířka (a tím i výška) křivky H1 je dána konstantou h0. Šířka křivky H1 je (2*1 + 1)h0/2 = h0 + h0 /2, šířka křivky H2 je (2*3 + 1)h0 /4 = h0 + h0 /2 + h0 /4 atd. Indukcí můžeme vyjádřit velikost křivky Hn ve tvaru (1 + 1/2 + 1/4 + ... + (1/2)n)h0, což nám umožňuje pro dané n a h0 zvolit velikost kreslící plochy. Navíc vidíme, že volba velikosti kreslící plochy 2h0 postačuje pro zobrazení Hilbertových křivek pro jakékoliv n. Křivky H1, ..., H5 vykreslené uvedeným programem jsou na obr.
.
Jistě jste si všimli, že program neobsahuje metodu main( ). Odpovídající metoda main( ) se nachází v jiné třídě, ve které se vytvoří okno potřebných rozměrů pro zobrazení objektu třídy Hilbert. Podrobnosti o potřebném grafickém uživatelském prostředí Javy lze najít v opisu AWT - Abstract Windowing Toolkit.
Program pro nalezení nejmenšího prvku pole algoritmem uvedeným v předcházejícím článku je na obr.. Rekurzivní algoritmus je vyjádřen metodou min( ). Myšlenka je rozdělení problému na části a vyjádřit řešení problému pomocí řešení jeho častí, v našem případě je to menší z minima dvou častí pole.
Obecně rekurzivní metoda rozdělí pole (problém) o velikosti n na dvě části o velikostech m a n-m. Celkový počet operací porovnání potom je:
T(n) = T(m) + T(n-m) + 1 pro n ≥ 1 a T(1) = 0
Řešením je T(n) = n -1.
Důkaz provedeme indukcí:
T(1) = 1 - 1 = 0
je-li pro k < n T(k) = k - 1 je T(n) = (m - 1) + (n - m - 1) + 1 = n - 1
Čas výpočtu je tedy O(n).
Program vyjadřující algoritmus řešení problému Hanojských věží, který jsme uvedli v předcházejícím článku je na obr.. Rekurzivní metoda prenesVez( ) volá sama sebe dvakrát. Jeli počet kotoučů věže n, nejprve přenese věž horních n-1 kotoučů na pomocnou tyč a po přenesení nejspodnějšího kotouče, věž z pomocné tyče (nyní parametr zdroj) přeneseme na cílovou tyč, přičemž roli pomocné tyče hraje původní zdrojová tyč.
Počet přenosů kotoučů pro velikost věže n je:
T(n) = 2T(n-1) + 1 pro n ≥ 2 a T(1) = 1
Řešením je T(n) = 2n - 1.
Důkaz opět provedeme indukcí:
T(1) = 21 - 1 = 1
je-li pro k < n T(k) = 2k - 1 je T(n) = 2(2n-1 - 1) + 1 = 2n - 1.
Čas výpočtu tedy roste exponenciálně s velikostí věže.