Níže uvedený text pochází z prvního vydání. Nad tímto textem se nachází aktuální stav po revizi sm�>řující k druhému vydání.

Rekurze

Co to vlastn�> je?

V předchozích částech učebnice jsme se zmínili o tom, že použití cyklu patří k jednomu ze základních kamenů programování. Navzdory tomuto tvrzení je ve skutečnosti možné vytvářet programy, které nepoužívají přímo vyjádřenou konstrukci cyklu. V n�>kterých jazycích, jako je například Lisp, přímá konstrukce cyklu jako FOR, WHILE, a dalších ve skutečnosti vůbec neexistuje. Místo toho se zde používá technika známá jako rekurze. Pro řešení n�>kterých typů problémů se rekurze ukazuje být velmi mocnou technikou. Proto se na ni teď podíváme.

Rekurzí jednoduše rozumíme použití n�>jaké funkce jako části definice té samé funkce. Takže o definici akronymu GNU (což je zdroj velkého množství softwarových produktů dostupných zdarma) říkáme, že je rekurzivní, protože zkratka GNU znamená GNU's Not Unix (čili GNU Není Unix). Zkratka GNU je tedy součástí definice významu zkratky samé.

Klíčem k fungování rekurze je to, že musí existovat podmínka ukončení taková, že v určité situaci funkce pokračuje v�>tví, která představuje nerekurzivní řešení. (Definice akronymu GNU tímto testem použitelnosti neprojde, protože vede k nekonečnému cyklu.)

Podívejme se na jednoduchý příklad. Matematická funkce faktoriál je definována jako součin všech čísel až po zadaný argument včetn�>. Faktoriál čísla 1 (jedna) je definován jako 1. Pokud se nad tím zamyslíme, pak zjistíme, že totéž můžeme vyjádřit jiným způsobem: faktoriál čísla N je roven N krát faktoriál čísla (N-1). Takže můžeme psát:

1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 2! x 3 = 6
N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

V jazyce Python to můžeme zapsat takto:

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

Protože v každém kroku snižujeme hodnotu čísla N a testujeme shodu na hodnotu 1, musí funkce skončit. V uvedené definici funkce je ovšem malá chyba. Pokud se ji pokusíte zavolat pro číslo menší než jedna, uvede se do nekonečného cyklu. Opravit to můžeme tím, že místo testu na rovnost použijeme operátor <=. Tento příklad ukazuje, jak snadno můžeme při zápisu podmínky ukončení ud�>lat chybu. U rekurzivních funkcí jde pravd�>podobn�> o jednu z nejb�>žn�>jších chyb. Abyste zajistili jejich správnou funkčnost, ujist�>te se, že testujete všechny hodnoty v okolí bodu ukončení rekurze.

Podívejme se, co se d�>je, když funkci spustíme. Povšimn�>te si, že příkaz return vrací n * (výsledek následujícího volání funkce factorial), takže dostáváme:

factorial(4) = 4 * factorial(3)
factorial(3) = 3 * factorial(2)
factorial(2) = 2 * factorial(1)
factorial(1) = 1

V tomto okamžiku se Python vrací do vyšších úrovní a dosazuje hodnoty:

factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24

Zápis funkce pro výpočet faktoriálu bez použití rekurze ve skutečnosti není tak obtížný. Vyzkoušejte si jej v rámci cvičení. V podstat�> potřebujete provést cyklus přes všechna čísla až do N a b�>hem této činnosti provádíte násobení. Ale pozd�>ji uvidíme, že existují funkce, jejichž zápis je bez použití rekurze mnohem obtížn�>jší (ve srovnání s rekurzivním zápisem).

Rekurzivní průchod seznamem

Jinou oblastí, kdy je použití rekurze velmi užitečné, je zpracování seznamů. Rekurzi můžeme snadno použít za předpokladu, že jsme schopni testovat prázdnost seznamu a generovat zeznam bez první položky. Pro získání části seznamu můžeme v jazyce Python použít techniku, které se říká slicing ([slajsing] = odkrajování, odřezávání). Plné vysv�>tlení naleznete v příručce jazyka Python. Pro naše účely postačí, když budeme v�>d�>t, že se při použtí indexu ve tvaru [1:] vrací kopie všech prvků seznamu prvku na idexu 1 až do konce seznamu. Takže pokud chceme získat první prvek seznamu L, napíšeme:

prvni = L[0] # použijeme prost�> normální indexování

A pokud chceme získat kopii zbytku seznamu, napíšeme:

zbytek = L[1:] # vyřízneme prvky na indexech 1, 2, 3, ...

Abyste se ujistili, že to funguje, napište na vyzývací řádek Pythonu následující:

>>> L = [1, 2, 3, 4, 5]
>>> print L[0]
1
>>> print L[1:]
[2, 3, 4, 5]

Poznámka překladatele: Obecn�> zápis Seznam[od:do] vyřízne z původního seznamu prvky počínaje indexem od až po prvek s indexem o jedno menším, než do. Pokud část od nebo do není uvedena, pak se do neuvedené části vnitřn�> doplní index, který zahrne prvky od začátku nebo do konce seznamu. Pří získávání části seznamu dochází ke kopii prvků. Zápis Seznam[:] se používá jako obrat pro získání kopie seznamu. Prostým přiřazením s2 = Seznam získáme pouze odkaz na originální seznam. Pokud zm�>níme s2, zm�>ní se i Seznam. Požadavek na získání kopie seznamu proto nepatří k n�>jak výjimečným.

Nyní se vraťme k použití rekurze pro tisk seznamů. Uvažujme jednoduchý případ, kdy chceme každý prvek seznamu řet�>zců vytisknout voláním funkce tiskSeznamu:

def tiskSeznamu(Seznam):
    if Seznam:
        print Seznam[0]
        # Podrobnosti k [1:] — viz příručka jazyka Python, 'slicing'.
        tiskSeznamu(Seznam[1:])

Pokud je seznam neprázdný — dotaz na neprázdný seznam v boolovském kontextu vrací hodnotu True —, pak vytiskneme obsah prvního prvku seznamu a zpracujeme stejným způsobem zbytek seznamu takto (nepythonovský pseudo kód):

Jsme uvnitř tiskSeznamu([1,2,3])
   tiskne se [1,2,3][0] => 1
   spouští se tiskSeznamu([1,2,3][1:]) => tiskSeznamu([2,3])
   => nyní jsme uvnitř tiskSeznamu([2,3])
      tiskne se [2,3][0] => 2
      spouští se tiskSeznamu([2,3][1:]) => tiskSeznamu([3])
      => nyní jsme uvnitř tiskSeznamu([3])
         tiskne se [3][0] => 3
         spouští se tiskSeznamu([3][1:]) => tiskSeznamu([])
         => nyní jsme uvnitř tiskSeznamu([])
            Podmínka v "if Seznam" není pro prázdný seznam spln�>na, 
            proto se vracíme z funkce (nejhlubší bod rekurze).
      => jsme zp�>t v tiskSeznamu([3])
         narazili jsme na konec funkce a vracíme se
   => jsme zp�>t v tiskSeznamu([2,3])
      narazili jsme na konec funkce a vracíme se
=> jsme zp�>t v tiskSeznamu([1,2,3]), tj. na nejvyšší úrovni
   narazili jsme na konec funkce a vracíme se

Poznámka: Výše uvedené vysv�>tlení je s úpravami převzato z textu, který uvedl Zak Arntson v mailing listu "Python Tutor" v červenci 2003.

V případ�> jednoduchého seznamu lze totéž jednoduše řešit při použití jednoduchého cyklu for. Ale uvažujme, jak by to vypadalo v případ�>, kdyby byl Seznam složit�>jší a mohl uvnitř obsahovat další seznamy. (Prvkem by mohl být buď řet�>zec nebo další seznam.) Pokud jsme schopni testovat, zda je prvek seznamu dalším seznamem, pak zavoláme funkci tiskSeznamu() rekurzivn�>. Pokud prvek není seznamem, pak jej jednoduše vytiskneme. Vyzkoušejme si to:

def tiskSeznamu(Seznam):
    # Jestliže je seznam prázdný, ned�>lej nic.
    if not Seznam: return
    # Pokud je první prvek seznamem, dosadíme jej do tiskSeznamu().
    if type(Seznam[0]) == type([]):
        tiskSeznamu(Seznam[0])
    else: # První prvek není seznam. Jednoduše jej vytiskneme. 
        print Seznam[0]
    # Nyní zpracujeme zbytek Seznamu. 
    tiskSeznamu(Seznam[1:])

Pokud se totéž pokusíte zapsat pomocí cyklu, zjistíte, že je to velmi obtížné. Rekurze umožní zapsat podobn�> složité úlohy srovnateln�> jednoduše. (Jinými slovy, rekurzivní řešení jednoduchého případu a uvedeného složit�>jšího případu je přibližn�> stejn�> obtížné.)

Je tu ovšem jeden zádrhel (jako vždycky). Rekurzivní zpracování velkých datových struktur typicky vede k velké spotřeb�> pam�>ťového prostoru. Takže pokud máte k dispozici málo pam�>ti nebo zpracováváte velmi velké datové struktury, může být složit�>jší konvenční řešení bezpečn�>jší.

Tak. A nyní ud�>lejme další skok do neznáma — seznámíme se s objektov�> orientovaným programováním.