0 dní v řadě · 0 bodů

Funkce · 24 min

Rekurze

Funkce, která volá sama sebe. Projdeš s ní složky a vnořená data, pochopíš zásobník volání a zjistíš, kdy je lepší obyčejný cyklus.

Hloubka
Úkoly
Lidsky řečeno

Stojíš v dlouhé frontě a chceš vědět, kolikátý jsi. Nemusíš vystoupit a počítat. Zeptáš se člověka před sebou: „Kolikátý jsi?“ On neví, tak se zeptá svého předchůdce, a otázka putuje dopředu. První ve frontě nikoho před sebou nemá a řekne: „Jsem první.“ Odpověď se vrací zpátky a každý k ní přičte jedničku. Přesně takhle pracuje rekurze.

Funkce, která volá sama sebe

Rekurze znamená, že funkce při své práci zavolá sama sebe s menší verzí téhož úkolu. Fronta z úvodu vypadá v Pythonu takhle.

def kolikaty_jsem(lidi_prede_mnou):
    if lidi_prede_mnou == 0:
        return 1
    return kolikaty_jsem(lidi_prede_mnou - 1) + 1

print(kolikaty_jsem(0))
print(kolikaty_jsem(4))
Výstup
1
5

Každá rekurzivní funkce má dvě části:

  • Základní případ je situace tak jednoduchá, že odpověď známe rovnou. Tady nikdo přede mnou, takže jsem první.
  • Rekurzivní krok úkol zmenší a zbytek svěří dalšímu volání. Tady se ptám člověka před sebou a přičtu jedničku.

Nemusí se nic vracet. Odpočet jen vypisuje a pak předá zbytek práce dál.

def odpocet(n):
    if n == 0:
        print("Start!")
        return
    print(n)
    odpocet(n - 1)

odpocet(3)
Výstup
3
2
1
Start!

Co se děje uvnitř: zásobník volání

Faktoriál čísla 4 je 4 * 3 * 2 * 1. Dá se ale říct i jinak: faktoriál n je n krát faktoriál n - 1. Do funkce přidáme výpisy s odsazením, ať je vidět každé volání.

def faktorial(n, hloubka=0):
    odsazeni = "  " * hloubka
    print(f"{odsazeni}faktorial({n}) začíná")
    if n <= 1:
        vysledek = 1
    else:
        vysledek = n * faktorial(n - 1, hloubka + 1)
    print(f"{odsazeni}faktorial({n}) vrací {vysledek}")
    return vysledek

print(faktorial(4))
Výstup
faktorial(4) začíná
  faktorial(3) začíná
    faktorial(2) začíná
      faktorial(1) začíná
      faktorial(1) vrací 1
    faktorial(2) vrací 2
  faktorial(3) vrací 6
faktorial(4) vrací 24
24

Volání faktorial(4) se nedokončí hned. Zastaví se na půli výpočtu a čeká na faktorial(3). Python si proto každé rozdělané volání odloží i s jeho proměnnými. Tomuhle místu se říká zásobník volání. Funguje jako komín talířů: nový jde nahoru a sundává se vždy ten horní.

text
cesta dolů                        cesta zpět

faktorial(1)                      vrací 1
faktorial(2)  čeká                2 * 1 = 2
faktorial(3)  čeká                3 * 2 = 6
faktorial(4)  čeká                4 * 6 = 24

Každé volání má vlastní n. Čtyři proměnné se stejným jménem si nepřekážejí, přesně jako si nepřekážejí lokální proměnné různých funkcí.

Kvíz

Co přesně se stane při faktorial(4) s násobením?

Když chybí brzda

Bez základního případu by se funkce volala donekonečna. Každé volání ale zabírá paměť, a tak Python hloubku omezuje. Výchozí limit je 1000 úrovní. Po jeho překročení skončí program chybou RecursionError.

def bez_konce(n):
    return bez_konce(n - 1)

bez_konce(5)
Výstup

Tutéž chybu dostaneš, když základní případ sice existuje, ale výpočet se k němu nikdy nedostane. U každé rekurze si proto polož tři otázky:

  1. Je tu základní případ?
  2. Zmenšuje se úkol při každém volání směrem k němu?
  3. Vrací každá větev výsledek?
def soucet_do(n):
    if n == 0:
        return 0
    n + soucet_do(n - 1)

print(soucet_do(1))
Výstup
None

Tady je to ještě horší, než to vypadá. Volání soucet_do(2) by spadlo na pokusu sečíst číslo s None. Oprava je jediné slovo: return n + soucet_do(n - 1).

Úkol

Součet cifer

Napiš rekurzivní soucet_cifer(n) pro celé číslo n >= 0. Pro 1234 vrátí 10.

def soucet_cifer(n):
    pass  # doplň

print(soucet_cifer(1234))
Výstup

Kde rekurze opravdu září: vnořená data

Faktoriál zvládne obyčejný cyklus. Rekurze se začne vyplácet, když data mají tvar stromu a předem nevíš, jak jsou hluboká. Typicky složky, které obsahují soubory a další složky.

