11. Rekurze a výjimky

1. Entice a měnitelnost
2. Enticové přiřazení
3. Entice jako výstupní hodnoty
4. Čisté funkce a modifikátory podruhé
5. Rekurzivní datové struktury
6. Rekurze
7. Výjimky
8. Koncová rekurze
9. Generátor seznamu
10. Mini case study: tree (Unix)
11. Glosář
12. Cvičení

11.1 Entice a měnitelnost

Až dosud jsme poznali dva složené datové typy: řetězce, které jsou složené ze znaků, a seznamy, které se skládají z položek libovolného typu. Jeden z rozdílů, které jsme zaznamenali, je ten, že položky seznamu mohou být měněny, zatímco znaky řetězce být měněny nemohou. Jinými slovy, řetězce jsou neměnitelné a seznamy jsou měnitelné.

Entice (tuple), podobně jako seznam, je pořadí položek libovolného typu. Narozdíl od seznamu jsou však entice neměnitelné. Z hlediska skladby je entice řada hodnot, oddělených čárkou:

>>> tup = 2, 4, 6, 8, 10

I když to není nezbytné, je obvyklé uzavírat entice do oblých závorek.

>>> tup = (2, 4, 6, 8, 10)

Při tvorbě entice s jedinou položkou musíme připojit závěrečnou čárku:

>>> tup = (5,)
>>> type(tup)
<type 'tuple'>

Bez čárky by byl výraz (5) považován Pythonem za celé číslo v závorce.

>>> tup = (5)
>>> type(tup)
<type 'int'>

Odhlédneme-li od skladby, entice podporují stejné operace jako řetězce a seznamy. Indexový operátor vybere položku z entice:

>>> tup = ('a', 'b', 'c', 'd', 'e')
>>> tup[0]
'a'

Úsekový operátor vybere rozsah položek:

>>> tup[1:3]
'b', 'c')

Pokusíme-li se však změnit některou z položek přiřazením, dostaneme chybové hlášení:

>>> tup[0] = 'X'
TypeError: object doesn't support item assignment

Ovšem, i když nemůžeme měnit položky entice, můžeme je nahradit jinou enticí:

>>> tup = ('X',) + tup[1:]
>>> tup
'X', 'b', 'c', 'd', 'e')

Případně můžeme přeměnit entici na seznam, ten upravit a přeměnit jej zpátky na entici:

>>> tup = ('X', 'b', 'c', 'd', 'e') 
>>> tup = list(tup)
>>> tup
['X', 'b', 'c', 'd', 'e']
>>> tup[0] = 'a'
>>> tup = tuple(tup)
>>> tup
('a', 'b', 'c', 'd', 'e')

11.2 Enticové přiřazení

Občas bývá užitečné vzájemně vyměnit hodnoty dvou proměnných. Při použití běžného příkazu přiřazení musíme použít dočasnou proměnnou. Záměnu a a b provedeme například takto: (a,b musí být definováno!)

>>> a = "ahoj"
>>> b = 5
>>> temp = a
>>> a = b
>>> b = temp
>>> print a,b
5 ahoj

Máme-li to provádět často, je uvedený postup neohrabaný. Python poskytuje způsob enticového přiřazení, které tento problém řeší úhledně:

>>> a, b = b, a

Na levé straně je entice proměnných, na pravé straně je entice hodnot. Každá hodnota je přiřazena své příslušné proměnné. Všechny výrazy na pravé straně se provedou před tím, než jsou přiřazeny. Tato vlastnost činí z enticového přiřazení všestranný nástroj.

Počet proměnných na levé straně musí zajisté být stejný jako na pravé straně:

>>> a, b, c, d = 1, 2, 3
ValueError: need more than 3 values to unpack

11.3 Entice jako výstupní hodnoty

Entice může být výstupní hodnotu funkce. Můžeme například napsat funkci, která zamění dva parametry:

