Cvičení č. 9 rozšířené o poznámky ze cvičení a řešení některých příkladů (ZS 2024/25)¶

V minulém díle jste viděli...¶

Definice funkce s parametry a vrácení výsledné hodnoty pomocí příkazu return:

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

# volání funkce s pozičními a s pojmenovanými argumenty:
print(demo_funkce(6, 7))
print(demo_funkce(y=6, x=7))
#demo_funkce(y=1, x=7)
print(1, 2, 3, end = "_")

19
29
1 2 3_

Také jste viděli, co je to lokální proměnná, jaký je její obor platnosti a jaké je chování v případě shody názvu několika proměnných s různým oborem platnosti.

Předávání argumentů funkci pozičním způsobem a pomocí pojmenovaných argumentů:

  • demo_funkce_s_mnoha_parametry(1, 2, 3, 4)
  • demo_funkce_s_mnoha_parametry(param1=1, param2=2, param3=3, param4=4)
  • demo_funkce_s_mnoha_parametry(param2=2, param1=1, param4=4, param3=3)
  • demo_funkce_s_mnoha_parametry(1, 2, param4=4)

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

In [8]:
help(print)

Help on built-in function print in module builtins:

print(*args, sep=' ', end='\n', file=None, flush=False)
    Prints the values to a stream, or to sys.stdout by default.

    sep
      string inserted between values, default a space.
    end
      string appended after the last value, default a newline.
    file
      a file-like object (stream); defaults to the current sys.stdout.
    flush
      whether to forcibly flush the stream.

Pojmenování proměnných a funkcí¶

Ačkoli pojmenování proměnných a funkcí typicky nemá vliv na správnou funkčnost programu, výběr vhodných jmen je velmi důležitý pro lidi, kteří zdrojový kód čtou a upravují. Pro přehlednost kódu je důležitých několik univerzálních pravidel:

  • Názvy by měly být výstižné a odpovídat tomu, k čemu v programu slouží. Nepoužívejte příliš obecné názvy.
  • Všechny názvy by měly být v angličtině (nejuniverzálnější přirozený jazyk).
  • Vyhýbejte se zkratkám a názvům které mohou mít více různých významů. Používání jednopísmenných identifikátorů je vhodné pouze v matematických výrazech (např. x, y, z, i, j, k).
  • Názvy funkcí typicky vyjadřují jejich účinek (např. print) nebo návratovou hodnotu (např. abs).
  • Chování funkce je dobré popsat v jejím docstringu (např. přípustné hodnoty parametrů, překvapivé chování, atd).

Několik jednoduchých příkladů:

Nevhodné Lepší
true_false rolled_a_one
d dice
play_helper take_turn
my_int num_rolls
l, I, O k, i, m

Rekurzivní funkce¶

In [12]:
# příklad: líní úředníci dávají razítka:
def razitka(n):
    if n == 1:
        print("*")
    elif n > 1:
        print("*")
        razitka(n-1)

razitka(5)

*
*
*
*
*
In [14]:
# příklad: nekonečná rekurze:
def razitka(n):
    razitka(n-1)
    print("*")
    
razitka(5)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[14], line 6
      2     razitka(n-1)
      3     print("*")
----> 6 razitka(5)

Cell In[14], line 2, in razitka(n)
      1 def razitka(n):
----> 2     razitka(n-1)
      3     print("*")

Cell In[14], line 2, in razitka(n)
      1 def razitka(n):
----> 2     razitka(n-1)
      3     print("*")

    [... skipping similar frames: razitka at line 2 (2974 times)]

Cell In[14], line 2, in razitka(n)
      1 def razitka(n):
----> 2     razitka(n-1)
      3     print("*")

RecursionError: maximum recursion depth exceeded

