Adobe Systems
F1420 – Rekurzia
1
Pokročilé funkcie, rekurzia
Kryštof Mrózek (445429@mail.muni.cz)
Kristína Tomanková (kristinatomankova@mail.muni.cz)
Radoslav Brunovský (rbrunovsky@mail.muni.cz)

Adobe Systems
2
Rekurzia
̶Rekurzia je proces, kedy sa objekt definuje pomocou samého seba.
̶
Two Mirrors (contrived) | Two mirrors facing one another cre… | Flickr
F1420 – Rekurzia

Adobe Systems
3
Rekurzívna funkcia
̶Funkcia, ktorá volá sama seba.
̶
̶
̶
̶
̶
̶
̶
Spôsobí takýto zápis funkcie nejaký problém?
̶
F1420 – Rekurzia
Vnútro funkcie (odsadené) – funkcia sa odkazuje sama na seba
rekurzívne volanie
obyčajné volanie

Adobe Systems
4
Základný prípad (base case)
̶Každá rekurzívna funkcia musí mať tzv. “base case“, ktorý po určitej dobe ukončí jej volanie.
̶Pokiaľ funkcia ničím neskončí, tak python ju skúsi zavolať max 1000x, pokým nevyhodí
RecursionError:
F1420 – Rekurzia

Adobe Systems
5
Základný prípad (base case)
̶Každá rekurzívna funkcia musí mať tzv. “base case“, ktorý po určitej dobe ukončí jej volanie.
̶Príklad: Spočítajte všetky čísla od 1 po x
F1420 – Rekurzia

Adobe Systems
6
Základný prípad (base case)
̶Každá rekurzívna funkcia musí mať tzv. “base case“, ktorý po určitej dobe ukončí jej volanie.
̶Príklad: Spočítajte všetky čísla od 1 po x
F1420 – Rekurzia
Base case – zadaný pomocou if podmienky

Adobe Systems
7
Základný prípad (base case)
F1420 – Rekurzia
suma(4)
vetva else:
return: 4 +
suma(3)
vetva else:
return: 3 +
suma(2)
vetva else:
return: 2 +
suma(1)
vetva if:
return: 1
Čo sa reálne deje, keď
zavolám suma(4):

Adobe Systems
8
Základný prípad (base case)
F1420 – Rekurzia
suma(4)
vetva else:
return: 4 +
suma(3)
vetva else:
return: 3 +
suma(2)
vetva else:
return: 2 +
suma(1)
vetva if:
return: 1
Čo sa reálne deje, keď
zavolám suma(4):
4 + 3 + 2 + 1
= 10

Adobe Systems
9
Cvičenie
F1420 – Rekurzia

Adobe Systems
10
Cvičenie
̶Napíšte rekurzívnu funkciu, ktorá spočíta faktoriál daného celého čísla.
F1420 – Rekurzia
Viacero základných prípadov

Adobe Systems
11
Cvičenie
̶Napíšte rekurzívnu funkciu, ktorá spočíta faktoriál daného celého čísla.
F1420 – Rekurzia

Adobe Systems
12
Rekurzívne funkcie vs iterácie
̶Rekurziu môžeme chápať aj ako “elegantnú“ iteráciu (všetky rekurzívne problémy sa dajú riešiť aj
iterovaním).
̶Príklad: Faktoriál
̶
F1420 – Rekurzia
Rekurzia
Iterácia

Adobe Systems
13
Rekurzívne funkcie vs iterácie
̶Rekurziu môžeme chápať aj ako “elegantnú“ iteráciu (všetky rekurzívne problémy sa dajú riešiť aj
iterovaním).
̶Príklad: Faktoriál
̶
F1420 – Rekurzia

Adobe Systems
14
Rekurzívne funkcie vs iterácie
̶Rekurziu môžeme chápať aj ako “elegantnú“ iteráciu (všetky rekurzívne problémy sa dajú riešiť aj
iterovaním).
̶Príklad: Faktoriál – v prípade volania funkcie na číslo 50 dostaneme výsledok v prípade využitia
iterácie cca 56x rýchlejšie.
F1420 – Rekurzia
Výhody rekurzie
Nevýhody rekurzie
Elegantný a prehľadný kód
Rekurzívne volanie funkcie zaberá veľa pamäte a času
Komplexný problém je rozdelený do jednoduchých pod-problémov
Náročné na debug
* Rekurziu je výhodné použiť v prípadoch, kde je vnáranie logické a prirodzené – napr. pri
navigovaní v súboroch na počítači.

Adobe Systems
15
Záverečné cvičenie
̶Predstavte si matriošku, ktorá má veľkosť x (predstavuje výšku matriošky). Každá nasledujúca
matrioška je o 20% menšia ako tá predchádzajúca. Minimálna veľkosť matriošky je 3 cm. Napíšte
funkciu, ktorá spočíta koľko matriošiek celkom obsahuje matrioška o veľkosti x.
F1420 – Rekurzia
Obrázky Russian Doll – procházejte fotografie, vektory a videa 30,599 | Adobe Stock