Chcete číst

Převod vícenásobné rekurze na iteraci

aneb kvůli stack overflow šaháme na StackOverflow.com

Občas si hraju na Project Euler - stránkách, kde jsou vystaveny (většinou matematické) úlohy, u kterých je cílem napsat program, který je vyřeší pokud možno za méně než minutu.

Na jazyku ani konečném řešení nezáleží, jde spíš o cestu, o průzkum bitevního pole (čti: hledání vlastností a algoritmů na Wikipedii, MathWorldu, počmárání tuny papíru při snaze najít opakující se vzor, který by šlo využít) a o ten pocit, kdy zadáte odpověď a ukáže se vám ... tohle. Ááááách. ;)

Není nad to :)

Před pár hodinami jsem se podíval na jeden z nových problémů, který má něco do činění s nesoudělnými čísly. Mě tedy zajímal hlavně algoritmus pro jejich generování:

def nesoudelna(n):
    # n = vrchni limit, nechceme v parech vetsi cisla nez toto

    # udelame seznam paru, ktery pak budeme vracet
    pary = []

    def rekurze(x,y):

        # jsme v limitu?
        # vzdy plati: x > y
        if x <= n:

            # vlozime to do seznamu
            pary.append((x,y))

            # funkci zavolame na dalsich parech
            rekurze(2*x - y, x)
            rekurze(2*x + y, x)
            rekurze(x + 2*y, y)

    # funkci zavolame na prvnich dvou parech
    rekurze(2,1)
    rekurze(3,1)

    # vse jsme vycerpali, vracime hotovy seznam
    return pary

Jenže ouha: tato funkce bude fungovat jen pro relativně malá n. Když bude n větší, vnitřní funkce se zavolá tolikrát, že mi program zařve na přetečení zásobníku.

print len(nesoudelna(50))   # 773
print len(nesoudelna(5000)) # RuntimeError: maximum recursion depth exceeded

To se většinou řeší převodem na funkci iterativní (tedy místo volání sebe sama používající nějakou smyčku). Vím, jak převést klasickou rekurzivní funkci, ale co když se volá vícekrát? StackOverflow.com dává odpověď: v tu chvíli je třeba použít zásobník.

Budeme jím napodobovat právě ten zásobník, který nám přetekl při rekurzivní funkci. Ale protože si na něj místo alokujeme sami, není nijak extra omezený. Může nám zabrat gigabajty paměti, programu to vadit nebude. Systémový zásobník by v tu chvíli už dávno spadl.

Využijeme toho, že Python má u seznamu funkce append() a pop() - což je přesně to, co potřebujeme, abychom zásobník mohli vytvořit. Náš zásobník bude obsahovat dvojice "argumentů," které je třeba zpracovat. S každým dalším voláním se teoreticky rozšíří o dvě dvojice (jednu jsme vyřešili, tři přidáváme), ale postupem času začneme narážet na náš limit n a prvků v zásobníku začne ubývat. Jdem na to:

def nesoudelna_iter(n):
    # n = vrchni limit, nechceme v parech vetsi cisla nez toto

    # udelame seznam paru, ktery pak budeme vracet
    pary = []

    # pocatecni hodnoty
    zasobnik = [(2,1),(3,1)]

    # dokud v zasobniku neco je
    while zasobnik:

        # vezmem to a dame do x,y
        x,y = zasobnik.pop()

        # jsme v limitu?
        # vzdy plati: x > y
        if x <= n:

            # vlozime to do seznamu
            pary.append((x,y))

            # do "todo" seznamu pridame dalsi vetve
            zasobnik.append((2*x - y, x))
            zasobnik.append((2*x + y, x))
            zasobnik.append((x + 2*y, y))
    
    # vse jsme vycerpali, vracime hotovy seznam
    return pary

Iterativní verze se liší tímto (zvýrazněné řádky výše):

  • ř. 8 - na začátku si definujeme zásobník s "argumenty"
  • ř. 11 - rozeběhneme to ne voláním vnitřní funkce, ale smyčkou while
  • ř. 14 - v té vyprazdňujeme zásobník
  • ř. 24-26 - místo znovuvolání vnitřní funkce přidáváme do zásobníku

A když tuto novou verzi zkusíme spustit?

print len(nesoudelna_iter(50))   # 773
print len(nesoudelna_iter(5000)) # 7600457

That's all, folks!

EDIT 3. 7. 2012: pročítám se tutoriálem Erlangu a narazil jsem na tuto skvělou ilustraci rekurze. :)

reCURSION

Napište komentář