Rekurze
Rekurzivní programy
 Vytisknout studijní materiál

Funkce

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ě.

Množiny

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 ( );

}

Eliminace koncové rekurze

Ř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.

Geometrické útvary

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.

Rekurzivní algoritmy

Nalezení nejmenšího prvku pole

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).

Hanojské věže

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.