Rekurze
E 3011
Jan Bóhm
RECETOX
April 19, 2023
Jan Bohm (RECETOX)
Cvičení IX
□        S> - =
April 19, 2023
1/7
Co nás dnes čeká
O Rek urze
Jan Bôhm (RECETOX)
Cvičení IX
□        S> - =
April 19, 2023
2/7
LOHATARE tV UORKING OM?
TRYING To FiX THE, PR08LEM51 CREATED UH£M I TRIED To Fix THE PROBLEMS I CREATED UHQJ I TRIED TD FIX THE PROBLEMS ICPEflTEPUHEN...
Figure: Zdroj: https://xkcd.com/1739/
□  ►   4 S
Co je to rekurze?
Neformálně - voláme funkci f uvnitř funkce f.
■
Jan Bôhm (RECETOX)
Cvičení IX
□        S> - =
April 19, 2023
4/7
Co je to rekurze?
Neformálně - voláme funkci f uvnitř funkce f.
Jednoduchý příklad
Co dělá tento kód?
def  countDown(n): if n <= 0:
print("BOOM!") else :
print(n)
countDown(n-1)
Jak používat rekurzi
Funkce musí rozlišovat 2 případy:
• Základní případ (base case) - jednoduchá situace, kterou umíme vyřešit. Opsahuje return a je to stop situace pro rekurzi.
o Rekurzivní případ - situace, kterou neumíme vyřešit jednoduše, ale umíme ji zjednodušit zavoláním funkce znovu na zjednodušený případ
Jan Bóhm (RECETOX)
Cvičení IX
April 19, 2023
4/7
Rekurze
Rekurentní faktorie
Napište funkci rFactorial(x), která spočítá faktoriál čísla x pomocí rekurze.
Porovnejte rychlost funkce f actorial(x), která počítá faktoriál pomocí cyklu a rychlost funkce rFactorial(x) pomocí návodu níže.
1 import time
2
3 def rFactorial(x):
4
5
6
7
8
if
return ??? else :
return ???rFactorial (???)
9 start = time.process_time() 10 print (rFactorial (500) ) n end = time.process_time () 12 print ("Time of execution:
end - start, "seconds")
Jan Bóhm (RECETOX)
Cvičení IX
□        S1 _ =
April 19, 2023
■E    "O ^ C* 5/7
Rekurze
Rekurentní Fibonacci
Napište funkci rFibonacci(n), spočítá n-té číslo Fibonacciho posloupnosti opomocí rekurze. Opět porovnejte rychlost staré funkce a této rekurentní pro n=35.
j
Jan Bóhm (RECETOX)
Cvičení IX
□        g - =
April 19, 2023
■E     "O ^ O' 6/7
Determinant matice
Determinant matice - Laplaceův rozvoj
Pomocí Laplaceova rozvoje naprogramujte funkci determinant (M), který ověří, zda je matice M čtvercová a pokud ano, spočítá její determinant pomocí Laplaceova rozvoje.
Návod
• Budeme používat rekurzi.
o Budeme rozvíjet podle prvního řádku/sloupce (záleží na vás).
• Laplaceův rozvoj namísto determinantu matice n x n počítá n determinantů matice (n — 1) x (n — 1) které sečte - vždy vynecháme daný řádek a sloupec.
o Pozor na znaménka, ta se střídají.
• Determinant pro matici 1 x 1 je triviální.
Jan Bôhm (RECETOX)
Cvičení IX
□        g - =
April 19, 2023
■E     "O ^ O' 7/7