Lekce 1 - Úvod do rekurze
Vítejte u první lekce kurzu o rekurzi. Rekurze je jednou ze zdánlivě obtížnějších kapitol programování a s její praktickou aplikací se v každodenním programátorském životě příliš často nesetkáme. Na druhou stranu nám její zvládnutí otevře nové obzory a umožní řešit problémy, které bychom jinými způsoby řešili jen velmi obtížně.
V dnešním tutoriálu o rekurzivních algoritmech si ukážeme, co je to rekurze, a jak se vytváří rekurzivní metoda.
Rekurzivní charakter úlohy
Začněme příkladem. Představme si, že chceme napsat metodu
suma(n), která jako parametr přebírá kladné celé číslo
n a vrací součet čísel od jedné do n.
Implementaci takové metody pomocí cyklu bychom jistě zvládli, my si však
můžeme všimnout, že výpočet suma(n) v sobě obsahuje
výpočet několika dalších sum, např. pro suma(4)
dostaneme:
Vzoreček pro výpočet sumy tedy můžeme zapsat takto:
suma(n) = 1, pokud n == 1,suma(n) = n + suma(n – 1), pokud n > 1.
O takových úlohách říkáme, že mají rekurzivní charakter, tzn. že ve svém řešení obsahují dílčí úlohy stejného typu.
Stejný rekurzivní charakter bychom našli u mnoha dalších úloh, např. u výpočtu celočíselné mocniny: xn = x · xn-1, nebo u výpočtu faktoriálu: n! = n · (n-1)!.
Rekurzivní metoda
Vraťme se ale k metodě pro výpočet sumy. Vyjdeme z rekurzivního vzorečku, který přepíšeme do podoby metody:
-
def suma(n): if n == 1: return 1 else: return n + suma(n - 1)
-
int suma(int n) { if (n == 1) return 1; else return n + suma(n - 1); }
-
public static function suma(int $n): int { if ($n == 1) return 1; else return $n + suma($n - 1); }
-
public static int suma(int n) { if (n == 1) return 1; else return n + suma(n - 1); }
Právě jsme napsali tzv. rekurzivní metodu.
V programátorské terminologii je rekurzivní metoda taková metoda, která někde ve svém těle volá sebe samu.
Všimněme si dvou důležitých věcí:
- metoda má ukončovací podmínku, při jejímž splnění
se další volání už neprovede (zde
if n == 1), - při rekurzivním volání se mění argument metody – proces se posouvá ke splnění úlohy.
Jak probíhají rekurzivní volání
Při rekurzivním volání se děje to samé, co při jakémkoliv jiném
volání metody. Dojde k pozastavení probíhajícího vlákna, volající
metoda předá řízení volané metodě a čeká na návratovou hodnotu.
Důležité je ale pochopit, že v případě rekurze se toto děje opakovaně a
v jedné chvíli máme rozpracováno několik metod, které postupují
podle stejného schématu. Časový průběh při volání např.
suma(4) vypadá takto:
Všimněme si důležité věci: Metoda, která byla volána jako první, končí jako poslední a naopak. Toto schéma označujeme jako LIFO.
Schématu LIFO – Last In First Out odpovídá fungování datové struktury zásobníku, který metody pro svůj běh využívají.
Další jednoduché rekurzivní metody
Uveďme si několik dalších příkladů jednoduchých rekurzivních metod.
Klesající posloupnost čísel
Začneme metodou, která jako parametr dostane celé číslo n a
na terminál vypíše klesající posloupnost čísel od
n do 1. Implementace takové rekurzivní metody může vypadat
například takto:
-
def vypisKlesajici(n): if n == 0: return print(n) vypisKlesajici(n - 1)
-
void vypisKlesajici(int n) { if (n == 0) return; Console.WriteLine(n); vypisKlesajici(n - 1); }
-
public static function vypisKlesajici(int $n): void { if ($n == 0) return; echo("$n<br>"); vypisKlesajici($n - 1); }
-
public static void vypisKlesajici(int n) { if (n == 0) return; System.out.println(n); vypisKlesajici(n - 1); }
Rostoucí posloupnost čísel
Zkusme si napsat podobnou metodu, která ale vypisuje
rostoucí posloupnost čísel od 1 do n. Mohli
bychom samozřejmě začít od jedničky, vždy vypsat číslo a zavolat metodu
s parametrem o jedničku větším. My ale můžeme udělat jinou úpravu:
Vyměníme pořadí výpisu čísla a volání
metody:
-
def vypisRostouci(n): if n == 0: return vypisRostouci(n - 1) print(n)
-
void vypisRostouci(int n) { if (n == 0) return; vypisRostouci(n - 1); Console.WriteLine(n); }
-
public static function vypisRostouci(int $n): void { if ($n == 0) return; vypisRostouci($n - 1); echo("$n<br>"); }
-
public static void vypisRostouci(int n) { if (n == 0) return; vypisRostouci(n - 1); System.out.println(n); }
Metoda pro výpis rostoucí posloupnosti tedy napřed zavolá svého
rekurzivního potomka, čeká na jeho návrat a teprve nakonec
vypisuje svoje číslo. Metoda volaná jako první (vypisující číslo
n) tedy provede výpis úplně naposled a naopak, tedy opět
LIFO schéma. Výsledkem je výpis rostoucí posloupnosti,
ačkoliv jsme začali voláním s parametrem n. Pokud je nám
fungování těchto dvou metod jasné, jsme k pochopení celé rekurze velmi
blízko.
Nejvyšší liché číslo
Posledním příkladem bude metoda, která prohledá pole celých čísel a vrátí nejvyšší v něm obsažené liché číslo. Pokud pole neobsahuje žádné liché číslo, metoda vrátí nulu:
-
def najdiNejvyssiLiche(pole, index = 0, maxLiche = 0): if index == len(pole): return maxLiche if pole[index] % 2 == 1 and pole[index] > maxLiche: maxLiche = pole[index] return najdiNejvyssiLiche(pole, index + 1, maxLiche)
-
int najdiNejvyssiLiche(int[] pole, int index = 0, int maxLiche = 0) { if (index == pole.Length) return maxLiche; if (pole[index] % 2 == 1 && pole[index] > maxLiche) maxLiche = pole[index]; return najdiNejvyssiLiche(pole, index + 1, maxLiche); }
-
public static function najdiNejvyssiLiche(array $pole, int $index = 0, int $maxLiche = 0): int { if ($index == count($pole)) return $maxLiche; if ($pole[$index] % 2 == 1 && $pole[$index] > $maxLiche) $maxLiche = $pole[$index]; return najdiNejvyssiLiche($pole, $index + 1, $maxLiche); }
-
public static int najdiNejvyssiLiche(int[] pole, int index, int maxLiche) { if (index == pole.length) return maxLiche; if (pole[index] % 2 == 1 && pole[index] > maxLiche) maxLiche = pole[index]; return najdiNejvyssiLiche(pole, index + 1, maxLiche); }
Metoda přebírá tři parametry:
- prohledávané pole,
- index aktuálně zkoumaného prvku,
- nejvyšší dosud nalezenou hodnotu.
Pokud je aktuálně zkoumané číslo liché a je větší než dosavadní maximum, je do dalšího volání dosazeno na jeho místo. Opět nezapomeňme na schéma LIFO: Nejvyšší hodnota se nakonec dostane k prvně volané metodě, která ji vrátí.
Kdy rekurzi použít
Doposud jsme rekurzi demonstrovali na jednoduchých úlohách. Jejich účelem bylo ukázat princip rekurze. Nicméně všechny tyto úlohy se dají snadno vyřešit pomocí cyklů. Rekurzivními metodami můžeme nahradit jakýkoliv cyklus, ale ve skutečnosti to málokterý programátor udělá. Důvody jsou tyto:
- rekurze zbytečně spotřebovává systémové prostředky, protože volání metod vyžaduje provedení množství operací a alokaci paměti pro argumenty, čemuž se při iteraci vyhneme,
- program se zbytečnou rekurzí je méně srozumitelný, hůř se spravuje a obtížněji se v něm hledají chyby.
Rekurzi nepoužíváme pro úlohy, které jdou snadno vyřešit prostým cyklem.
Užitečnou pomůckou při rozhodování je kolikrát metoda ve svém těle volá sebe samu. Pokud pouze jednou, označujeme takovou rekurzi za lineární a je velmi pravděpodobné, že taková metoda půjde nahradit cyklem. Pokud metoda sebe samu volá více než jednou, označujeme ji jako stromovou a v tom případě nám může rekurze velmi pomoct.
V příští lekci, Stromová rekurze - Generování všech možností, si ukážeme, jak se rekurze skutečně používá. Naučíme se, jak vygenerovat všechny možnosti při řešení nějaké úlohy.
