previous up next hi end end

13. Rekurze a iterace

  1. Rekurzivní datové struktury
  2. Rekurze II
  3. Memoizace
  4. Iterátory
  5. Generátory
  6. Chyby a výjimky
  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 II

Tento text je pokračováním části 4.5 - Rekurze I.

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):
    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. 5.10), 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í.

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.4 Iterátory). 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:

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.

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)

Kód pro fibonacci je příkladem koncové rekurze.

Koncová rekurze je však 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í fibointer(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.3 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.3.11 a kap. 12.12):

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.4 Iterátory

Iterátor je interní objekt, jenž vlastní metody __iter__() a __next__(), které vracejí hodnotu následného elementu při každé své invokaci.

Iterátor se vytváří čtverým způsobem:

  1. Použitím funkce iter - viz kap. 4.6.
  2. Skrytě, pro interní potřebu idiomu for... či funkce open(...), min(), max(), map(), filter(), zip(), enumerate() a reversed().
  3. Pomocí generátorové funkce a generátorového výrazu, jejichž výstupem jsou iterátory, které provádějí takzvaný líný výpočet (lazy evaluation).
  4. Vytvořením třídy s definovanými metodami __iter__() a next(). Takto definovaný iterátor líný výpočet neprovádí.

Iterátory definované třídou

Iterátorem v tomto případě je instance třídy s definovanými metodami __iter__()  a next().

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