Složku napodobíme slovníkem. Číslo znamená soubor a jeho velikost, další slovník znamená podsložku. Funkce isinstance(x, int) zjistí, jestli je x celé číslo.

disk = {
    "smlouva.pdf": 120,
    "poznamky.txt": 4,
    "fotky": {
        "pes.jpg": 300,
        "dovolena": {"more.jpg": 500, "hory.jpg": 450},
    },
}

def velikost(polozka):
    if isinstance(polozka, int):
        return polozka
    return sum(velikost(obsah) for obsah in polozka.values())

print(velikost(disk))
print(velikost(disk["fotky"]))
Výstup
1374
1250

Celá logika má dva řádky: soubor zná svou velikost, složka je součtem svého obsahu. S cykly by bylo potřeba tolik vnoření, kolik je úrovní, a to předem nevíš. Podobně se strom vypíše.

disk = {
    "smlouva.pdf": 120,
    "fotky": {
        "pes.jpg": 300,
        "dovolena": {"more.jpg": 500},
    },
}

def vypis(slozka, odsazeni=0):
    for nazev, obsah in slozka.items():
        if isinstance(obsah, dict):
            print(" " * odsazeni + nazev + "/")
            vypis(obsah, odsazeni + 2)
        else:
            print(" " * odsazeni + f"{nazev} ({obsah} kB)")

vypis(disk)
Výstup
smlouva.pdf (120 kB)
fotky/
  pes.jpg (300 kB)
  dovolena/
    more.jpg (500 kB)

Stejný tvar mají komentáře s odpověďmi, organizační struktura firmy, kategorie v e-shopu, JSON nebo HTML stránka.

Úkol

Rozbal krabice v krabicích

Napiš zplostit(seznam). Seznam může obsahovat další seznamy v libovolné hloubce. Vrať nový plochý seznam všech prvků ve stejném pořadí. Původní seznam neměň.

def zplostit(seznam):
    pass  # doplň

print(zplostit([1, [2, [3, [4]]], 5]))
Výstup
Úkol

Všechny cesty k souborům

Napiš cesty(slozka, predpona=""). Vrátí seznam úplných cest ke všem souborům, s lomítkem mezi úrovněmi. Pro {"a.txt": 1, "b": {"c.txt": 2}} vrátí a.txt a b/c.txt. Soubor je cokoli, co není slovník.

def cesty(slozka, predpona=""):
    pass  # doplň

print(cesty({"a.txt": 1, "b": {"c.txt": 2}}))
Výstup

Past: stejná práce pořád dokola

Po schodech jdeš po jednom nebo po dvou. Kolika způsoby vyjdeš n schodů? Na poslední schod vede cesta buď z předposledního, nebo z toho o dva níž. Odpověď je tedy součet dvou menších úloh. Zápis je krásně krátký, ale počítadlo prozradí problém.

volani = 0

def zpusoby(n):
    global volani
    volani += 1
    if n <= 1:
        return 1
    return zpusoby(n - 1) + zpusoby(n - 2)

print(zpusoby(10), volani)

volani = 0
print(zpusoby(20), volani)
Výstup
89 177
10946 21891

Pro dvacet schodů je to přes dvacet tisíc volání. Každý další schod počet volání zhruba 1,6krát zvýší, a to proto, že se stejné podúlohy řeší znovu a znovu.

text
zpusoby(4)
├── zpusoby(3)
│   ├── zpusoby(2)   ◄── poprvé
│   │   ├── zpusoby(1)
│   │   └── zpusoby(0)
│   └── zpusoby(1)
└── zpusoby(2)       ◄── znovu to samé
    ├── zpusoby(1)
    └── zpusoby(0)

Lék znáš z lekce o closures: pamatovat si hotové výsledky. Říká se tomu memoizace a standardní knihovna ji má připravenou ve functools.cache. Řádek se zavináčem zatím ber jako nálepku „pamatuj si výsledky“. Dělá totéž co zpusoby = cache(zpusoby) a podrobně ho vysvětlí lekce o dekorátorech.

from functools import cache

volani = 0

@cache
def zpusoby(n):
    global volani
    volani += 1
    if n <= 1:
        return 1
    return zpusoby(n - 1) + zpusoby(n - 2)

print(zpusoby(20), volani)
print(zpusoby(80), volani)
Výstup
10946 21
37889062373143906 81

Každá hodnota se teď počítá jen jednou. Z exponenciálního růstu se stal lineární a osmdesát schodů je hotových okamžitě.

Úkol

Trasy městem

Město je mřížka ulic. Začínáš vlevo nahoře, končíš vpravo dole a smíš jít jen doprava nebo dolů. Napiš pocet_tras(radky, sloupce). V mřížce s jediným řádkem nebo jediným sloupcem existuje právě jedna trasa. Jinak je tras tolik, kolik z políčka pod tebou plus kolik z políčka vpravo. Použij cache, ať je výpočet rychlý.

from functools import cache

def pocet_tras(radky, sloupce):
    pass  # doplň

