13. Rekurze a iterace

1. Rekurzivní datové struktury
2. Rekurze I
3. Rekurze II
   1. Nekonečná rekurze
   2. Koncová rekurze
4. Memoizace
5. Iterátory definované třídou
6. Chyby a výjimky
   1. Vlastní výjimky
   2. Ošetření výjimek
7. Glosář
8. Cvičení

13.1 Rekurzivní datové struktury

Všechny dosud poznané datové typy mohou být v seznamech a enticích uspořádány přerůzným způsobem. Seznamy a entice mohou být také vnořené.

Povšimněme si, že termín seznam s vnořenými seznamy je použit ve své vlastní definici. Rekurzivní definice jako tato jsou zcela obvyklé v matematice a v programování. Poskytují stručný a účinný způsob popisu rekurzivních datových struktur, které jsou částečně složeny z menších a jednodušších výskytů sebe sama. Nejedná se o definici v kruhu, neboť v jisté úrovni dospějeme k seznamu, který nemá žádné položky, jež by byly seznamem.

Předpokládejme, že našim úkolem je napsat funkci, která sečte všechny hodnoty v seznamu s vnořenými seznamy. Python má vestavěnou funkci, která vytvoří součet řady čísel:

>>> sum([1, 2, 8])
11
>>> sum((3, 5, 8.5))
16.5
>>>

Pro náš seznam s vnořenými seznamy však funkce sum nepracuje:

>>> sum([1, 2, [11, 13], 8])
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for +: 'int' and 'list'

Problém spočívá v tom, že třetí položka seznamu je také seznam [11, 13], který nemůže být přičten k 1, 2, a 8.

13.2 Rekurze I

Rekurze je technika, při které funkce volá (s jinými parametry) samu sebe. Funkci countdown(n) z odstavce 5.4 můžeme s pomocí rekurze zapsat takto:

def countDown(n):       
    if n < 1:         # omezující podmínka (základní případ)          
        return print("Nemelem")
    print(n)          # melem, n=0 nebo n>n
    countDown(n-1)    # rekurzivní volání se změnou argumentu 

Správně definovaná rekurze vyhovuje těmto dvěma požadavkům:

• Má deklarovaný základní případ u kterého opakovaný výpočet končí.
• Hodnota argumentu rekurzivního volání směřuje k hodnotě základního případu

Pokud by rekurzivní volání nenarazilo na základní případ, šlo by o nekonečnou rekurzi s neúměrným nárokem na paměť počítače.Tuto situaci si Python sám ošetří tak, že po určitém počtu opakování výpočet zastaví.

V matematice známý pojem faktoriál čísla n neboli n faktoriál: (n!) je označení pro součin souvislé číselné řady 1 až n:
n! = n * (n-1) * (n-2) * ... *1   Ukážeme si jeho různé vyjádření:

Matematická definice:

0! = 1                             # faktoriál nuly = 1
n! = n(n-1)

Vyjádření pomocí iterace while...

def fact_w(n):
    f, i = 1, 0                    # hromadné přiřazení
    while i < n :
       i += 1; f = f*i             # rozšířené přiřazení
    return f

Vyjádření pomocí iterace for...

def fact_f(n):
    f = 1
    for i in range(1, n+1):   # range končí před koncovou mezí
	f = f*i
    return f

Vyjádření pomocí rekurze

def fact_r(n):
    if n < 2:                 # základní případ)
        return 1
    return n * fact_r(n-1)    # rekurzivní volání funkce 

Opakovaný výpočet pomocí rekurze je někdy pomalejší než výpočet pomocí iterace. Na konci odstavce 13.3.2 si ukážeme výpočet Fibonacciho čísla rekurzí, iterací a rychlý výpočet pomocí memoizace.

Má se za to, že každé rekurzivní řešení lze vyjádřit iterační smyčkou a naopak. Oběma způsobům je společná existence mezní podmínky, určující konec opakovaného výpočtu.
Nekonečná rekurze může skončit krachem systému, zatímco nekonečná iterace je odchycena a ukončena Pythonem.

13.3 Rekurze II

K vytvoření součtu všech čísel v našem rekurzivním seznamu s vnořeným seznamem potřebujeme traverzovat seznamem, navštívit každou číselnou položku uvnitř vnořené struktury a připočítávat číselné hodnoty k našemu součtu.

