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))
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)
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))
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
24Volá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í.
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 = 24Kaž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í.
Co přesně se stane při faktorial(4) s násobením?
Než může proběhnout 4 * ..., musí být znám výsledek faktorial(3). Výpočet se tedy skládá odzadu, od základního případu.
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)
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:
- Je tu základní případ?
- Zmenšuje se úkol při každém volání směrem k němu?
- 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))
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).
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))
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"]))
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)
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.
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š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}}))
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)
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.
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)
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ě.
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))
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))))
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))
5007
Kdy je rekurze v Pythonu nejlepší volba?
Strom se přirozeně dělí na menší stromy a hloubka bývá malá. U plochých dat by rekurze jen přidala režii a brzy narazila na limit.
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))
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))
[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ří.