Při vykonávání programu typicky dochází k velkému počtu větvení a přepínání prostředí, ve kterých se vyhodnocují jednotlivé funkce. K přepínání může docházet na několika místech, např.:

  • funkce f postupně volá funkce g, h, atd.
  • při skládání funkcí v rámci jednoho výrazu, např. f(g(a, h(b)), h(g(a, b)))

Dalším typickým způsobem větvení programu je rekurze. Rekurzivní funkce je taková funkce, která volá sama sebe, a to buď přímo (f → f) nebo nepřímo (f → g → h → f). Použití rekurze může v určitých případech zjednodušit řešení dané úlohy. Jako příklad porovnejte iterační a rekurzivní algoritmus pro hledání klíče v hromadě krabic:

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)

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

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, nejprve si ukážeme nerekurzivní zápis:

\begin{align*} 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).

Implementace odpovídajícího algoritmu v jazyku Python může vypadat následovně:

In [10]:
# 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))

24

Tip: Zkuste ve funkci factorial_iterative místo příkazu while použít příkaz for a funkci range.

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*} \begin{align*} f(n)= n! = \begin{cases} 1 &\quad \text{pokud $n = 0$,} \\ n \cdot f(n-1) &\quad \text{pokud $n \ge 1$.} \end{cases} \end{align*}

Zde je jasně vidět základní/počáteční podmínka pro ukončení rekurze, rekurzivní volání pro hodnotu o 1 menší a rekombinace výsledku menší úlohy s parametrem velké úlohy. Rekurzivní algoritmus tedy můžeme dostat pomocí obecné struktury popsané výše (místo výpustek ... je třeba doplnit správný kód):

In [4]:
# Faktorial počítaný rekurzivně:
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))

1
1
2
6
24
In [7]:
# Faktorial počítaný iterativně pomocí for cyklu
def factorial_forcycle(n):
    product = 1
    for i in range(2, n+1):
        product = product * i
    return product
    
print(factorial_forcycle(4))

24
In [21]:
factorial_iterative(1000)
Out[21]:
402387260077093773543702433923003985719374864210714632543799910429938512398629020592044208486969404800479988610197196058631666872994808558901323829669944590997424504087073759918823627727188732519779505950995276120874975462497043601418278094646496291056393887437886487337119181045825783647849977012476632889835955735432513185323958463075557409114262417474349347553428646576611667797396668820291207379143853719588249808126867838374559731746136085379534524221586593201928090878297308431392844403281231558611036976801357304216168747609675871348312025478589320767169132448426236131412508780208000261683151027341827977704784635868170164365024153691398281264810213092761244896359928705114964975419909342221566832572080821333186116811553615836546984046708975602900950537616475847728421889679646244945160765353408198901385442487984959953319101723355556602139450399736280750137837615307127761926849034352625200015888535147331611702103968175921510907788019393178114194545257223865541461062892187960223838971476088506276862967146674697562911234082439208160153780889893964518263243671616762179168909779911903754031274622289988005195444414282012187361745992642956581746628302955570299024324153181617210465832036786906117260158783520751516284225540265170483304226143974286933061690897968482590125458327168226458066526769958652682272807075781391858178889652208164348344825993266043367660176999612831860788386150279465955131156552036093988180612138558600301435694527224206344631797460594682573103790084024432438465657245014402821885252470935190620929023136493273497565513958720559654228749774011413346962715422845862377387538230483865688976461927383814900140767310446640259899490222221765904339901886018566526485061799702356193897017860040811889729918311021171229845901641921068884387121855646124960798722908519296819372388642614839657382291123125024186649353143970137428531926649875337218940694281434118520158014123344828015051399694290153483077644569099073152433278288269864602789864321139083506217095002597389863554277196742822248757586765752344220207573630569498825087968928162753848863396909959826280956121450994871701244516461260379029309120889086942028510640182154399457156805941872748998094254742173582401063677404595741785160829230135358081840096996372524230560855903700624271243416909004153690105933983835777939410970027753472000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
In [12]:
# rekurze má omezenou maximální hloubku: 
factorial_recursive(10000)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
Cell In[12], line 2
      1 # rekurze má omezenou maximální hloubku: 