def swap(x, y):
    return y, x

Nebo můžeme přiřadit výstupní hodnotu funkce entici s dvěma proměnnými: (a,b musí být definováno!)

a, b = swap(a, b)

Při definici funkce swap jsme se mohli dopustit tohoto snadného omylu:

def swap(x, y):     # incorrect version!
    x, y = y, x

Když tuto funkci zavoláme: (a,b musí být definováno!)

swap(a, b)

potom k žádné záměně nedojde. Záměnné přiřazení uvnitř funce swap se v prostoru __main__ neprojeví.

Tato funkce nevyvolá chybové hlášení, ale neprovede to, co jsme si přáli. To je příklad sémantické (významové) chyby.

11.4 Čisté funkce a modifikátory podruhé

V kapitole 9 jsme si povídali o čistých funkcích a modifikátorech v souvislosti se seznamy. Pro entice modifikátory psát nemůžeme, protože entice jsou neměnitelné. .

Zde máme modifikátor, který vloží novou hodnotu do středu seznamu:

#
# seqtools.py
#

def insert_in_middle(val, lst):
    middle = len(lst)/2
    lst[middle:middle] = [val]

Spustíme si to, abychom viděli, že to chodí:

>>> from seqtools import *
>>> my_list = ['a', 'b', 'd', 'e']
>>> insert_in_middle('c', my_list)
>>> my_list
['a', 'b', 'c', 'd', 'e']

Zkusíme-li to s enticí, dostaneme chybu:

>>> my_tuple = ('a', 'b', 'd', 'e')
>>> insert_in_middle('c', my_tuple)
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "seqtools.py", line 7, in insert_in_middle
    lst[middle:middle] = [val]
TypeError: 'tuple' object does not support item assignment
>>> 

Problém je ten, že entice jsou neměnitelné a nepodporují úsekové přiřazení. Jednoduchým řešením je udělat z insert_in_middle čistou funkci:

def insert_in_middle(val, tup):
    middle = len(tup)/2
    return tup[:middle] + (val,) + tup[middle:]

Tato verze nyní chodí pro entice, ne však pro seznamy a řetězce. Chceme-li verzi pro všechny sekvenční typy, potřebujeme zapouzdřit naši hodnotu do správného sekvenčního typu. Malá pomocná funkce vykoná div:

def encapsulate(val, seq):
    if type(seq) == type(""):
        return str(val)
    if type(seq) == type([]):
        return [val]
    return (val,)

Nyní můžeme napsat insert_in_middle tak, aby pracovala s každým vestavěným typem sekvence:

def insert_in_middle(val, seq):
    middle = len(seq)/2
    return seq[:middle] + encapsulate(val, seq) + seq[middle:]

Poslední dvě verze insert_in_middle jsou čisté funkce. Nemají řádné postranní účinky. Přidáme-li encapsulate a poslední verzi insert_in_middle do modulu seqtools.py, můžeme to vyzkoušet:

>>> from seqtools import *
>>> my_string = 'abde'
>>> my_list = ['a', 'b', 'd', 'e']
>>> my_tuple = ('a', 'b', 'd', 'e')
>>> insert_in_middle('c', my_string)
'abcde'
>>> insert_in_middle('c', my_list)
['a', 'b', 'c', 'd', 'e']
>>> insert_in_middle('c', my_tuple)
('a', 'b', 'c', 'd', 'e')
>>> my_string
'abde'

Hodnoty my_string, my_list, a my_tuple se nezměnily. Chceme-li, aby je fce insert_in_middle změnila, musíme výstup funkce přiřadit proměnné:

>>> my_string = insert_in_middle('c', my_string)
>>> my_string
'abcde' 

11.5 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 čísel, 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.

11.6 Rekurze

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.

Moderní programovací jazyky vesměs rekurzi podporují - to jest,umožňují, aby funkce mohla volat ve své definici samu sebe. Potřebný program v Pythonu 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([]):
            sum = sum + recursive_sum(element)
        else:
            sum =sum + element
    return sum

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

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

