02_rekurze

Rekurze

Přednáška 2

Rekurze

• Rekurze je jeden ze způsobů řešení algoritmů
• Rekurze je stav, kdy objekt je součástí sám sebe 

(například: namíříme-li kameru na monitor, který 

zobrazuje obraz z kamery či soustava protilehlých 

zrcadel)

• Rekurze musí obsahovat podmínku ukončení 

(konečnost algoritmu)

• Rekurze je situace, kdy se jako součást řešení problému 

objeví stejný problém/řešení

• Většinu případů rekurzí lze převést na nerekurzivní 

algoritmus (a naopak )

Rekurze

• Rekurze je spojená s vysokými nároky na využití 

paměti zásobníku 

• I vlastní kód rekurzivního volání je rozsáhlejší o režii 

s voláním funkce a předáváním parametrů. Tato 
část zabere také více času oproti realizaci cyklem

• Rekurentní algoritmy mohou vést k přehlednějšímu 

řešení (pro některé typy úloh)

• V programování se objevuje rekurze u funkcí a u 

datových typů

Rekurze

• U datových typů se jedná o struktury s uzly, které se odkazují/propojují 

s jinými uzly stejného typu. Proměnná reprezentující uzel, musí tedy 
obsahovat stejnou proměnnou, nebo několik, které na ni navazují. 
(Binární strom se skládá z uzlu a dvou stromů …).

• V případě, že by proměnná obsahovala přímo stejnou proměnnou, došlo 

by k rekurzi přímo při jejím vytváření a tím by jedna proměnná zaplnila 
celou paměť. Proto se pro návazné struktury musí používat odkaz 
(ukazatel).

• Druhým důvodem proč nemůže proměnná obsahovat sama sebe je to, 

že v daném místě ještě není dokončena její definice a proto se nezná její 
velikost (a překladač pro ni tedy nemůže vyhradit místo, které nezná a 
zahlásí chybu).

Rekurze

• Příklady rekurze

• strom (z větve jdou větve, co je ještě větev? …)
• většina her - pravidla v každém tahu jsou stejná, princip 

řešení je tedy stejný i když se data mění. 

• matrjošky  ( https://www.educative.io/collection/page/10370001/760001/1000001 )
• fraktály ( https://www.root.cz/clanky/fraktaly-kolem-nas/) 
• Google.com -> zadat heslo „Recursion“