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

  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
• 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_cached má výchozí hodnotu, kterou je prázdný slovník
  • 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))
    

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