Potřebný program pro vytvoření součtu čísel v seznamu s vnořeným seznamem je díky rekurzi překvapivě krátký:

def recursive_sum(nested_num_list):      (vnořený seznam)
    sum = 0
    for element in nested_num_list:
        if type(element) == type([]):  # je-li položkou seznam
            sum = sum + recursive_sum(element)
        else:
            sum = sum + element
    return sum

Tělo fce se skládá hlavně ze smyčky for, která traverzuje seznamem nested_num_list. Je-li položkou seznamu numerická hodota nikoliv seznam (větev else), přičte se číslo jednoduše k proměnné sum. Je-li položkou seznam, potom je opět volána fce recursive_sum pro argument, jímž je vnořený seznam. Příkaz uvnitř těla funkce, jímž je volána táž funkce, se nazývá rekurzivní volání.

Poněkud komplikovanější úlohou je nalezení největší hodnoty v seznamu s vnořeným seznamem. Následující definice funkce obsahuje doctest (viz kap. 3.8), kterým si jednak ilustrujeme řešený problém a zároveň ověříme správnost naší funkce:

def recursive_max(nested_num_list):
    """
    >>> recursive_max([2, 9, [1, 13], 8, 6])
    13
    >>> recursive_max([2, [[100, 7], 90], [1, 13], 8, 6])
    100
    >>> recursive_max([2, [[13, 7], 90], [1, 100], 8, 6])
    100
    >>> recursive_max([[[13, 7], 90], 2, [1, 100], 8, 6])
    100
    """
    
    largest = nested_num_list[0]
    while type(largest) == type([]):
        largest = largest[0]

    for element in nested_num_list:
        if type(element) == type([]):
            max_of_elem = recursive_max(element)
            if largest < max_of_elem:
                largest = max_of_elem
        else:                 # element is not a list
            if largest < element:
                largest = element

    return largest

Čertovým kopýtkem tohoto problému je určení numerické hodnoty pro inicializaci proměnné largest. Nemůžeme jednoduše zadat, že je to nested_num_list[0], protože by touto položkou mohlo být jak číslo, tak seznam. Problém je řešen použitím smyčky while, která přiřadí proměnné largest první číselnou hodnotu bez ohledu na hloubku jejího vnoření.

13.3.1   Nekonečná rekurze

Při rekurzivním volání téže funkce se generuje řada výsledků, z nichž jeden má být určen jako výstup volání posledního. Takový výsledek se nazývá základní případ (base case). Bez základního případu dostaneme nekonečnou rekurzi. Tato situace je technicky ošetřena tak, že se Python zastaví po dosažení implicitně nastavené hloubky rekurze (1000 cyklů) a vrací chybu při běhu programu.

Ve funkci recursive_sum je počet rekurzivních volání určen počtem prvků v seznamu. Základní případ zde poskytuje skrytá funkce next() idiomu FOR i IN iterable (viz odst. 13.5 Iterátory definované třídou). Ve funkci countdown(n) (s koncovou rekurzí) je základním případem hodnota n = 0.

Příkladem nekonečné rekurze budiž tato funkce:

infinite_recursion.py

def recursion_depth(number):
    print("Recursion depth number {}." .format(number))
    recursion_depth(number + 1)

recursion_depth(0)

Ve stejném adresáři, ve kterém máte uložený svůj program, zapište na příkazový řádek:

F:/codetest/> python infinite_recursion.py

Po bezmocném sledování ubíhajících řádků na monitoru se po chvíli dočkáte následujícího konce záznamu:

File "infinite_recursion.py", line 3, in recursion_depth
   recursion_depth(number + 1)
RuntimeError: maximum recursion depth exceeded

Nekonečná rekurze může být těžko něčemu prospěšná, takže si při každé deklaraci rekurzivního volání bedlivě ohlídáme okrajové podmínky, vytvářející základní případ.

13.3.2   Koncová rekurze

Když se rekurzivní volání objeví na posledním řádku těla funkce, označujeme jej jako koncovou rekurzi.

Zde je koncová rekurze použita u funkce countdown:

def countdown(n):
    if n == 0:
        print("Blastoff!")
    else:
        print(n)
        countdown(n-1)

Mnohé dobře známé matematické funkce jsou definovány rekurzivně. Například Fibonacciho číslo, nebo fibonacciho sekvence, definovaná:

fibonacci(0) = 1
fibonacci(1) = 1
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

To lze také snadno přepsat do Pythonu:

def fibonacci (n):
    if n == 0 or n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

Koncová rekurze je v Pythonu považována za špatnou techniku, protože používá více systémových zdrojů než ekvivalentní iterativní řešení. Volání fibonacci(500) uvede interpreta Pythonu do rozpaků.

Mnohem rychlejší než rekurzivní verze je verze iterační, která by mohla vypadat takto:

def fiboiter (n):
    old, new = 0, 1
    if n == 0:
        return 0 
    for i in range(n-1):
	old, new = new, old + new
    return  new

Vyzkoušejte volání fiboiter(500) a budete příjemně překvapeni.
Při cvičení si zkusíte napsat iterační verzi funkce factorial a v dalším odstavci si ukážeme memoizovanou alternativu funkce fibonacci, která je ze všech tří verzí nejrychlejší.

13.4 Memoizace

Když jsme si v předchozím odstavci pohrávali s funkcí fibonacci, mohli jsme si všimnout, že čím větší argument jsme použili, tím déle trvalo provádění funkce. Se zvětšujícím se argumentem časové nároky velmi rychle rostly. Na jednom z našich počítačů končí fibonacci(20) okamžitě, fibonacci(30) zabere asi vteřinu a fibonacci(40) trvá zhruba věčnost.

Abychom pochopili proč, pohleďme na toto schéma volání funkce fibonacci(4):

Schéma zobrazuje sadu funkcí v rámečcích se šipkami, ukazujícími na volané funkce. Nejvýše umístěná fce, fibonacci(4) volá fibonacci(3) a fibonacci(2). Fce fibonacci(3) zas volá fibonacci(2) a fibonacci(1). A tak dále.

Spočítejme, kolikrát je voláno fibonacci(0) a fibonacci(1). Je to řešení neefektivní a rychle se zhoršuje při zvětšujícím se argumentu.

Dobrým řešením, zvaným memoizace (memoization), je ukládat si záznamy (hints) o spočítaných hodnotách do slovníku pro potřebu dalšího použití. Takovýmto záznamům říkejme třeba náznaky. Zde vidíme realizaci funkce fibonacci s podporou náznaků:

memo = {0:0, 1:1}
def fibomem(n):
    if n not in memo:
        memo[n] = fibomem(n-1) + fibomem(n-2)
    return memo[n]

Slovník memo zaznamenává fibonacciho čísla, která již známe. Začínáme pouhými dvěma páry: 0 ukazuje na 0, 1 na 1.

Kdykoli je funkce fibomem volána, prozkoumá svůj slovník, zda neobsahuje výsledek. Jestliže ano, vrací výsledek bez dalších okolků. Jestliže ne, počítá novou hodnotu. Tato hodnota je přidána do slovníku před tím, než se funkce vrátí k rekurzivnímu volání.

S použitím této verze náš počítač spočítá fibonacci(50) v jednom oka mžiku.

>>> fibomem(100)
354224848179261915075

Alternativní způsob výpočtu Fibbonacciho čísla pomocí memoizace představuje výpočet s podporou dekorátorů (viz kap.12.7 a 12.8)

def memoize(fun):                # dekorátorová funkce
    memo = {}
    def wrapper(x):
        if x not in memo:            
            memo[x] = fun(x)
        return memo[x]
    return wrapper
    
