Rekurze
Lekce 9
Co jsme dnes probrali
Rekurze
- Rekurzivní funkcí myslíme tu, která uvnitř svého těla volá sama sebe
- Může se zacyklit do nekonečna
- To ale nechceme, chceme určit konečnou podmínku (tehdy funkce skončí)
- Může se zacyklit do nekonečna
- Používají se na řešení úloh, které se dají seskládat s dílčích řešení, které
se počítají stejným způsobem.
- Třeba výpočet faktoriálu, Fibonacciho posloupnost, mocniny, apod.
- Výpočet faktoriálu by vypadal takto:
1 def faktorial(n): 2 if n == 0: 3 return 1 4 else: 5 return n * faktorial(n - 1) - Na hodině jsme se zabývali Fibonacciho posloupností. Sestrojili jsme pro
výpočet $n$-tého Fibonacciho čísla rekurzivní funkci:
1 def fib(n): 2 if (n <= 0): 3 return 0 4 elif (n == 1): 5 return 1 6 else: 7 return fib(n - 1) + fib(n - 2) - Je ale neefektivní (má exponenciální časovou složitost), protože počítá
více stejných čísel najednou
- Můžeme si je někde pamatovat a poté využít bez zbytečného znovuvypočítání
- Tomu říkáme caching
- Je ale neefektivní (má exponenciální časovou složitost), protože počítá
více stejných čísel najednou
- Výpočet $n$-tého Fibonacciho čísla s použitím cache:
1 def fib_cached(n, cache={}): 2 if (n <= 0): 3 # pokud n <= 0, vraťme 0 4 return 0 5 elif n == 1: 6 # pokud n == 1, vraťme 1 7 return 1 8 elif n in cache: 9 # pokud už jsme n-té Fib. číslo již vypočítali, vrátíme ho 10 return cache[n] 11 else: 12 # pokud ne, vypočteme ho 13 num = fib_cached(n - 1, cache) + fib_cached(n - 2, cache) 14 # zapamatujeme si ho 15 cache[n] = num 16 # vrátíme ho 17 return num - V definici funkce můžete vidět argument
cache={}- To říká, že druhý argument funkce
fib_cachedmá výchozí hodnotu, kterou je prázdný slovník
- To říká, že druhý argument funkce
- Pro cache můžeme použít i pole
1 def fib_c(n, cache): 2 if cache[n] != -1: 3 return cache[n] 4 else: 5 cache[n] = fib_c(n - 1, cache) + fib_c(n - 2, cache) 6 7 return cache[n] 8 9 n = 500 10 cache = [-1] * (n + 1) 11 cache[0] = 0 12 cache[1] = 1 13 print(fib_c(n, cache))
- V definici funkce můžete vidět argument
- Pokud byste si o rekurzi chtěli ještě něco přečíst, můžete zde (začátek této stránky, potom už se tam píše o něčem jiném)