----> 2 factorial_recursive(10000)

Cell In[4], line 7, in factorial_recursive(n)
      4     return 1
      6 # rekurzivní volání pro vyřešení menší úlohy
----> 7 partial = factorial_recursive(n-1)
      9 # rekombinace a vrácení finálního výsledku
     10 return n * partial

Cell In[4], line 7, in factorial_recursive(n)
      4     return 1
      6 # rekurzivní volání pro vyřešení menší úlohy
----> 7 partial = factorial_recursive(n-1)
      9 # rekombinace a vrácení finálního výsledku
     10 return n * partial

    [... skipping similar frames: factorial_recursive at line 7 (2974 times)]

Cell In[4], line 7, in factorial_recursive(n)
      4     return 1
      6 # rekurzivní volání pro vyřešení menší úlohy
----> 7 partial = factorial_recursive(n-1)
      9 # rekombinace a vrácení finálního výsledku
     10 return n * partial

RecursionError: maximum recursion depth exceeded

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.

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 [11]:
factorial_iterative(100)
Out[11]:
93326215443944152681699238856266700490715968264381621468592963895217599993229915608941463976156518286253697920827223758251185210916864000000000000000000000000

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} $$

Hodnoty této posloupnosti aproximují logaritmickou spirálu, ve které je faktor růstu roven hodnotě zlatého řezu:

Funkci pro výpočet Fibonacciho čísel naprogramujeme nejprve rekurzivním způsobem analogicky matematické definici uvedené výše (místo výpustek ... je třeba doplnit správný kód):

In [29]:
def fib(n):
    if n < 0:
        return
    elif 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. Vyhodnocování funkce fib můžeme zobrazit pomocí stromové struktury:

Pro větší hodnoty parametru n se výpočet velmi rychle zpomaluje (má exponenciální složitost). Rychlejšího programu s lineární složitostí můžeme dosáhnout několika způsoby:

  1. pamatovat si předchozí výsledky volání funkce fib (pro tuhle implementaci teď nemáme dostatečné znalosti)
  2. použití rekurze chytřejším způsobem
  3. použití iteračního přístupu

Chytřejší způsob použití rekurze pro Fibonacciho posloupnost může vypadat např. následovně:

In [13]:
def fib_recursive(n, a=0, b=1):
    if n < 0:
        return
    if n == 0:
        # ověření první počáteční podmínky
        return a
    elif n == 1:
        # ověření druhé počáteční podmínky
        return b
    else:
        # rekurzivní krok a rekombinace
        # parametry `a` a `b` představují poslední dvě spočítané hodnoty,
        # zde dojde k výpočtu nové hodnoty a posunutí
        return fib_recursive(n - 1, b, a + b)

print(fib_recursive(8))
for i in range(8):
    print(fib_recursive(i), end = " ")

21
0 1 1 2 3 5 8 13

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
    if n <= 1:
        return n
    new_term = 0
    
    # iterační výpočet
    for i in range(n-1):
        new_term = term1 + term2
        term1 = term2
        term2 = new_term

    return new_term

for i in range(8):
    print(fib_iterative(i), end = " ")
#print(fib_iterative(8))

0 1 1 2 3 5 8 13

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 [16]:
# řešení úlohy 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 [17]:
# ř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 [15]:
def uspor_rekurzivne(mesice, urok, vklad):
    if mesice == 0:
        return 0 
        
    minuly_mesic = uspor_rekurzivne(mesice-1, urok, vklad)
    
    urok_z_usporene_castky = minuly_mesic * urok / 100  #/ 12
    
    return minuly_mesic + urok_z_usporene_castky + vklad


print(uspor_rekurzivne(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

4. Rekurze na předchozích cvičeních¶

V některých příkladech z předchozích cvičení lze také výhodně použít rekurzi (např. řetězové zlomky apod).