Poněkud komplikovanější úlohou je nalezení největší hodnoty v seznamu s vnořeným seznamem:

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]
    whiletype(largest) == type([]):
        largest = largest[0]

    for element innested_num_list:
        if type(element) == type([]):
            max_of_elem = recursive_max(element)
            iflargest < 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í.

U obou uvedených příkladů máme základní případ, který nevede k rekurzivnímu volání: je to případ, kdy položkou je číslo, nikoliv seznam. Bez základního případu dostaneme nekonečnou rekurzi. Python se zastaví po dosažení maximální hloubky rekurze a vrací chybu při běhu programu.

Zapište následující kód do souboru infinite_recursion.py:

#
# infinite_recursion.py
#
def recursion_depth(number):
    print"Recursion depth number %d." % 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

Jistě bychom si nepřáli, aby se něco podobného stalo uživateli některého z našich programů, takže se před ukončením rozpravy o rekurzi podívejme, jak jsou podobné chyby ošetřeny Pythonem.

11.7 Výjimky

Kdykoli dojde k chybě za běhu programu, vytvoří se výjimka. Běh programu se zastaví a Python vytiskne záznam, který končí výpisem aktuální výjimky.

Výjimku vytvoří například dělení nulou:

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

Rovněž přistoupení k neexistující položce seznamu:

>>> a = []
>>> print a[5]
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
IndexError: list index out of range
>>>

Nebo pokus o přiřazení hodnoty položce entice:

>>>tup = ('a', 'b', 'd', 'd')
>>>tup[2] = 'c'
Traceback (most recent call last):
   File"<stdin>", line1, in <module>
TypeError: 'tuple' object does not  support item assignment
>>>

Ve všech případech se chybové hlášení na poslední řádce skládá ze dvou částí: uvádí se typ chyby před dvojtečkou a podrobnosti o chybě za dvojtečkoou.

Někdy zamýšlíme provést operaci, která by mohla skončit chybovým hlášením, ale nechceme, aby se program zastavil. Výjimku můžeme ošetřit s použitím příkazů try a except.

Můžeme například chtít, aby uživatel zadal jméno souboru a potom se jej pokusit otevřít. Nechceme, aby program kleknul, zadá-li se jméno neexistujícího souboru, chceme tuto výjimku ošetřit:

filename = raw_input('Enter a file name: ')
try:
    f = open (filename, "r")
except:
    print 'There is no file named', filename

Příkaz try provede příkazy prvního bloku. Nevyskytne-li se výjimka, ignoruje se příkaz except. Vyskytne-li se nějaká výjimka, provedou se příkazy větve except a běh programu pokračuje.

Tuto činnost můžeme zapouzdřit do funkce exists; ta přijme jméno souboru a vrátí True když soubor existuje a False když nikoliv:

def exists(filename):
    try:
        f = open(filename)
        f.close()
        returnTrue
    except:
        return False

Lze použít několik bloků except k ošetření různých druhů výjímek (podrobněji o výjimkách viz kapitola Errors and Exceptions v tutoriálu od Guido van Rossuma: Python Tutorial).

Když program narazí na podmínku pro vznik chyby, lze jej přinutit, aby oznámil (raise) 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 = input('Please enter your age: ')
    if age < 0:
        raise ValueError, '%s is not a valid age' % age
    return age

Příkaz raise přijímá dva argumenty: typ výjimky a bližší informaci o chybě. ValueError je vestavěná výjimka, která co nejblíže odpovídá chybě, kterou chceme hlásit. Úplný výpis vestavěných výjimek lze nalézt v kapitole 2.3 příručky Python Library Reference, kterou rovněž napsal tvůrce Pythonu, Guido van Rossum.

Pokud fce get_age ošetří chybu, může program pokračovat; v opačném případě vytiskne Python záznam a skončí:

>>> get_age()
Please enter your age: 42
42 
>>> get_age()
Please enter your age: -2
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
  File "learn_exceptions.py", line 4, in get_age
    raise ValueError, '%s is not a valid age' % age
ValueError: -2 is not a valid age
>>>

Chybové hlášení obsahuje typ výjimky a dodatečnou informaci, kterou jsme poskytli.

S použitím ošetřené výjimky můžeme nyní upravit fci infinite_recursion.py tak, aby se rekurze zastavila po dosažení zadaného počtu opakování:

#
# infinite_recursion.py
#
def recursion_depth(number):
    print "Recursion depth number %d." % number
    try:
        recursion_depth(number + 1)
    except:
        print "Maximum recursion depth exceeded."

recursion_depth(0)

Vyzkoušej tuto verzi a pozoruj výsledky.

11.8 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 z kapitoly 6:

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

Jakékoliv počítání, které může být provedeno s použitím iterace, může být také provedeno s použitím rekurze.

Mnohé dobře známé matematické funkce jsou definovány rekurzivně. Například faktoriál (!) 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ý vztah 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.

>>> numbers = [1, 2, 3, 4]
>>> [x**2 for x in numbers]
[1, 4, 9, 16]
>>> [x**2 for x in numbers if x**2 > 8]
[9, 16] 
>>> [(x, x**2, x**3) for x in numbers]
[(1, 1, 1), (2, 4, 8), (3, 9, 27), (4, 16, 64)]
>>> files = ['bin', 'Data', 'Desktop', '.bashrc', '.ssh', '.vimrc']
>>> [name for name in files if name[0] != '.']
['bin', 'Data', 'Desktop']
>>> letters = ['a', 'b', 'c']
>>> [n*letter for n in numbers for letter in letters]
['a', 'b', 'c', 'aa', 'bb', 'cc', 'aaa', 'bbb', 'ccc', 'aaaa', 'bbbb', 'cccc']
>>>

[expr for item1 in seq1 for item2 in seq2 ... for itemx in seqx if condition]

output_sequence = []
for item1 in seq1:
    for item2 in seq2:
        ...
            for itemx> in seqx:
                if condition:
                    output_sequence.append(expr)

11.10 Případová ministudie: tree (Unix)

Následující program používá jisté chování unixového programu tree .

#!/usr/bin/env python

import os
import sys


def getroot():
    if len(sys.argv) == 1:
        path = ''
    else:
        path = sys.argv[1]

    if os.path.isabs(path):
        tree_root = path
    else:
        tree_root = os.path.join(os.getcwd(),path)

    return tree_root


def getdirlist(path):
    dirlist = os.listdir(path)
    dirlist = [name for name in dirlist if name[0] != '.']
    dirlist.sort()
    return dirlist


def traverse(path, prefix='|--', s='.\n', f=0, d=0):
    dirlist = getdirlist(path)

    for num, file in enumerate(dirlist):
        lastprefix = prefix[:-3] + '`--'
        dirsize = len(dirlist)

        if num < dirsize - 1:
            s += '%s %s\n' % (prefix, file)
        else:
             s += '%s %s\n' % (lastprefix, file)
        path2file = os.path.join(path, file)

        if os.path.isdir(path2file):
            d += 1
            if getdirlist(path2file):
                s, f, d = traverse(path2file, '|   ' + prefix, s, f, d)
        else:
            f += 1

    return s, f, d


if __name__ == '__main__':
    root =  >getroot()
    tree_str, files, dirs = traverse(root)

    if dirs == 1:
        dirstring = 'directory'
    else:
        dirstring = 'directories'
    if files == 1:
        filestring = 'file'
    else:
        filestring = 'files'

    print tree_str
    print '%d %s, %d %s' % (dirs, dirstring, files, filestring)

11.11 Glosář

11.12 Cvičení