@memoize                         # dekorace funkcí
def fibomem(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibomem(n-1) + fibomem(n-2)

# >>> fibomem(100) ==> 354224848179261915075

class Memoize:                    # dekorátorová třída
    def __init__(self, fn):
        self.fn = fn
        self.memo = {}
    def __call__(self, *args):
        if args not in self.memo:
            self.memo[args] = self.fn(*args)
        return self.memo[args]

@Memoize                         # dekorace třídou
def fibomem(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibomem(n-1) + fibomem(n-2)

# >>> fibomem(100) ==> 354224848179261915075

Všechny tři způsoby používají slovník memo a podmínku if x not in memo:.

13.5 Iterátory definované třídou

Iterátorem v tomto případě je instance třídy s definovanými metodami __iter__()  a next(). Takto definovaný iterátor líný výpočet neprovádí.

Jako příklad si uvedeme skript, který si poté pustíme v konzole:

class Count: 
    def __init__(self, m):
        self.m = m-1
        self.n = 0
    def __iter__(self):
        return self
    def __next__(self):
        if self.n <= self.m:
            cur, self.n = self.n, self.n + 1
	    return cur
        else:
            raise StopIteration() 

>>> cnt = Count(5)     # instance třídy a zároveň iterátor
>>> next(cnt)            # první iterace
0 
>>> for i in cnt: print(i, end=" ") 
1 2 3 4                  # opakovaná iterace pro zbytek členů
>>> for in cnt: print(i, end=" ") 
...                      # zdvořilé mlčení, iterátor je prázdný

Alternativa funkce squares(start, stop) ve tvaru uživatelského iterátoru může mít tento tvar:

class Squares(object): 
    def __init__(self, start, stop):
        self.start = start
        self.stop = stop
    def __iter__(self):
        return self
    def __next__(self):
        if self.start >= self.stop:
            raise StopIteration
        current = self.start * self.start
        self.start += 1
        return current 

>>> sqr = Squares(4,8)          # instance třídy a zároveň iterátor
>>> 
>>> for i in sqr: print(i, end=" ") 
16 25 36 49                     # dychtivá (eager) iterace
>>> for in sqr: print(i, end=" ") 
...                             # zdvořilé mlčení, iterátor je prázdný

13.6 Chyby a výjimky

Jak už bylo uvedeno v první kapitole, mohou se při kontrole zdrojového kódu kompilací vyskytnout chyby skladebné (syntaktické) a při interpretaci objektového kódu za běhu programu (run-time) takzvané chyby výjimkové, neboli výjimky (exceptions).
Při výskytu těchto událostí dojde k zastavení výpočtu a případně k poskytnutí stručné informace o (možné) příčině události.

Příklad chyby skladebné

>>> print(55/2))
  File "<stdin>", line 1
    print(55/2))
               ^
SyntaxError: unmatched ')'         # neshodný počet závorek     

Při výskytu takovéto chyby se zastaví běh kompilace a zobrazí se informace s označením místa na řádku, kde k chybě došlo (^)

Příklad výjimkové události

Při výskytu předpokládané výjimky (např. dělení nulou) zastaví Python běh programu a pokusí se zobrazit informaci o vzniklé chybě:

>>> print(55/0)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
ZeroDivisionError: division by zero

Poznámka: Výjimky jsou definovány jako instance třídy, odvozené od třídy BaseException. Úplný výpis vestavěných výjimek Pythonu lze nalézt v dokumentaci Built-in Exceptions.

13.6.1   Vlastní výjimky

Kromě standardních (built-in) výjimek je možné používat vlastní výjimky a to deklarací:

• sledované podmínky (např. if x < 0)
• následné reakce při případném nesplnění podmínky - tato reakce má standardní skladbu:
  raise Název_chyby ("Info pro uživatele");
  pro název chyby se použije zavedené systémové označení - viz Built-in Exceptions

Klauzulí raise lze vyvolat výjimku kdykoliv to je potřebné:

>>> x = "Hello!"
>>> if not type(x) is int:                       # sledovaná podmínka
...     raise TypeError(": Jen celá čísla!")     # reakce programu

Traceback (most recent call last):               # chybové hlášení>
  File "<stdin>", line 2, in <module>
TypeError: : Jen celá čísla!                     # sledovaná podmínka

Další příklad:

>>> x = -5
>>> if x < 0 : 
...    raise Exception(": Pouze x > 0!")

Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
Exception: : Pouze x > 0!

Ověření správnosti uživatelem zadaného výrazu lze také zajistit předsazeným příkazem assert:

>>> x = -5
>>> assert x > 0                    # lze doplnit komentář

Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError           # název chyby je zde dosazen automaticky

Jiný příklad s komentářem:

>>> import sys
>>> assert ('linux' in sys.platform), "Tento kód běží jen ve Windows!"
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
AssertionError: Tento kód běží jen ve Windows!

Použití příkazu 'assert' je výhodné při ladění (debugging) kódu, tedy při vyhledávání potenciálně chybujícího místa kódu.
Příkaz 'assert' je vhodný pro jednoduché ověření přijatého údaje:

>>> spin = int(input('Zadej kladné číslo: '))   - viz Poznámka
Zadej kladné číslo: -7
>>> assert (spin > 0),         'Jen kladná čísla, prosím!'
Traceback (most recent call last):
  File <stdin>, line 1, in <module>
