Princip rekurze a iterace

2007-12-29 14:13 napsal Lukáš Havrlant

Rekurze je procedura/funkce, která volá sebe sama ve svěm těle. Další rozlišení bude následovat.

Rekurzivní procesy

V matematice známe funkce, které jsou definovány pomocí sebou samých. Nejtypičtější je samozřejmě faktoriál – n!. Faktoriál je definovaný nějak takhle: pokud je n menší nebo rovno jedné, je výsledek jedna. V opačném případě platí, že n! = n * (n – 1)! Vidíte tam tu hezkou rekurzi? Faktoriál n spočtete jako n krát faktoriál o jedna méně. Důležitá je ovšem ta hraniční (limitní) podmínka, že pokud je n jedna (nebo méně), je faktoriál jedna. Kdybychom tuto podmínku neměli, dostali bychom nekonečnou rekurzi, která by pro nás asi moc velký užitek neměla. Tohoto principu můžeme využít v programování. Ukázky budu psát v Céčku:

int fak(int n)
{
        if(n<=1)
        {
                return 1;
        }
        else
        {
                return (n*fak(n-1));
        }
}

Teď si trochu projdeme, co se vlastně v počítači stane a jakou má tahle funkce časovou složitost. Demonstrovat si to budeme na výpočtu příkladu fak(5). V tomto rekurzivním procesu nastanou dvě fáze – navíjení a odvíjení. Ve fázi navíjení se postupně volají jednotlivé faktoriály a nabalují se na sebe. V prvním kroku navíjecí fáze vzniká 5 * 4!. Ve druhém kroku 5 * 4 * 3! atd. Zde je důležité si uvědomit, že počítač si musí v každém kroku pamatovat předešlý výsledek, předešlé n. Když budu počítat faktoriál z milionu, musí mít počítač uloženo v paměti všech milion čísel, než dojde k jedničce (1 000 000, 999 999, 999 998, …).

Ve chvíli, kdy snížíme n na jedničku, navíjecí fáze se zastaví (dosáhli jsme limitní podmínky rekurze) a můžeme přistoupit k fázi odvíjení. Ta spočívá v aplikování násobení na mezivýpočty. Přehledně to ukazuje následující schéma:

|(fak 5)
| (fak 4)
| |(fak 3)
| | (fak 2)
| | |(fak 1)
| | |1
| | 2
| |6
| 24
|120

Nebo ještě přehledněji:

fak(5):
(5 * (fak(4)));
(5 * (4 *(fak(3)))));
(5 * (4 * (3 *(fak(2)))));
(5 * (4 * (3 * (2 *(fak(1)))));
(5 * (4 * (3 * (2 * (1)))));
(5 * (4 * (3 * (2))));
(5 * (4 * (6)));
(5 * (24));
(120);

Vidíme, že nejprve voláme proceduru fak a její argument postupně dekrementuje. To je fáze navíjení. Poté začíná samotný výpočetní proces – fáze odvíjení. Mezivýsledky se násobí a nakonec získáváme výsledek.

Teď něco ke složitosti. Časová složitost je poměrně jednoduchá, vždy provádíme n aplikací procedury fak, složitost je tedy lineární (ale nenechte se zmást lineární složitostí, faktoriál milionu stejně nespočítáte ;-)). Prostorová složitost (to je složitost, která nám říká, kolik spotřebujeme paměti během výpočtu) je také lineární, protože si vždy musíme pamatovat n čísel, která budeme ve fázi odvíjení násobit. V příkladu je to vidět v tomto řádku: (5 * (4 * (3 * (2 * (1))))); Počítač si musí vyhradit místo pro každé z těchto čísel a každé z těchto čísel si musí běhet výpočtu zapamatovat, aby je zde zase mohl z paměti vytáhnout a vypočítat výsledek.

Teď si ukážeme další příklad rekurzivní procedury a sice klasickou Fibonacciho posloupnost. Ta je definována nějak takhle:

n=0 -> fib(n)=0
n=1 -> fib(n)=1
jinak -> fib(n)=fib(n-1) + fib(n-2)

