Deváté cvičení ... okomentované doplňkové příklady (Skupina 3)¶

Z minule¶

In [1]:
# ukázka funkce, kde některé parametry mají výchozí hodnotu
def demo_funkce(x, y = 1, z = 0, w = 0):
    if y >= 0:
        return x ** 2 - 3 * x + 1 + z +  w
    else:
        return x + y

# volání funkce s pozičními a s pojmenovanými argumenty:
print(demo_funkce(1, w=10))
print(demo_funkce(x=5))

9
11

Co je to docstring a jak zobrazit nápovědu pro nějaký objekt, např. pro funkci print:

In [ ]:
help(print)

Rekurzivní funkce¶

Rekurzivní funkce je taková funkce, která volá sama sebe, a to buď přímo (f → f) nebo nepřímo (f → g → h → f).

Výpočet faktoriálu¶

Klasickým příkladem pro vysvětlení rekurze je výpočet faktoriálu nezáporného celého čísla $n$. Tuto operaci lze definovat oběma způsoby. Jednak pomocí nerekurzivního zápisu:

\begin{align*} f(n) = n! &= n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 3 \cdot 2 \cdot 1 = \prod\limits_{j=1}^n j, \end{align*}

přičemž $0! = 1$ dle konvence (prázdný produkt).

Alternativně můžeme faktoriál definovat rekurzivně:

\begin{align*} n! = \begin{cases} 1 &\quad \text{pokud $n = 0$,} \\ n \cdot (n-1)! &\quad \text{pokud $n \ge 1$.} \end{cases} \end{align*}

Pak:

\begin{align*} f(n) = \begin{cases} 1 &\quad \text{pokud $n = 0$,} \\ n \cdot f(n-1) &\quad \text{pokud $n \ge 1$.} \end{cases} \end{align*}
In [3]:
# matematickou definici můžeme snadno přepsat do podoby programu:
def factorial_recursive(n):
    # ověření základní/počáteční podmínky
    if n == 0:
        return 1

    # rekurzivní volání pro vyřešení menší úlohy
    partial = factorial_recursive(n-1)

    # rekombinace a vrácení finálního výsledku
    return n * partial

#print(factorial_recursive(0))
#print(factorial_recursive(1))
#print(factorial_recursive(2))
#print(factorial_recursive(3))
print(factorial_recursive(4))

24

Tip: Kliknutím na tlačítko pytutor v rozhraní JupyterLab se zobrazí grafická interpretace toho, co se v programu děje. Je důležité si uvědomit, že jednotlivá volání rekurzivní funkce jsou na sobě zcela nezávislá – mají různé hodnoty parametrů, nezávislé lokální proměnné, atd. V grafické interpretaci pytutor je to názorně zobrazeno.

Obecná struktura rekurzivní funkce se skládá z následujících částí:

  1. základní případ: nejjednodušší úloha, kterou lze vyřešit přímo bez použití rekurze
  2. rekurzivní volání: rozdělení velké úlohy na menší části a použití stejné funkce pro vyřešení těchto menších úloh
  3. rekombinace: spojení výsledků menších úloh pro vyřešení původní velké úlohy
In [2]:
# Faktorial počítaný iterativně pomocí while cyklu
def factorial_iterative(n):    
    product = 1
    while n > 1:
        product = product * n
        n = n - 1

    return product

print(factorial_iterative(0))
print(factorial_iterative(1))
print(factorial_iterative(2))
print(factorial_iterative(3))
print(factorial_iterative(4))

1
1
2
6
24
In [4]:
# Faktorial iterativně pomocí for cyklu:
def factorial_iterative(n):    
    product = 1
    for n in range(2,n+1):
        product = product * n
    return product

print(factorial_iterative(0))
print(factorial_iterative(1))
print(factorial_iterative(2))
print(factorial_iterative(3))
print(factorial_iterative(4))

1
1
2
6
24

Stejně jako v iteračním případě i rekurzivní algoritmus se může zacyklit:

  • pokud v cyklu while neošetříte správně podmínku, kdy se má jeho provádění ukončit, program nikdy neskončí
  • pokud v rekurzivní funkci neošetříte správně počáteční podmínku, která ukončí rekurzi, stane se totéž (resp. program skončí systémovou chybou po dosažení maximální dovolené hloubky rekurze)
In [ ]:
# chyba: nezadala jsem počáteční podmínku:
def factorial_recursive(n):
    # ověření základní/počáteční podmínky
    # if n == 0:
    #    return 1

    # rekurzivní volání pro vyřešení menší úlohy
    partial = factorial_recursive(n-1)

    # rekombinace a vrácení finálního výsledku
    return n * partial

#print(factorial_recursive(0))
#print(factorial_recursive(1))
#print(factorial_recursive(2))
#print(factorial_recursive(3))
print(factorial_recursive(4))

Všimněte si, že Python umožňuje poměrně efektivně pracovat s libovolně velkými celými čísly. Pomocí výše definovaných funkcí můžeme rychle spočítat např. hodnotu $100!$ (výpočet by měl trvat jen zlomek vteřiny):

In [12]:
factorial_iterative(100)
Out[12]:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000
In [ ]:
# rekurze má omezenou maximální hloubku: 
factorial_recursive(10000)

Fibonacciho posloupnost¶