class CountTo: 
    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 = CountTo(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.5 Generátory

Generátor je objekt, vytvořený aplikací generátorového výrazu, případně voláním generátorové funkce. Generátor je iterátor, který místo hotových objektů ukládá instrukce pro jejich individuální vytvoření při iteraci.

Generátorový výraz

Generátorový výraz je vytvořen komprehenci entice (viz 8.10).

>>> st = "abakus"                     # iterovatelný řetězec - iteráble 
>>> stv = (i for i in st)             # generátorový objekt - iterátor
>>> for i in st: print (i, end=" ")   # dychtivá (eager) iterace iteráblu
a b a k u s 
>>> for i in stv: print (i, end=" ")  # líná (lazy) iterace iterátoru
a b a k u s 

Generátorový výraz lze vytvořit i s použitím idiomu for pro funkci range(~). Zde funkce range() vytvoří iterovatelný objekt, který se komprehencí přemění na iterátor:

>>> gv = (i*i for i in range(5))        # generátorový objekt - iterátor 
>>> for i in gv: print (i, end=", ")    # líná (lazy) iterace 
0, 1, 4, 9, 16 

Generátorová funkce

Generátorová funkce musí obsahovat alespoň jeden příkaz yield. Volání generátorové funkce vrací generátorový objekt, jenž je iterátorem s přímo použitelnou funkcí next(~) či metodou __next__() - stejně jako v předchozím případě:

def count_to(m):
   n = 0
   while n <= m:
      yield n              # poskytuje elementy iterátoru
      n += 1
========== RESTART: F:\Codetest\HowTo\trump.py ==========

>>> ct = count_to(5)                  # generátorový objekt, iterátor
>>> next(ct)                          # 1. krok dychtivé iterace
0
>>> ct.__next__()                     # 2. krok dychtivé iterace
1
>>> for i in ct: print (i, end=" ")   # líná (lazy) iterace
2 3 4 5
>>> next(ct)
StopIteration                         # iterátor je prázdný

Generátorový objekt vytvoří i tato generátorová funkce:

def squares(start, stop): 
    for i in range(start, stop):
        yield i * i

Výpočet řady Fibonacciho čísel můžeme provést pomocí následujícího generátoru:

def fibonacci():
    a, b = 0, 1 
    while True:  # nekonečná smyčka! 
        yield a
        a, b = b, a+b 

Generátor s nekonečnou smyčkou voláme pro konkretní mez:

>>> f = fibonacci() 
>>> type(f)        # -->  <class 'generator'> 
>>> f.__next__()   # -->  0
>>> next(f)        # -->  1    alternativní verze
...
>>> for i in range(7): print(next(f), end=" ")
1 2 3 5 8 13 21
>>> f.__next__()   # -->  34 

Generátorový výraz a generátorová funkce vrací generátorový objekt, který je pomalu (líně) vyhodnocovaným iterátorem.

Líný výpočet

Generátorové objekty podporují líný výpočet (lazy evaluation), při kterém se odkládá výpočet výrazu až do chvíle jeho potřeby. Důsledkem je zmenšená potřeba zdrojů (paměti) při zvýšeném výkonu procedury.

Lze sestavit potenciálně nekonečné struktury, např. smyčky - viz fibonacci().

Líný výpočet se obtížně kombinuje s imperativními strukturami jako je ošetření výjímek nebo vstup/výstup; může vytvářet "space leaks" (viz).

Příkladem procedury, uplatňující líný výpočet, je použití slovníku v kapitole 11.7 Switch case, kde u funkce kalkul(oprerátor, x,y) je řešeno částečné ošetření výjimek.


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.

Vlastní výjimky

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

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!

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 "", line 1, in <module>
AssertionError: Jen kladná čísla, prosím!

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


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

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 uvedený skript použijeme jen pro jeden chybný vstup:

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

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ář

datová struktura (data structure)
Uspořádání dat pro jejich snadnější použití.
rekurzivní definice (recursive definition)
Definice, která se odkazuje sama na sebe. Aby byla smysluplná, musí obsahovat nerekurzivní základní případ. Tímto se liší od definice v kruhu. Rekurzivní definice často skýtají elegantní způsob vyjádření složitých datových struktrur.
rekurze (recursive call)
Příkaz v rekurzivní funkci, který je volá právě prováděnou funkci (to jest samu sebe).
základní případ (base case)
Větev podmíněného příkazu v rekurzivní funkci, který nevede k rekurzivnímu volání.
nekonečná rekurze (infinite recursion)
Funkce, která rekurzivně volá sama sebe, aniž by dospěla k základnímu případu. Způsobí chybu při běhu programu.
koncová rekurze (tail recursion)
Rekurzivní volání umístěné na konci definice funkce. Tato metoda se příliš nedoporučuje, protože bývá méně účinná než iterativní funkce (see the Wikipedia article on tail recursion for more information).
výjimka (exception)
Chyba při běhu programu, pro níž je k dispozici definice třídy.
ošetřit výjimku (handle an exception)
Zabránit registrované chybě (výjimce) aby ukončila běh programu s použitím příkazů try a except.
vyvolat výjimku (raise)
Aktivovat výjimku s použitím příkazu raise.

13.8 Cvičení

  1. Napište funkci recursive_min, která vrátí nejmenší číselnou hodnotu seznamu s vnořenými seznamy:
    def recursive_min(nested_num_list):
        """
        >>> recursive_min([2, 9, [1, 13], 8, 6])
        1
        >>> recursive_min([2, [[100, 1], 90], [10, 13], 8, 6])
        1
        >>> recursive_min([2, [[13, -7], 90], [1, 100], 8, 6])
        -7
        >>> recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6])
        -13
        """
    
    Funkce by měla vyhovět všem doctestům.
  2. Napište funkci recursive_count, která vrátí počet výskytů číselné hodnoty target v seznamu nested_number_list:
    def recursive_count(target, nested_num_list):
        """
        >>> recursive_count(2, [2, 9, [2, 1, 13, 2], 8, [2, 6]])
        4
        >>> recursive_count(7, [[9, [7, 1, 13, 2], 8], [7, 6]])
        2
        >>> recursive_count(15, [[9, [7, 1, 13, 2], 8], [2, 6]])
        0
        >>> recursive_count(5, [[5, [5, [1, 5], 5], 5], [5, 6]])
        6
        """
    
    Funkce vyhoví všem doctestům?
  3. Napište funkci flatten, která vrátí jednoduchý seznam, obsahující všechny honoty z nested_number_list:
    def flatten(nested_num_list):
        """
        >>> flatten([2, 9, [2, 1, 13, 2], 8, [2, 6]])
        [2, 9, 2, 1, 13, 2, 8, 2, 6]
        >>> flatten([[9, [7, 1, 13, 2], 8], [7, 6]])
        [9, 7, 1, 13, 2, 8, 7, 6]
        >>> flatten([[9, [7, 1, 13, 2], 8], [2, 6]])
        [9, 7, 1, 13, 2, 8, 2, 6]
        >>> flatten([[5, [5, [1, 5], 5], 5], [5, 6]])
        [5, 5, 1, 5, 5, 5, 5, 6]
        """
    
  4. Napište funkci readposint(), která vyzve uživatele k zadání kladného celého čísla a to případně opakovaně, dokud není zadána korektní vstupní hodnota.
    V ukázce se zadávanou hodnotou 'spin' nám procedura chodí korektně jen pro jeden chybný vstup, "což není to pravé ořechové".
    Pro ověření správnosti uživatelského vstupu použijte mechanizmus ošetření výjimky.
  5. Přepište funkci factorial s použitím iterace místo rekurze. Volejte svou funkci pro argument 1000 a změřte jak rychle vrátí výsledek.

previous up next hi end end