Neboli jde o součet dvou předchozích členů posloupnosti, přičemž posloupnost začíná čísly 0 a 1. Prvních pár členů vypadá takhle: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, … Proceduru, která počítá n-tý prvek téhle posloupnosti, napíšeme rekurzivně takto:

int fib(int n)
{
    switch(n)
    {
        case 0: return 0; break;
        case 1: return 1; break;
        default: return fib(n-2)+fib(n-1);
    }
}

Vypadá to poměrně jednoduše, striktně jsme se drželi definice. Tenhle postup je na první pohled správný, ale na ten druhý je samozřejmě špatně. Teď asi nastal čas, abychom si pověděli, jaký je rozdíl mezi lineárně rekurzivním procesem a stromově rekurzivním procesem. Lineárně rekurzivní procedura je procedura, která ve svém těle volá sebe sama nanejvýš jednou. Naopak stromově rekurzivní procedura volá sebe sama nejméně dvakrát. A to nám udělá strašný bordel ve složitosti.

Pokud volá procedura sebe sama pouze jednou, je to lineární složitost a počet prvků se plus minus rovná počtu aplikací procedury. To je v pořádku, tak to má být. Jestliže ovšem máme stromově rekurzivní proces, každá procedura volá sebe sama dvakrát (nebo vícekrát). Tedy v prvním kroku voláme původní proceduru dvakrát. V druhém kroku v každé nově vyvolané proceduře opět voláme další dvě procedury – celkem čtyři další procedury. V třetím kroku voláme dalších osm procedur, dále šestnáct procedur a tak dále. Dostáváme zřejmou složitost 2n.

A to je přesně případ Fibonacciho posloupnosti naprogramované stromově rekurzivním procesem. Prohlédněte si následující diagram zachycující, co se vlastně během aplikace té procedury děje:

|(fib 5)
| (fib 4)
| |(fib 3)
| | (fib 2)
| | |(fib 1)
| | |1
| | |(fib 0)
| | |0
| | 1
| | (fib 1)
| | 1
| |2
| |(fib 2)
| | (fib 1)
| | 1
| | (fib 0)
| | 0
| |1
| 3
| (fib 3)
| |(fib 2)
| | (fib 1)
| | 1
| | (fib 0)
| | 0
| |1
| |(fib 1)
| |1
| 2
|5

Jak vidíte, počítali jsme pátý člen a diagram je dlouhý jako týden před výplatou. Mimochodem si zde můžete všimnout, že fáze navíjení a odvíjení nemusí být v celém bloku celistvé a mohou se překrývat. Je evidentní, že tudy cesta nevede – zkuste si schválně u sebe doma spočítat třeba padesátý člen. Nejspíše se jen tak nedopočítáte. A jak teď z toho ven?

Iterativní procesy

Cesta vede přes lineárně iterativní procesy. O co jde? Ukázali jsme si, že stromově rekurzivní procedury, ve kterých voláme proceduru vícekrát než je zdrávo, nejsou vždy použitelné. Takže musíme srazit počet volání procedury na minimum, nejlépe na jedno volání. Což by se mohlo zdát jako problém, když i v definici Fibonacciho posloupnosti figuruje funkce fib dvakrát. Ale jde to.

V iterativních procesech si totiž předáváme mezivýpočty jako argumenty procedury. Nemusíme tedy volat dvakrát proceduru fib, stačí mít v této proceduře dva argumenty navíc, které budou sloužit k uchovávání předchozí dvou výsledků řady. Podívejme se na řešení:

int fib_iter(int n, int a=0, int b=1)
{
    if(n<=0)
    {
        return a;
    }
    else
    {
        fib_iter(n-1, b, a+b);
    }
}