AssertionError: Jen kladná čísla, prosím!

Poznámka: Výstup z funkce 'input' je nutné konvertovat na formát 'integer'

13.6.2   Ošetření výjimek

Chceme-li zařídit aby provádění programu pokračovalo i po výskytu určité chyby, provedeme takzvané "ošetření výjimky" (exception handling).
To zpravidla spočívá v použití klauzule try v kombinaci s klauzulemi assert, except, else či finally s následujícími významy:

try: 
    uvádí ověřovaný blok kódu - provedou se všechny výrazy, 
    pokud se nenarazí na výjimku
assert: 
    uvádí ověřovací podmínku, která rozdělí tok výpočtu do dvou
    větví - pokračování programu nebo chybové hlášení	
except:
    následný blok kódu ošetří chybu či nesplněnou podmínku z bloku 'try' nebo 'assert'
else: 	
    uvádí blok kódu při splnění podmínky v bloku 'try'
finally:
    následný kód se provede vždy, bez ohledu na 'výjimky' 	

Klauzulí assert a except může být v případě potřeby více, případně se jedna klauzule může vztahovat na více výjimek.
Klauzule assert je neaktivní, použije-li se při spuštění programu flag -o nebo je příponou souboru ~.pyv (místo ~.pyc).

Problematické rozšíření příkladu se zadávanou hodnotou 'spin':

# in_text/try_spin_int.py

try:
    spin = int(input('Zadej kladné číslo: '))
    assert (spin > 0), 'Jen kladná čísla, prosím!'

except:
    spin = int(input('Zadej kladné číslo: '))
	
print("Přijato: ", spin) 	

Evokací v konzole IDLE (F5) zjistíme, že některý chybný vstup je ignorován:

===== RESTART: F:\Codetest\HowTo\ch-13\spin.py ====
Zadej kladné číslo: "šle"              # ticho po pěšině
Zadej kladné číslo: -5
Přijato : -5
>>>   Tuto nepovedenou proceduru napravíme v cvičení 13.8.6                              

Pěkný příklad řešení kořenů kvadratické rovnice:

import math
 
def KvadrRovnice(a, b, c): 
    try: 
        assert a != 0, "Chyba, nulový kvadratický člen"
        D = (b*b - 4*a*c)                      # hodnota diskriminantu 
        assert D > 0, "Chyba, diskriminant je menší než 0"
        r1 = (-b + math.sqrt(D))/(2 * a)       # první kořen rovnice  
        r2 = (-b - math.sqrt(D))/(2 * a)       # druhý kořen rovnice 
        print("Kořeny rovnice jsou: ", r1, "", r2) 
    except AssertionError as msg:              # vestavěná formule  
        print(msg) 

Klauzule except tiskne komentáře z klauzulí assert.

>>> KvadrRovnice(-1, 5, -6)
Kořeny rovnice jsou : 2.0  3.0
>>> KvadrRovnice(0, 5, -6)
Chyba, nulový kvadratický člen
>>> KvadrRovnice(1, 1, 6)
Chyba, diskriminant je menší než 0

Kombinaci try, except, else lze použít spolu s deklarací třídy pro ošetření vlastní výjimky, jíž v tomto případě je zadání krátkého hesla:

class MyExcept(Exception):
    def __init__(self, length, atleast):
	Exception.__init__(self)
	self.length = length
	self.atleast = atleast
	
try:
    s = input("Zadej heslo: ")
    if len(s) < 7:
        raise MyExcept(len(s), 7)
except MyExcept as x:
    print ("MyExceptError: Heslo je krátké ({0}<{1})"
	           .format(x.length, x.atleast))
else:
    print ("Heslo je v pořádku")	

Jak vidno, naše třída dědí z vestavěné třídy Exception. K použití deklarované třídy dochází při (opětovné) evokaci celého bloku kódu v aplikaci IDLE:

========== RESTART: F:\Codetest\HowTo\aTrampol.py ==========
Zadej heslo: woke
MyExceptError: Heslo je krátké (4<7)
>>>
========== RESTART: F:\Codetest\HowTo\aTrampol.py ==========
Zadej heslo: BarelPanel
Heslo je v pořádku
>>>

13.7 Glosář

13.8 Cvičení