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.