• Lekce 9
  • Co jsme dnes probrali
    • 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čí)
• 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:

  def faktorial(n):
    if n == 0:
        return 1
    else:
        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:

  def fib(n):
    if (n <= 0):
        return 0
    elif (n == 1):
        return 1
    else:
        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
• Výpočet $n$-tého Fibonacciho čísla s použitím cache:

  def fib_cached(n, cache={}):
    if (n <= 0):
        # pokud n <= 0, vraťme 0
        return 0
    elif n == 1:
        # pokud n == 1, vraťme 1
        return 1
    elif n in cache:
        # pokud už jsme n-té Fib. číslo již vypočítali, vrátíme ho
        return cache[n]
    else:
        # pokud ne, vypočteme ho
        num = fib_cached(n - 1, cache) + fib_cached(n - 2, cache)
        # zapamatujeme si ho
        cache[n] = num
        # vrátíme ho
        return num
  

  • V definici funkce můžete vidět argument cache={}
    • To říká, že druhý argument funkce fib_cached má výchozí hodnotu, kterou je prázdný slovník
  • Pro cache můžeme použít i pole

    def fib_c(n, cache):
        if cache[n] != -1:
            return cache[n]
        else:
            cache[n] = fib_c(n - 1, cache) + fib_c(n - 2, cache)
    
            return cache[n]
    
    n = 500
    cache = [-1] * (n + 1)
    cache[0] = 0
    cache[1] = 1
    print(fib_c(n, cache))
    

• 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)