Fibonacciho posloupnost je posloupnost nezáporných celých čísel $F_n$ pro $n \in \mathbb N_0$, která je definována následujícím rekurentním předpisem:

$$ F_n = \begin{cases} 0 &\quad \text{pokud $n = 0$,} \\ 1 &\quad \text{pokud $n = 1$,} \\ F_{n-2} + F_{n-1} &\quad \text{pokud $n \ge 2$,} \\ \end{cases} $$
In [16]:
# rekurzivní algoritmus:
def fib(n):
    if n == 0:
        # ověření první počáteční podmínky
        return 0
    elif n == 1:
        # ověření druhé počáteční podmínky
        return 1
    else:
        # rekurzivní volání pro vyřešení menších úloh
        # rekombinace a vrácení finálního výsledku
        return fib(n-2) + fib(n-1)

print(fib(5))

5

Tato implementace je sice velmi přehledná a přímočará, ale není vůbec efektivní. Při výpočtu funkce s danou hodnotou n totiž dochází k velkému množství větvení a opakovanému spouštění funkce s argumenty, které už byly spočítány dříve – viz interaktivní průchod nástrojem pytutor.

Řešení:¶
  1. pamatovat si předchozí výsledky volání funkce fib (pro tuhle implementaci teď nemáme dostatečné znalosti)
  2. použití iteračního přístupu

Iterační funkci pro výpočet Fibonacciho čísel zkuste naprogramovat sami. Můžete využít následující kostru programu:

In [14]:
def fib_iterative(n):
    # nastavení počátečních hodnot
    term1 = 0
    term2 = 1

    # iterační výpočet
    for i in range(n):
        new = term1 + term2
        term1 = term2
        term2 = new
    return term1

print(fib_iterative(5))

5
In [17]:
# rekurze, která imituje iterativní výpočet
def fib_recursive(n,term1 = 0, term2 = 1):
    if n == 0:
        # ověření počáteční podmínky
        return term1
    else:
        # rekurzivní volání pro vyřešení menších úloh
        # rekombinace a vrácení finálního výsledku
        return fib_recursive(n-1, term2, term1+term2)

print(fib_recursive(5))

5

Příklady¶

1. Součet číslic¶

Naprogramujte funkci sum_digits(n), která rekurzivním způsobem spočítá součet číslic v desítkovém zápisu přirozeného čísla n. (Nerekurzivní algoritmus jsme již programovali na některém z předchozích cvičení.)

In [10]:
# iterativně:
def sum_digits(n):
    sum = 0
    while n > 0 :
        d = n % 10
        n = n // 10
        sum += d
    return sum    

print(sum_digits(123))
assert sum_digits(1234567890) == 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0

6
In [1]:
# řešení úlohy rekurzivně:
def sum_digits(n):

    # ověření základní/počáteční podmínky
    if n == 0:
        return 0
        
    # rekurzivní volání pro vyřešení menší úlohy
    v = sum_digits(n // 10) 

    # rekombinace a vrácení finálního výsledku
    return (n % 10) + v
print(sum_digits(123))

assert sum_digits(1234567890) == 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 0

6

2. Spořící kalkulačka¶

Na spořící účet vkládáme každý měsíc stejnou částku. Naprogramujte funkci, která pro zadaný počet měsíců, úrok a měsíční vklad spočte a vrátí uspořenou částku včetně úroků. Úlohu řešte nejprve pomocí rekurze a poté bez využití rekurze.

In [3]:
def uspor_rekurzivne(mesice, urok, vklad):
    
    # ověření základní/počáteční podmínky
    if mesice == 0:
        return 0

    # rekurzivní volání pro vyřešení menší úlohy
    usporena_castka = uspor_rekurzivne(mesice - 1, urok, vklad)

    # rekombinace a vrácení finálního výsledku
    
    # zhodnoť uspořenou částku:
    usporena_castka += usporena_castka * (urok/100)
                 # řešení pro měsíční úrok: urok/100
                 # pro roční úrok:          urok/12/100
    
    # přidej aktuální vklad:
    usporena_castka += vklad
    
    return usporena_castka

print(uspor_rekurzivne(12, 3.3, 1000))

14436.345269786387
In [4]:
def uspor_bez_rekurze(mesice, urok, vklad):
    
    usporena_castka = 0

    # pro každý měsíc:
    for mesic in range(mesice):
        
        # zhodnoť uspořenou částku:
        usporena_castka += usporena_castka * (urok/100)
        
        # přidej aktuální vklad:
        usporena_castka += vklad
        
    return usporena_castka

print(uspor_bez_rekurze(12, 3.3, 1000))

14436.345269786387

3. Největší společný dělitel dvou čísel¶

Naprogramujte funkci, která spočítá a vrátí hodnotu největšího společného dělitele celých čísel a a b. Nejprve vymyslete svůj vlastní, "naivní" algoritmus:

In [ ]:
def nsd_naive(a, b):
    ...

print(nsd_naive(140, 15))

assert nsd_naive(288, 420) == 12

Poté naprogramujte řešení stejné úlohy pomocí Eukleidova algoritmu:

In [ ]:
def nsd_euclid(a, b):
    ...

print(nsd_euclid(140, 15))

assert nsd_euclid(288, 420) == 12