Vystačili jsme si s jedním voláním procedury fib_iter a celá procedura je tak mnohem efektivnější. Vtip spočívá v tom, že si mezivýpočty posíláme v argumentech procedury. Hezky je to vidět hned v prvním kroku, kdy se a=0 a b=1. V dalším voláním procedury se do áčka uloží béčko, tedy jednička a do béčka součet a+b, tedy také jednička. V dalším kroku se do áčka zase uloží béčko, jednička a do béčka se uloží součet a+b, tedy dvojka. A tak dále a tak dále… Postupně také snižujeme n a až dojde nuly, vrátíme a, kde bude hodnota, kterou hledáme. Následující diagram to krásně zachycuje:

|(fib_iter 10 0 1)
|(fib_iter 9 1 1)
|(fib_iter 8 1 2)
|(fib_iter 7 2 3)
|(fib_iter 6 3 5)
|(fib_iter 5 5 8)
|(fib_iter 4 8 13)
|(fib_iter 3 13 21)
|(fib_iter 2 21 34)
|(fib_iter 1 34 55)
|(fib_iter 0 55 89)
|55

Teď si tento iterativní proces dále rozebereme. Jistě jste si všimli, že tenhle diagram je mírně odlišný od ostatních – chybí fáze odvíjení. Není totiž potřeba. U rekurzí jsme museli dospět do koncové podmínky a poté jsme mohli teprve vyhodnocovat výraz. Zde u iterativní verze po ukončení limitní podmínky máme výsledek okamžitě, netřeba nic odvíjet. Z toho vyplývá jedna důležitá vlastnost. Rekurze je v koncové pozici. Koncová pozice nastává v případě, kdy iterativně voláme procedury aniž bychom ji aplikovali s nějakou další operací. n * fak(n-1) není koncová pozice, protože je tam ještě ta operace násobení. fib_iter(10) je koncová pozice, protože se tam již jiná operace nenachází.

Jestliže je rekurzivní procedura v koncové pozici, jsme schopni provést optimalizaci na koncovou pozici. Když se nad tím zamyslíte, u rekurzí jsme si museli ve fázi navíjení pamatovat mezivýsledky, abychom je mohli aplikovat ve fázi odvíjení. Nic takového ovšem u lineárně iterativních procesů nemusíme provádět, protože zde fáze odvíjení odpadá. Klesá tedy prostorová složitost procedury – nemusíme si pamatovat n čísel, můžeme si dovolit přepisovat stále stejný chlíveček v paměti počítače. Když jsme rekurzivně počítali faktoriál ze sta, museli jsme mít vyhrazeno sto chlívečků na mezivýsledky 100, 99, 98, … U iterativní verze nám stačí jeden chlíveček, kde budeme postupně přepisovat 100, 9900, 970 200, … Z toho vyplývá, že prostorová složitost iterativních procedur v koncové pozici je konstatní. Časová složitost pochopitelně také klesá, to je vidět z diagramu, na lineární. Pomocí iterativní verze Fibonacciho posloupnosti již padesátý člen opravdu spočítáte.

Až někdy budete programovat v jazyku, ve kterém třeba nejsou cykly nebo prostě jen rekurze máte rádi, vzpomeňte si na iterativní procesy, ať tam nemáte samé procedury s exponenciální časovou složitostí ;-).

Linkuj.cz!

Komentáře

29. December 2007, 15:49

To je náhoda. Zrovna včera jsem se snažil vysvětlit kámošovi co to ta rekurze vlastně je. A hned mi výjde takovýhle článek. Hned mu pošlu odkaz :o)

# ObiSkyWalker
29. December 2007, 20:32

Díky za skvělý článek :-) Způsob rekurze sice znám, ale takhle dopodrobna jsem ho nikdy nestudoval.

30. December 2007, 14:28

Možná by ještě stálo za to připsat další posup řešní a to pomocí cyklu. Jednoduše bez volání fib_iter ve vetvi, kdy je n je větší než nula. Třeba za použití sekvence/listu­/pole… podle názvosloví jazyka.

Ukázka v Pythonu:

.
fiblst=[0,1]
for i in range(1,10):
      fiblst.append(fi­blst[i]+fiblst[i-1])
print fiblst
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55]

Komentáře jsou uzavřeny