print(pocet_tras(3, 3))
Výstup

Rekurze, nebo cyklus?

Když úkol jde přímočaře napsat cyklem, napiš cyklus. V Pythonu je rychlejší, nemá limit hloubky a je mu rozumět stejně dobře.

def faktorial(n):
    vysledek = 1
    for i in range(2, n + 1):
        vysledek *= i
    return vysledek

print(faktorial(5))
print(len(str(faktorial(1500))))
Výstup
120
4115

Druhý řádek je počet cifer čísla 1500!. Rekurze by se k němu s výchozím limitem vůbec nedostala.

Rekurzi si nech na stromy a úlohy, které se přirozeně dělí na menší stejného druhu. Když je strom extrémně hluboký, dá se rekurze přepsat na cyklus s vlastním seznamem rozpracovaných položek. Je to tentýž zásobník, jen ho spravuješ sám a limit 1000 se ho netýká.

def velikost(koren):
    celkem = 0
    zasobnik = [koren]
    while zasobnik:
        polozka = zasobnik.pop()
        if isinstance(polozka, int):
            celkem += polozka
        else:
            zasobnik.extend(polozka.values())
    return celkem

hluboko = {"soubor": 7}
for _ in range(5000):
    hluboko = {"slozka": hluboko, "log": 1}

print(velikost(hluboko))
Výstup
5007
Kvíz

Kdy je rekurze v Pythonu nejlepší volba?

Pod kapotou · zásobník v CPythonu 3.11 a 3.12

Od 3.11 volání z Pythonu do Pythonu nespouští znovu C funkci interpretu. Nový rámec se založí a interpret jen přeskočí na jeho kód, takže čistě pythonovská rekurze nespotřebovává C zásobník. Rámce leží v blocích na haldě, které si spravuje interpret, a plnohodnotné objekty frame z nich vznikají až při potřebě.

Ve 3.12 platí sys.setrecursionlimit jen pro kód v Pythonu. Vestavěné funkce mají vlastní ochranu proti přetečení C zásobníku. Zvýšení limitu tak čisté rekurzi opravdu pomůže, stojí jen paměť. Jakmile ale rekurze prochází přes C, například přes functools.cache, map nebo sorted s klíčem, dosažitelná hloubka je menší, sys.setrecursionlimit s ní ve 3.12 nepohne a přesné číslo závisí na verzi i platformě. Cache před hlubokým výpočtem raději předehřej zdola: for i in range(n): zpusoby(i).

CPython optimalizaci koncového volání nemá, a to záměrně: zmizely by rámce ze stopy výjimky. Přepis do „koncového“ tvaru tedy v Pythonu nic neušetří. Přepiš takovou funkci rovnou na while.

Pod kapotou · rekurze v produkci

Rekurze nad vstupem od uživatele je riziko. Stačí poslat hluboce vnořený dokument. Sám standardní parser json na něm skončí výjimkou RecursionError, která není potomkem ValueError, takže ji běžné except ValueError u validace nezachytí a z chybného požadavku se stane chyba 500.

import json

zprava = "[" * 100_000 + "]" * 100_000
try:
    json.loads(zprava)
except RecursionError as chyba:
    print(type(chyba).__name__)
print(issubclass(RecursionError, ValueError), issubclass(RecursionError, RuntimeError))
Výstup
RecursionError
False True

Omez velikost těla požadavku a u vlastních průchodů kontroluj hloubku, nebo použij explicitní zásobník.

Reálná data bývají graf, ne strom. Procházení s cyklem se bez evidence navštívených uzlů zacyklí. Standardní knihovna si to hlídá: repr vypíše [...], json.dumps hlásí Circular reference detected a copy.deepcopy vede tabulku memo. U vlastního průchodu si ukládej id(uzel) do množiny.

smycka = [1]
smycka.append(smycka)
print(smycka)

def soucet(uzel, videno=None):
    videno = set() if videno is None else videno
    if id(uzel) in videno:
        return 0
    videno.add(id(uzel))
    return sum(soucet(x, videno) if isinstance(x, list) else x for x in uzel)

print(soucet(smycka))
Výstup
[1, [...]]
1

Složitost počítej i s pomocnou prací. f(seznam[1:]) kopíruje zbytek v každém kroku, takže jednoduchý průchod vyjde O(n²) a paměť O(n²) po dobu rekurze. Předávej index. Paměť rekurze je O(hloubka): vyvážený strom má hloubku O(log n), zdegenerovaný O(n), což je důvod, proč quicksort dělá rekurzi nejdřív do menší části.

functools.cache drží silné odkazy na všechny argumenty a výsledky bez omezení, takže na dlouho běžícím serveru roste. Tam použij lru_cache(maxsize=...) a sleduj cache_info(). Argumenty musí být hashovatelné, proto seznam neprojde a n-tice ano.

Vyzkoušej si: Strom rekurzivních volání

Prochází volání funkce krok za krokem a ukazuje hloubku zásobníku. Můžeš zapnout paměť výsledků a sledovat, kolik volání ušetří.