previous up next hi end end

13. Rekurze a iterace

  1. Rekurzivní datové struktury
  2. Rekurze
  3. Náznaky
  4. Iterace
  5. Iterátory
  6. Generátory
  7. Chyby a výjimky
  8. Glosář
  9. 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é. Organizace dat s cílem jejich snadného použití se nazývá datová struktura.

Je čas voleb a my pomáháme počítat přicházející hlasy. Hlasy přicházející z jednotlivých volebních mísností, okrsků, měst, zemí a států jsou někdy oznamovány jako celkový součet hlasů, někdy jako výčet mezisoučtů. Přemýšleje kterak nejlépe uspořádat spočítané hlasy, rozhodneme se použít seznam s vnořenými seznamy, který bychom definovali následovně:

Seznam s vnořenými seznamy čísel je seznam, jehož položkami jsou:

  1. čísla
  2. seznam s vnořenými seznamy čísel

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

Procesu, při kterém funkce volá samu sebe, se říká rekurze a takové funkce jsou rekurzivní. Příkaz, ve kterém volá funkce samu sebe, se nazývá rekurzivní volání.

Rekurze je jedním z nejkrásnějších a nejelegantnějších nástrojů v programování.

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([]): # or: if isinstance(element, list):
            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. 4.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_mraax([[[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.6 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 koncová rekurze.

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 factorial je definován takto:

0! = 1
n! = n(n-1)

To lze snadno v Pythonu zapsat:

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

Jiný dobře známý matematický výraz je 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)

Jak factorial tak fibonacci jsou příklady 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í factorial(1000) překročí maximální hloubku rekurze. Zkuste si fibonacci(35) a na výsledek si docela počkáte, nicméně nebojte se, dočkáte se ho.

Při cvičení si zkusíte napsat iterační verzi funkce factorial a v dalším odstavci si ukážeme lepší verzi funkce fibonacci.

13.3 Náznaky

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 schema volání funkce fibonacci(4):

Schema 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 je ukládat si záznamy o spočítaných hodnotách do slovníku pro potřebu dalšího použití. Takovýmto záznamům říkejme náznaky (hints). Zde vidíme realizaci funkce fibonacci s použitím náznaků:

previous = {0:0, 1:1}

def fibonacci(n):
    if n in previous:
        return previous[n]
    else:
        new_value = fibonacci(n-1) + fibonacci(n-2)
        previous[n] = new_value
        return new_value
Slovník previous 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 fibonacci volána, prozkoumá svůj slovník, zda neobsahuje výsledek. Jestliže ano, vrací výsledek bez dalších okolků. Jestliže ne, potom 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(100) v jednom oka mžiku.

>>>fibonacci(100)
354224848179261915075

13.4 Iterace

V matematice je za iteraci považován opakovaný, postupně se zpřesňující výpočet určité hodnoty, přičemž se přibližná mezihodnota použije jako východisko pro výpočet hodnoty následné, přesnější - viz Newtonova metoda v kapitole 5.11.

V programování je za iteraci považován rovněž opakovaný výpočet, ale provedený postupně pro jednotlivé členy iterovatelné řady argumentů.

Iterovatelnou řadou argumentů jsou v Pythonu kontejnery string, list, tuple, set, frozenset, dictionary (dict), bytearray a rovněž soubor, otevřený funkcí open("file").

Pomocí smyčky for můžeme volat jednotlivé členy iterovatelného objektu a nakládat s nimi dle ctěné libosti:

    FOR i in ITERABLE:
        do something, např. print(i)	

Tato interakce je umožněna skrytým aparátem jazyka Python a jeho překladače, který si v následujícím textu přiblížíme. Ujasníme si pojmy jako iterable, iterátor, generátor a další.

Iterable je iterovatelný objekt s definovanou metodou __iter__().

O tom, že naše známé kolektory jsou touto metodou vybaveny a že to tedy jsou 'iterábly', se přesvědčíme sekvencí

>>> dir(zkoumany_objekt)
jejímž výstupem je seznam metod a funkcí zadaného objektu, v němž je metoda __iter__() uvedena.

13.5 Iterátory

Iterátor je objekt, který podporuje tak zvaný "iterační protokol", což znamená, že má definovanou metodu __iter__() a funkci __next__(), která vrací následnou hodnotu při každé své invokaci.

Je to "stínová" kopie iteráblu (iterovatelného objektu), která postupně odevzdává své prvky a "škrtá je ze seznamu". Říkáme, že iterátor je objekt, který si je vědom svého stavu. Jeho skrytý pointer ukazuje na prvek, který je právě na řadě.

Iterátory jsou výhodné tím, že snižují spotřebu paměti; vyprázdněný iterátor je "garbage collected".

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

  1. Skrytě, pro interní potřebu idiomu for... či funkce open(...), případně funkce min(), max(), ....
  2. použitím funkce iter(iterable).
  3. Vytvořením třídy s definovanými metodami __iter__()  a   next(). Takto definovaný iterátor líný výpočet neprovádí.
  4. Pomocí generátorové funkce a generátorového výrazu, jejichž výstupem jsou iterátory, které provádějí tak zvaný líný výpočet (lazy evaluation).

Interní iterátor

Při použití idiomu "FOR i IN iterable:do something" dochází k tomu, že si překladač nejprve vytvoří iterační objekt (iterátor), který je vybaven funkcí next(). Tato funkce je opakovaně evokována idiomem "FOR i IN iterable:".

Funkce open("soubor.txt") si rovněž vytváří svůj iterátor:

>>> f = open("c:/Abakus/readme.txt")  # iterátor 
>>> next(f)     # první řádek souboru
>>> next(f)     # další řádek souboru
>>> for i in f: print(i, end="")  # zbývající řádky souboru

Vlastní iteráror

Na iterovatelné objekty lze aplikovat funkci iter(), která je přetvoří na iterátor:

>>> li = [1, 2, 3] # iterovatelný seznam s __iter__()
>>> ili = iter(li) # iterátor s __iter__() i s next()
>>> dir(ili) # viz

S iterátorem lze provádět iteraci opakovaným voláním funkce next()
>>> next(ili)
1 
>>> next(ili)
2 
>>> next(ili)
3 
>>> next(ili)
Traceback (most recent call last):
File "<interactive input>", line 1, in <module>
StopIteration
>>> 

Poté, co se vyčerpá "délka iterace", ukončí se provádění smyčky; iterátor je "mrtvý brouk":

>>> for i in ili: print (i) # --> zdvořilé mlčení

Iterátor je rovněž iterovatelný objekt. Iteraci můžeme provést buď najednou ve smyčce FOR nebo postupně opakovaným voláním funkce next().

Iterátor ili je v této chvíli nepoužitelný ale můžeme jej obnovit:

>>> ili = iter(ili) # a máme nabito

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 překladači:

class CountTo: 
    def __init__(self, m):
        self.m = m
        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)
0 
>>> for i in cnt: print(i, end="") 
1 2 3 4 5          # dychtivá (eager) iterace
>>> 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="") 
4 9 16 25 36 49         # dychtivá (eager) iterace
>>> for in sqr: print(i, end="") 
...          # zdvořilé mlčení, iterátor je prázdný

13.6 Generátory

Generátorový výraz

Generátorový výraz je podobný komprehenci seznamu, s tím rozdílem, že je uzavřen v kulatých závorkách.

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

Generátorovým výrazem je i tento objekt:

(i*i for i in range(start, stop)) 

Generátorová funkce

Generátorová funkce musí obsahovat alespoň jednu instrukci yield, např:

>>> def count_to(m): 
...     n = 0
...     while n <= m:
...         yield n
...         n += 1
  
>>> ct = count_to(5)       # generátorový objekt, iterátor
>>> for in in ct: print (i, end="") # líná (lazy) iterace

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 iterátorem.

Funkce 'range'

Funkce range() vrací rovněž generátorový objekt, který své jednotlivé členy generuje postupně, na požádání. Má konstantní nárok na použití paměti, neboť ukládá pouze výsledek posledního volání.

Pro vytvoření seznamu či entice se používá idiom

>>> ln = list(range(5))
>>> ln
[0,1,2,3,4]
>>> tp = tuple(range(5))
>>> tp
(0,1,2,3,4)
>>> 

Libovolný prvek generátorového objektu můžeme vyvolat metodou .__getitem__(n):

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


13.7 Chyby a výjimky

Jak už bylo uvedeno v první kapitole, mohou se při kompilaci kódu vyskytnout chyby skladebné (syntaktické) a chyby za běhu programu tak zvané "run-time errors". Oba typy chyb jsou události, které Python umí ošetřit.

Syntaktické chyby

Při výskytu skladebné chyby se zastaví běh kompilace a zobrazí se informace s uvedením inkriminovaného řádku a označením místa na řádku, kde k chybě došlo (celé slovo před znakem ^ - zde za slovem True má být dvojtečka):

>>> while True print ("Nazdar!")
   File "<stdin>", line 1
     while True print ("Nazdar!")
	            ^
 SyntaxError: invalid syntax     

Výjimky

Výjimka (exception) je systemizovaná chyba, k níž dojde při běhu programu. Výjimky jsou definovány jako třídy, odvozené od třídy BaseException. Úplný výpis těchto tříd lze nalézt na 5. Built-in Exceptions.

Kromě vestavěných (built-in) výjimek (např. TypeError, IndexError, ZeroDivisionError, ... ) je možné používat vlastní typ výjimky vytvořením třídy, odvozené od třídy Exception - viz 8.5 User defined exceptions.

Při výskytu systemizované chyby (např. dělení nulou) zastaví Python běh programu a zobrazí informaci o vzniklé chybě:

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

Chybové hlášení na poslední řádce se skládá ze dvou částí: název chyby (neboli třídy-výjimky) před dvojtečkou a podrobnosti o chybě za dvojtečkou.

Ošetření výjimek

Chceme-li zařídit aby po výskytu určité chyby pokračovalo provádění programu, provedeme tak zvané "ošetření výjimky" (exception handling).

To zpravidla spočívá v použití příkazu try a klauzule except (případně také else či finally ) dle následujícího schematu:

try: 
    do_something()
except:
    handle_excepton()
... 

Klauzulí 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:

... except(RuntimeError, TypeError, NameError):
... pass        # some activity

Pro klauzuli except s určitou standardní výjimkou platí, že tato klauzule se vztahuje také na všechny výjimky, které jsou z uvedené výjimky (třídy) odvozené.

Neuvedeme-li v klauzuli žádnou výjimku, pak tato klauzule platí pro všechny vestavěné výjimky, což nemusí být zrovna to pravé ořechové:

def bad_example:(number):
    try:
	return number / 0
    except: # slabá klauzule
	print("Máme chybu, nevíme jakou")
	
bad_example("aleš")
Máme chybu, nevíme jakou	

Příklad s try, except, else:

# Určení přítomnosti či nepřítomnosti souboru

def exists(filename):   # název souboru v uvozovkách
    try:
        f = open(filename)
    except OSError:		
        print ("Soubor nenalezen")
    else:  
        f.close() 
	print ("Soubor existuje a byl zavřen")

Sémantická výhrada: Zjišťovat přítomnost souboru tím, že jej dokážeme otevřít, je poněkud nemotorné. Jednak může dojít k aktualizaci časového razítka, druhak můžeme dostat nesprávnou odpověď jenom proto, že je soubor někde otevřen nebo že k němu nemáme oprávnění.

Vybranější způsob je pomocí metody isfile z modulu os.path:

if os.path.isfile("c:/temp/testdata.txt"):
...

Záměrné vyvolání výjimek

Když program narazí na omezující podmínku, můžeme pro případ jejího nesplnění přinutit program, aby vyvolal (raise) standardní výjimku. Následuje příklad, ve kterém se zkoumá zda uživatelem zadané číslo je nezáporné. Pokud je záporné, oznámí se výjimka.

# learn_exceptions.py

def get_age():
    age = int(input('Uveďte svůj věk: '))
    if age < 0:
       	raise ValueError("{0} není platná hodnota".format(age))
    return age

>>> get_age()
Uveďte svůj věk: -15
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "learn_exceptions.py", line 10, in get_age
    raise ValueError("{0} není platná hodnota".format(age)
ValueError: -15 není platná hodnota
>>>

Nebo lze raise použít i pro ošetření vlastní výjimky:

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

13.8 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 disposici 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.9 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ů 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]
        """
    
    Nezapomeňte na doctesty.
  4. Napište funkci readposint, která vyzve uživatele k zadání kladného celého čísla a vstup ověří. Ukázka průběhu může vypadat takto:
    >>> num = readposint()
    Please enter a positive integer: yes
    yes is not a positive integer.  Try again.
    Please enter a positive integer: 3.14
    3.14 is not a positive integer.  Try again.
    Please enter a positive integer: -6
    -6 is not a positive integer.  Try again.
    Please enter a positive integer: 42
    >>> num
    42
    >>> num2 = readposint("Now enter another one: ")
    Now enter another one: 31
    >>> num2
    31
    >>>
    
    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