Rekurze
E 3011
Jan Bóhm
RECETOX
April 17, 2024
Jan Bóhm (RECETOX)
Přednáška IX
□        S> - =
April 17, 2024
1/7
Motivace
def mystery(n):
if n <= 0:
print("BOOM!")
else :
print(n) mystery(n-1)
mystery (10)
Jan Bohm (RECETOX)
Přednáška IX
UHATARE m UORKlNO OM?
TRYIM3 to FIX THE PROBLEMS I CREATED UHEľM I trw x) FlX
the pfíceum r created uhew
itriedtdfixihe problems ICREflTEDUHEN...
Figure: Zdroj: https://xkcd.com/1739/
□ s
Co je to rekurze?
Neformálně - voláme funkci f uvnitř funkce f.
Jan Bôhm (RECETOX)
Přednáška IX
□        S> - =
April 17, 2024
4/7
Co je to rekurze?
Neformálně - voláme funkci f uvnitř funkce f.
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)
Přednáška IX
□        S> - =
April 17, 2024
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:
Jan Bóhm (RECETOX)
end - start, "seconds")
Přednáška IX April 17, 2024
5/7
Rekurze
Rekurentní Fibonacci
Napište funkci rFibonacci(n), která spočítá n-té číslo Fibonacciho posloupnosti pomocí rekurze. Opět porovnejte rychlost staré funkce a této rekurentní pro n=35.
Rekurentní ciferný součet
Napište funkci rDigitSum(n), která spočítá opakovaný ciferný součet (tj počítáme ciferný součet dokud nedostaneme jednociferné číslo, např. 654 15-» 6.
Jan Bôhm (RECETOX)
Přednáška IX
□        g - =
April 17, 2024
6/7
Collatzova domněnka
Algorithm 1: Collatzova domnenka
Input: n e N while n > 1 do
if n is even then
|   n <- n -T- 2 ; else
|   n <- 3 • n + 1; end
return n
end
Rekurentní Collatzova domněnka
Napište funkci rCollatz(n, seq = None), která rekurentně provede algoritmus výše a vrátí jej jako list, např.: rCollatz(lO) = [10, 5, 16, 8, 4, 2, 1]
Jan Bôhm (RECETOX)
Přednáška IX
□ - =
April 17, 2024
7/7