12. Rekurzia

Už vieme, že opakovať nejaký výpočet môžeme pomocou cyklov, napr. pomocou for-cyklu alebo while-cyklu. Ďalším spôsobom je rekurzia, pri ktorej sa nejaký výpočet opakuje len pomocou volaní podprogramu. Keď budeme chcieť opakovať nejaký výpočet pomocou rekurzie, budeme na to musieť:

  • zadefinovať funkciu, pričom v tele tejto funkcie bude výpočet, ktorý chceme opakovať

  • potom samotné opakovanie sa bude realizovať volaním funkcie - najčastejšie samej seba.

Uvidíme, že rekurzívna funkcia by mala nejako zabezpečiť, aby takéto opakovanie nebolo nekonečné.

Rekurzia sa bude často používať aj na riešenie úloh, ktoré vieme rozložiť na menšie časti a niektoré z týchto (už menších) častí riešime opäť zavolaním samotnej funkcie. Keďže toto druhé (tzv. rekurzívne) volanie už rieši menšiu úlohu, ako bola pôvodná, je šanca, že sa takéto riešenie priblížilo k očakávanému výsledku. Toto je ale už náročnejší pohľad na rekurziu, k nemu sa dopracujeme až po získaní mnohých skúseností.

Aby sme mali šancu lepšie porozumieť mechanizmu rekurzie, pripomeňme si mechanizmus volania funkcií, ktorý sme zaviedli na predchádzajúcich prednáškach:

  • zapamätá sa návratová adresa

  • vytvorí sa nový menný priestor funkcie

    • v ňom sa vytvárajú lokálne premenné aj parametre

  • vykoná sa telo funkcie

  • po skončení vykonania tela funkcie sa zruší menný priestor (aj so všetkými premennými)

  • vykonávanie programu sa vráti na návratovú adresu

Nekonečná rekurzia

Rekurzia v programovaní teda znamená, že funkcia najčastejšie zavolá samú seba, t.j. že funkcia je definovaná pomocou samej seba. Na prvej ukážke vidíme rekurzívnu funkciu, ktorá nerobí nič iné, len volá samú seba:

def xy():
    xy()

xy()

Takéto volanie po krátkom čase skončí chybovou správou:

...
  [Previous line repeated 990 more times]
RecursionError: maximum recursion depth exceeded

To, že funkcia naozaj volala samú seba, môžeme vidieť, keď popri rekurzívnom volaní urobíme nejakú akciu, napr. budeme zvyšovať nejakú globálnu premennú:

def xy():
    global pocet
    pocet += 1
    xy()
>>> pocet = 0
>>> xy()
...
RecursionError: maximum recursion depth exceeded
>>> pocet
994

V tomto prípade program opäť spadne, hoci môžeme vidieť, že sa naozaj zvyšovalo počítadlo. Treba si uvedomiť, že každé zvýšenie počítadla znamená rekurzívne volanie a teda vidíme, že ich bolo skoro tisíc. My už vieme, že každé volanie funkcie (bez ohľadu na to, či je rekurzívna alebo nie) spôsobí, že Python si niekde zapamätá nielen návratovú adresu, aby po skončení funkcie vedel, kam sa má vrátiť, ale aj menný priestor tejto funkcie. Python má na tieto účely rezervu okolo 1000 vnorených volaní. Ak toto presiahneme, tak sa dozvieme správu ‚RecursionError: maximum recursion depth exceeded‘ (hĺbka rekurzívnych volaní presiahla nastavené maximum).

Teraz vyskúšajme rekurzívny program s korytnačkou:

import turtle

def xy(d):
    t.fd(d)
    t.lt(60)
    xy(d + 0.3)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
xy(1)

Po spustení program niečo kreslí, ale aj tak veľmi rýchlo spadne:

...
RecursionError: maximum recursion depth exceeded ...

Odkrokujme si to:

  • v poslednom riadku programu je volanie funkcie xy() => vytvorí sa parameter d (čo je vlastne lokálna premenná), ktorej hodnota je 1,

  • nakreslí sa čiara dĺžky d a korytnačka sa otočí vľavo o 60 stupňov,

  • znovu sa volá funkcia xy(), ale so zmeneným parametrom d na d + 0.3, t.j. vytvorí sa nová lokálna premenná d (v novom mennom priestore) s hodnotou 1.3,

  • toto sa robí donekonečna - našťastie to časom spadne na preplnení pythonovskej pamäte pre volania funkcií

Informácie o mennom priestore a aj návratovej adrese si Python ukladá v špeciálnej údajovej štruktúre zásobník.

Zásobník (stack)

je údajová štruktúra, ktorá má tieto vlastnosti:

  • nové prvky pridávame na vrch (napr. na vrch kopy tanierov, resp. na koniec radu čakajúcich)

  • keď potrebujeme zo zásobníka nejaký prvok, vždy ho odoberáme z vrchu (odoberáme naposledy položený tanier, resp. posledný v rade čakajúcich)

Odborne sa tomu hovorí LIFO (last in first out), teda posledný prišiel, ale ako prvý odišiel - bol obslúžený (zrejme, keby to bol rad napr. v obchode, tak by sme ho považovali za nespravodlivý rad).

Zásobník sa používa na uchovávanie menných priestorov: každé ďalšie volanie funkcie, vytvorí nový menný priestor, ktorý sa uloží na koniec doteraz vytvorených menných priestorov. Keď ale príde ukončenie volania funkcie, z tohto zásobníka sa odstráni naposledy pridávaný menný priestor (hoci sme ho zaradili ako posledný, vybrali sme ho ako prvý, t.j. LIFO).

Chvostová rekurzia (nepravá rekurzia)

Aby sme nevytvárali nikdy nekončiace programy, t.j. nekonečnú rekurziu, niekde do tela rekurzívnej funkcie musíme vložiť test, ktorý zabezpečí, že v niektorých prípadoch rekurzia predsa len skončí. Keďže rekurzia vlastne slúži na opakovanie výpočtu, budeme musieť prezradiť, kedy (v akom prípade) toto opakovanie, teda rekurzívne volanie, končí. Na začiatok funkcie umiestnime podmienený príkaz if, ktorý otestuje, či už nenastal taký prípad, že netreba opakovať výpočet aj s rekurzívnym volaním. Možno by v tomto prípade stačilo len vykonať nejaké „nerekurzívne“ príkazy a skončiť. Zrejme, keď tento test neprejde (nenastal tento špeciálny prípad), vykoná sa pôvodný výpočet a celé sa to opakuje (vďaka rekurzívnemu volaniu).

Takýto špeciálny prípad, keď už nebude potrebné rekurzívne volanie, budeme volať triviálnym prípadom („base case“). Môžeme si to predstaviť aj takto: rekurzívna funkcia rieši nejaký komplexný problém a pri jeho riešení volá samu seba (rekurzívne volanie, „recursive case“) väčšinou s nejakými pozmenenými údajmi. V niektorých prípadoch ale rekurzívne volanie na riešenie problému nepotrebujeme, ale vieme to vyriešiť „triviálne“ aj bez nej (riešenie takejto úlohy je už „triviálne“). V takto riešených úlohách vidíme, že sa funkcia skladá z dvoch častí:

  • pri splnení nejakej podmienky, sa vykonajú príkazy bez rekurzívneho volania (triviálny prípad),

  • inak sa vykonajú príkazy, ktoré v sebe obsahujú rekurzívne volanie .

Zrejme, toto má šancu fungovať len vtedy, keď po nejakom čase naozaj nastane podmienka triviálneho prípadu (podmienka, ktorá ukončí opakovanie), t.j. keď sa tak menia parametre rekurzívneho volania, že sa k triviálnemu prípadu nejako blížime.

V nasledujúcej ukážke môžete vidieť, že rekurzívna špirála sa kreslí tak, že sa najprv nakreslí úsečka dĺžky d, korytnačka sa otočí o 60 stupňov vľavo a dokreslí sa špirála s väčšími hodnotami. Toto celé skončí, keď už by sme chceli nakresliť špirálu väčšiu ako 100 - takáto špirála sa už nenakreslí. Akciou triviálneho prípadu je tu nič, t.j. žiadna akcia pre príliš veľké špirály:

import turtle

def spir(d):
    if d > 100:
        pass     # nerob nič
    else:
        t.fd(d)
        t.lt(60)
        spir(d + 3)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
spir(10)
_images/12_1.png

Ručne odkrokujme volanie funkcie spir(92), pritom si zaznačíme, čo sa deje na zásobníku:

  • pre volanie spir(92): na zásobníku vznikne nová lokálna premenná d s hodnotou 92 … korytnačka nakreslí čiaru, otočí sa a volá spir() s parametrom 95,

  • pre volanie spir(95): na zásobníku vznikne nová lokálna premenná d s hodnotou 95 … korytnačka nakreslí čiaru, otočí sa a volá spir() s parametrom 98,

  • pre volanie spir(98): na zásobníku vznikne nová lokálna premenná d s hodnotou 98 … korytnačka nakreslí čiaru, otočí sa a volá spir() s parametrom 101,

  • pre volanie spir(101): na zásobníku vznikne nová lokálna premenná d s hodnotou 101 … korytnačka už nič nekreslí ani sa nič nevolá … funkcia spir() končí, t.j.

    • zabudnú sa všetky lokálne premenné na tejto úrovni, t.j. premenná d s hodnotou 101 a riadenie sa vráti za posledné volanie funkcie spir() - tá ale končí, t.j.

    • zabudnú sa všetky lokálne premenné na tejto úrovni, t.j. premenná d s hodnotou 98 a riadenie sa vráti za posledné volanie funkcie spir() - tá ale končí, t.j.

    • zabudnú sa všetky lokálne premenné na tejto úrovni, t.j. premenná d s hodnotou 95 a riadenie sa vráti za posledné volanie funkcie spir() - tá ale končí, t.j.

    • zabudnú sa všetky lokálne premenné na tejto úrovni, t.j. premenná d s hodnotou 92 a riadenie sa vráti za posledné volanie funkcie spir() - teda za posledný riadok programu (za riadok spir(92))

Toto nám potvrdia aj kontrolné výpisy vo funkcii:

def spir(d):
    print(f'volanie spir({d})')
    if d > 100:
        pass     # nerob nič
        print('... trivialny pripad - nerobim nic')
    else:
        t.fd(d)
        t.lt(60)
        print(f'... rekurzivne volam spir({d + 3})')
        spir(d+3)
        print(f'... navrat z volania spir({d + 3})')
>>> spir(92)
volanie spir(92)
... rekurzivne volam spir(95)
volanie spir(95)
... rekurzivne volam spir(98)
volanie spir(98)
... rekurzivne volam spir(101)
volanie spir(101)
... trivialny pripad - nerobim nic
... navrat z volania spir(101)
... navrat z volania spir(98)
... navrat z volania spir(95)

Nakoľko rekurzívne volanie funkcie je iba na jednom mieste, za ktorým už nenasledujú ďalšie príkazy funkcie, toto rekurzívne volanie sa dá ľahko prepísať cyklom while:

def spir(d):
    while d <= 100:
        t.fd(d);
        t.lt(60);
        d = d + 3;

Rekurzii, v ktorej za rekurzívnym volaním nie sú ďalšie príkazy, hovoríme chvostová rekurzia (jediné rekurzívne volanie je posledným príkazom funkcie). Takáto rekurzia sa dá prepísať na nerekurzívnu funkciu najčastejšie pomocou while-cyklu.

Rekurziu môžeme používať nielen pri kreslení pomocou korytnačky, ale napr. aj pri výpisoch pomocou print(). V nasledujúcom príklade vypisujeme vedľa seba čísla n, n-1, n-2, …, 2, 1:

def vypis(n):
    if n < 1:
        pass               # nič nerob len skonči
    else:
        print(n, end=', ')
        vypis(n - 1)       # rekurzívne volanie
>>> vypis(20)
20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1,

Zrejme by bolo veľmi jednoduché to prepísať bez použitia rekurzie, napr. pomocou while-cyklu (alebo for-cyklu). Poexperimentujme, a vymeňme dva riadky: vypisovanie print() s rekurzívnym volaním vypis(). Po spustení vidíte, že aj táto nová rekurzívna funkcia sa dá prepísať len pomocou while-cyklu (resp. for-cyklu), ale jej činnosť už nemusí byť pre každého na prvý pohľad až tak jasná - odtrasujte túto zmenenú verziu:

def vypis(n):
    if n < 1:
        pass      # nič nerob len skonči
    else:
        vypis(n - 1)
        print(n, end=', ')
>>> vypis(20)
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,

Táto funkcia chce vypísať prvých n čísel. Aby to urobila, najprv vypíše prvých n - 1 čísel (volanie vypis(n - 1)) a až potom číslo n (posledný príkaz print(n, end=', ')).

Uvedomte si, že túto rekurzívnu funkciu môžeme zapísať aj takto:

def vypis(n):
    if n < 1:
        return      # nič nerob len skonči
    vypis(n - 1)
    print(n, end=', ')

alebo:

def vypis(n):
    if n >= 1:
        vypis(n - 1)
        print(n, end=', ')

Lenže v týchto zápisoch nie je triviálny prípad až tak čitateľný. Preto, kým si na rekurziu nezvykneme a nestane sa pre nás úplne prirodzeným spôsobom riešenia úloh, bude radšej zvýrazňovať takýto triviálny prípad ako jednu vetvu príkazu if.

Pravá rekurzia

Rekurzie, ktoré už nie sú obyčajné chvostové, sú na pochopenie trochu zložitejšie. Pozrime takéto kreslenie špirály:

def spir(d):
    if d > 100:
        t.pencolor('red')     # a skonči
    else:
        t.fd(d)
        t.lt(60);
        spir(d + 3)
        t.fd(d)
        t.lt(60)

spir(1)

Nejaké príkazy sú pred aj za rekurzívnym volaním. Aby sme to lepšie rozlíšili, triviálny prípad nastaví inú farbu pera.

Aj takéto rekurzívne volanie sa dá prepísať pomocou dvoch cyklov:

def spir(d):
    pocet = 0
    while d <= 100:    # čo sa deje pred rekurzívnym volaním
        t.fd(d)
        t.lt(60)
        d += 3
        pocet += 1
    t.pencolor('red')  # triviálny prípad
    while pocet > 0:   # čo sa deje po vynáraní z rekurzie
        d -= 3
        t.fd(d)
        t.lt(60)
        pocet -= 1
_images/12_2.png

Aj v ďalších príkladoch môžete vidieť pravú rekurziu. Napr. vylepšená funkcia vypis vypisuje postupnosť čísel:

def vypis(n):
    if n < 1:
        pass         # skonči
    else:
        print(n, end=', ')
        vypis(n - 1)
        print(n, end=', ')

vypis(10)
10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10,

Keď ako triviálny prípad pridáme výpis hviezdičiek, toto sa vypíše niekde medzi postupnosť čísel. Viete, kde sa vypíšu tieto hviezdičky?

def vypis(n):
    if n < 1:
        print('***', end=', ')         # a skonči
    else:
        print(n, end=', ')
        vypis(n - 1)
        print(n, end=', ')

vypis(10)

V ďalších príkladoch s korytnačkou využívame veľmi užitočnú funkciu poly:

def poly(pocet, dlzka, uhol):
    while pocet > 0:
        t.fd(dlzka)
        t.lt(uhol)
        pocet -= 1

Ktorú môžeme cvične prerobiť na rekurzívnu:

def poly(pocet, dlzka, uhol):
    if pocet <= 0:
        pass          # nič nerob len skonči
    else:
        t.fd(dlzka)
        t.lt(uhol)
        poly(pocet - 1, dlzka, uhol)

čo môžeme zapísať aj takto:

def poly(pocet, dlzka, uhol):
    if pocet > 0:
        t.fd(dlzka)
        t.lt(uhol)
        poly(pocet - 1, dlzka, uhol)

Zistite, čo kreslia funkcie stvorec a stvorec1:

def stvorec(a):
    if a > 100:
        pass          # nič nerob len skonči
    else:
        poly(4, a, 90)
        stvorec(a + 5)

def stvorec1(a):
    if a > 100:
        t.lt(180)       # a skonči
    else:
        poly(4, a, 90)
        stvorec1(a + 5)
        poly(4, a, 90)

Všetky tieto príklady s pravou rekurziou by ste mali vedieť jednoducho prepísať bez rekurzie pomocou niekoľkých cyklov.

Faktoriál

V nasledujúcom príklade počítame faktoriál prirodzeného čísla n. Matematici ho niekedy definujú takto:

  • buď je to 1 pre n=0

  • alebo n * (n-1) * (n-2) * ... * 2 * 1 pre n >= 1

Tu vidíme zapísaný obyčajný cyklus.

Inokedy ale matematici zadefinujú faktoriál n! takto:

  • 1 pre n=0 (už vieme, že je to triviálny prípad)

  • (n-1)! * n (vidíme rekurzívne volanie)

Prepíšme to rekurzívnou funkciou:

def faktorial(n):
    if n == 0:
        return 1
    return faktorial(n - 1) * n

Triviálnym prípadom je tu úloha, ako vyriešiť 0!. Toto vieme vyriešiť aj bez rekurzie, lebo je to 1. Ostatné prípady sú už rekurzívne: na to, aby sme vyriešili zložitejší problém (n faktoriál), najprv vypočítame jednoduchší (n-1 faktoriál) - zrejme pomocou rekurzie - a z neho skombinujeme (násobením) požadovaný výsledok. Hoci toto riešenie nie je chvostová rekurzia (po rekurzívnom volaní faktorial sa musí ešte násobiť), vieme ho jednoducho prepísať pomocou cyklu.

Otočenie reťazca

Pozrime ďalšiu jednoduchú rekurzívnu funkciu, ktorá otočí znakový reťazec (zrejme to vieme urobiť aj jednoduchšie pomocou retazec[::-1]):

def otoc(retazec):
    if len(retazec) <= 1:
        return retazec
    return otoc(retazec[1:]) + retazec[0]

print(otoc('Bratislava'))
print(otoc('Bratislava'*100))

Táto funkcia pracuje na tomto princípe:

  • krátky reťazec (prázdny alebo jednoznakový) sa otáča jednoducho: netreba robiť nič, lebo on je zároveň aj otočeným reťazcom

  • dlhšie reťazce otáčame tak, že z neho najprv odtrhneme prvý znak, otočíme zvyšok reťazca (to je už kratší reťazec ako pôvodný) a k nemu na koniec prilepíme odtrhnutý prvý znak

Toto funguje dobre, ale veľmi rýchlo narazíme na limity rekurzie: dlhší reťazec ako 1000 znakov už táto rekurzia nezvládne.

Vylepšime tento algoritmus takto:

  • reťazec budeme skracovať o prvý aj posledný znak, takýto skrátený rekurzívne otočíme a tieto dva znaky opäť k reťazcu prilepíme, ale v opačnom poradí: na začiatok posledný znak a na koniec prvý:

def otoc(retazec):
    if len(retazec) <= 1:
        return retazec
    return retazec[-1] + otoc(retazec[1:-1]) + retazec[0]

print(otoc('Bratislava'))
print(otoc('Bratislava'*100))
print(otoc('Bratislava'*200))

Táto funkcia už pracuje pre 1000-znakový reťazec správne, ale opäť nefunguje pre reťazce dlhšie ako 2000.

Ďalšie vylepšenie tohto algoritmu už nie je také zrejmé:

  • reťazec rozdelíme na dve polovice (pritom jedna z nich môže byť o 1 kratšia ako druhá)

  • každú polovicu samostatne otočíme

  • tieto dve otočené polovice opäť zlepíme dokopy, ale v opačnom poradí: najprv pôjde druhá polovica a za ňou prvá

def otoc(retazec):
    if len(retazec) <= 1:
        return retazec
    prva = otoc(retazec[:len(retazec) // 2])
    druha = otoc(retazec[len(retazec) // 2:])
    return druha + prva

print(otoc('Bratislava'))
print(otoc('Bratislava' * 100))
print(otoc('Bratislava' * 200))
povodny = 'Bratislava' * 100000
r = otoc(povodny)
print(len(r), r == povodny[::-1])

Zdá sa, že tento algoritmus už nemá problém s obmedzením na hĺbku vnorenia rekurzie. Zvládol aj 1000000 znakový reťazec.

Vidíme, že pri rozmýšľaní nad rekurzívnym riešením problému je veľmi dôležité správne rozdeliť veľký problém na jeden alebo aj viac menších, tie rekurzívne vyriešiť a potom to správne spojiť do jedného výsledku. Pri takomto rozhodovaní funguje matematická intuícia a tiež nemalá programátorská skúsenosť. Hoci nie vždy to ide tak elegantne, ako pri otáčaní reťazca.

Binomické koeficienty

Ďalší príklad ilustruje využitie rekurzie pri výpočte binomických koeficientov. Vieme, že binomické koficienty sa dajú vypočítať pomocou matematického vzorca:

bin(n, k) = n! / (k! * (n - k)!)

Teda výpočtom nejakých troch faktoriálov a potom ich delením. Pre veľké n to môžu byť dosť veľké čísla, napr. bin(1000,1) potrebuje vypočítať 1000! a tiež 999!, čo sú dosť veľké čísla, ale ich vydelením dostávame výsledok len 1000. Takýto postup počítať binomické koeficienty pomocou faktoriálov asi nie je najvhodnejší.

Tieto koeficienty ale vieme zobraziť aj pomocou Pascalovho trojuholníka, napr.:

          1
        1   1
      1   2   1
    1   3   3   1
  1   4   6   4   1
1   5  10  10   5   1

Každý prvok v tomto trojuholníku zodpovedá bin(n,k), kde n je riadok tabuľky a k je stĺpec. Pre túto tabuľku poznáme aj takýto vzťah:

bin(n,k) = bin(n-1,k-1) + bin(n-1,k)

t.j. každé číslo je súčtom dvoch čísel v riadku nad sebou, pričom na kraji tabuľky sú 1. To je predsa krásna rekurzia, v ktorej kraj tabuľky je triviálny prípad:

def bin(n, k):
    if k == 0 or n == k:
        return 1
    return bin(n - 1, k - 1) + bin(n - 1, k)

for n in range(6):
    for k in range(n + 1):
        print(bin(n, k), end=' ')
    print()

po spustení:

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1

Všimnite si, že v tomto algoritme nie je žiadne násobenie iba sčitovanie a ak by sme aj toto sčitovanie previedli na zreťazovanie reťazcov, videli by sme:

def bin_retazec(n, k):
    if k == 0 or n == k:
        return '1'
    return bin_retazec(n - 1, k - 1) + '+' + bin_retazec(n - 1, k)

print(bin(6, 3), '=', bin_retazec(6, 3))
20 = 1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1+1

Rekurzívny algoritmus pre výpočet binárnych koeficientov by mohol využívať vlastne len pripočítavanie jednotky.

Fibonacciho čísla

Na podobnom princípe ako napr. výpočet faktoriálu, funguje aj fibonacciho postupnosť čísel: postupnosť začína dvomi členmi 0, 1. Každý ďalší člen sa vypočíta ako súčet dvoch predchádzajúcich, teda:

  • triviálny prípad: fib(0) = 0

  • triviálny prípad: fib(1) = 1

  • rekurzívny popis: fib(n) = fib(n - 1) + fib(n - 2)

Zapíšeme to v Pythone:

def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
>>> for i in range(15):
        print(fib(i), end=', ')

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,

Tento rekurzívny algoritmus je ale veľmi neefektívny, napr. fib(100) asi nevypočítate ani na najrýchlejšom počítači.

V čom je tu problém? Veď nerekurzívne je to veľmi jednoduché, napr.:

def fib(n):
    a, b = 0, 1
    while n > 0:
        a, b = b, a + b
        n -= 1
    return a

for i in range(15):
    print(fib(i), end=', ')

print('\nfib(100) =', fib(100))
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377,
fib(100) = 354224848179261915075

Pridajme do rekurzívnej verzie funkcie fib() globálne počítadlo, ktoré bude počítať počet zavolaní tejto funkcie:

def fib(n):
    global pocet
    pocet += 1
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

pocet = 0
print('fib(15) =', fib(15))
print('pocet volani funkcie =', pocet)
pocet = 0
print('fib(16) =', fib(16))
print('pocet volani funkcie =', pocet)
fib(15) = 610
pocet volani funkcie = 1973
fib(16) = 987
pocet volani funkcie = 3193

Vidíme, že tento počet volaní veľmi rýchlo rastie a je určite väčší ako samotné fibonacciho číslo. Preto aj fib(100) by trvalo veľmi dlho (vyše 354224848179261915075 volaní funkcie).

Binárne stromy

Medzi informatikmi sú veľmi populárne binárne stromy. Rekurzívne kresby binárnych stromov sa najlepšie kreslia pomocou grafického pera korytnačky. Aby sa nám lepšie o binárnych stromoch rozprávalo, zavedieme pojem úroveň stromu, t.j. číslo n, pre ktoré platí:

  • ak je úroveň stromu n = 0, nakreslí sa len čiara nejakej dĺžky (kmeň stromu)

  • pre n >= 1, sa najprv nakreslí čiara, potom sa na jej konci nakreslí najprv vľavo celý binárny strom úrovne (n-1) a potom vpravo opäť binárny strom úrovne (n-1) (hovoríme im podstromy) - po nakreslení týchto podstromov sa ešte vráti späť po prvej nakreslenej čiare

  • po skončení kreslenia stromu ľubovoľnej úrovne sa korytnačka nachádza na mieste, kde začala kresliť

  • ľavé aj pravé podstromy môžu mať buď rovnako veľké konáre ako kmeň stromu, alebo sa môžu v nižších úrovniach (teda v podstromoch) zmenšovať

Úroveň stromu nám hovorí o počte rekurzívnych vnorení pri kreslení stromu (podobne budeme neskôr definovať aj iné rekurzívne obrázky a často budeme pritom používať pojem úroveň).

Najprv ukážeme binárny strom, ktorý má vo všetkých úrovniach rovnako veľké podstromy:

import turtle

def strom(n):
    if n == 0:
        t.fd(30)        # triviálny prípad
        t.bk(30)
    else:
        t.fd(30)
        t.lt(40)        # natoč sa na kreslenie ľavého podstromu
        strom(n - 1)    # nakresli ľavý podstrom (n-1). úrovne
        t.rt(80)        # natoč sa na kreslenie pravého podstromu
        strom(n - 1)    # nakresli pravý podstrom (n-1). úrovne
        t.lt(40)        # natoč sa do pôvodného smeru
        t.bk(30)        # vráť sa na pôvodné miesto

t = turtle.Turtle()
t.lt(90)
strom(4)
_images/12_3.png

Binárne stromy môžeme rôzne vylepšovať, napr. vetvy stromu sa vo vyšších úrovniach môžu rôzne skracovať, uhol o ktorý je natočený ľavý a pravý podstrom môže byť tiež rôzny. V tomto riešení si všimnite, kde je skrytý triviálny prípad rekurzie:

import turtle

def strom(n, d):
    t.fd(d)
    if n > 0:
        t.lt(40)
        strom(n - 1, d * 0.7)
        t.rt(75)
        strom(n - 1, d * 0.6)
        t.lt(35)
    t.bk(d)

t = turtle.Turtle()
t.lt(90)
strom(5, 80)
_images/12_4.png

Algoritmus binárneho stromu môžeme zapísať aj bez parametra n, ktorý určuje úroveň stromu. V tomto prípade rekurzia končí, keď sú kreslené úsečky príliš malé:

import turtle

def strom(d):
    t.fd(d)
    if d > 5:
        t.lt(40)
        strom(d * 0.7)
        t.rt(75)
        strom(d * 0.6)
        t.lt(35)
    t.bk(d)

turtle.delay(0)
t = turtle.Turtle()
t.lt(90)
strom(80)

Ak využijeme náhodný generátor, môžeme vytvárať stromy, ktoré budú navzájom rôzne:

import turtle
from random import randint

def strom(n, d):
    t.pensize(2 * n + 1)
    t.fd(d)
    if n == 0:
        t.dot(10, 'green')
    else:
        uhol1 = randint(20, 40)
        uhol2 = randint(20, 60)
        t.lt(uhol1)
        strom(n - 1, d * randint(40, 70) / 100)
        t.rt(uhol1 + uhol2)
        strom(n - 1, d * randint(40, 70) / 100)
        t.lt(uhol2)
    t.bk(d)

turtle.delay(0)
t = turtle.Turtle()
t.lt(90)
t.pencolor('maroon')
strom(6, 150)
_images/12_5.png

V tomto riešení si všimnite, kde sme zmenili hrúbku pera, aby sa strom kreslil rôzne hrubý v rôznych úrovniach. Tiež sa tu na posledných „konároch“ nakreslili zelené listy - pridali sme ich v triviálnom prípade. Využili sme tu korytnačiu metódu t.dot(veľkosť, farba), ktorá na pozícii korytnačky nakreslí bodku danej veľkosti a farby.

Každé spustenie tohto programu nakreslí trochu iný strom. Môžeme vytvoriť celú alej stromov, v ktorej bude každý strom trochu iný:

import turtle
from random import randint

def strom(n, d):
    t.pensize(2 * n + 1)
    t.fd(d)
    if n == 0:
        t.dot(10, 'green')
    else:
        uhol1 = randint(20, 40)
        uhol2 = randint(20, 60)
        t.lt(uhol1)
        strom(n - 1, d * randint(40, 70) / 100)
        t.rt(uhol1 + uhol2)
        strom(n - 1, d * randint(40, 70) / 100)
        t.lt(uhol2)
    t.bk(d)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
t.lt(90)
t.pencolor('maroon')
for i in range(6):
    t.pu()
    t.setpos(100*i - 250, -50)
    t.pd()
    strom(5, 50)
_images/12_6.png

V nasledujúcom riešení vzniká zaujímavý efekt tým, že v triviálnom prípade urobí korytnačka malý úkrok vpravo a teda sa nevracia po tých istých čiarach a preto sa ani nevráti presne na to isté miesto, kde štartovala kresliť (pod)strom. Táto „chybička“ sa stále zväčšuje a zväčšuje, až pri nakreslení kmeňa stromu je už dosť veľká:

import turtle

def strom(n, d):
    t.fd(d)
    if n == 0:
        t.rt(90)
        t.fd(1)
        t.lt(90)
    else:
        t.lt(40)
        strom(n - 1, d * 0.67)
        t.rt(75)
        strom(n - 1, d * 0.67)
        t.lt(35)
    t.bk(d)

turtle.delay(0)
t = turtle.Turtle()
t.lt(90)
strom(6, 120)
_images/12_7.png

Binárny strom sa dá nakresliť viacerými spôsobmi aj nerekurzívne. V jednom z nich využijeme zoznam korytnačiek, pričom každá z nich po nakreslení jednej úsečky „narodí“ na svojej pozícii ďalšiu korytnačku (vytvorí svoju kópiu), pričom ju ešte trochu otočí. Idea algoritmu je takáto:

  • prvá korytnačka nakreslí kmeň stromu - prvú úsečku dĺžky d

  • na jeho konci (na momentálnej pozícii tejto korytnačky) sa vyrobí jedna nová korytnačka, s novým relatívnym natočením o 40 stupňov vľavo (pripravuje sa, že bude kresliť ľavý podstrom) a sama sa otočí o 50 stupňov vpravo (pripravuje sa, že bude kresliť pravý podstrom)

  • dĺžka d sa zníži napr. na d * 0.6

  • všetky korytnačky teraz prejdú v svojom smere dĺžku d (nakreslia úsečku dĺžky d) a opäť sa na ich koncových pozíciách vytvoria nové korytnačky otočené o 40 a samé sa otočia o 50 stupňov, a d sa opäť zníži

  • toto sa opakuje n krát a takto sa nakreslí kompletný strom

import turtle

def nova(pos, heading):
    t = turtle.Turtle()
    #t.speed(0)
    #t.ht()
    t.pu()
    t.setpos(pos)
    t.seth(heading)
    t.pd()
    return t

def strom(n, d):
    pole = [nova([0, -300], 90)]
    for i in range(n):
        for j in range(len(pole)):
            t = pole[j]
            t.pensize(3*n - 3*i + 1)
            t.pencolor('maroon')
            t.fd(d)
            if i == n - 1:
                t.dot(20, 'green')
            else:
                pole.append(nova(t.pos(), t.heading() + 40))
                t.rt(50)
        d *= 0.6

    print('pocet korytnaciek =', len(pole))

# turtle.delay(0)
strom(7, 300)
_images/12_8.png

Pre korytnačky na poslednej úrovni sa už ďalšie nevytvárajú, ale na ich koncoch sa nakreslí zelená bodka. Program na záver vypíše celkový počet korytnačiek, ktoré sa takto vyrobili (je ich presne toľko, koľko je zelených bodiek ako listov stromu). Všimnite si pomocnú funkciu nova(), ktorá vytvorí novú korytnačku a nastaví jej novú pozíciu aj smer natočenia. Funkcia ako výsledok vráti túto novovytvorenú korytnačku. V tomto prípade program vypísal:

pocet korytnaciek = 64

Ďalšie rekurzívne obrázky

Napíšeme funkciu, ktorá nakreslí obrázok stvorce úrovne n, veľkosti a s týmito vlastnosťami:

  • pre n = 0 nekreslí nič

  • pre n = 1 kreslí štvorec so stranou dĺžky a

  • pre n > 1 kreslí štvorec, v ktorom v každom jeho rohu (smerom dnu) je opäť obrázok stvorce ale už zmenšený: úrovne n-1 a veľkosti a/3

Štvorce v každom rohu štvorca:

import turtle

def stvorce(n, a):
    if n == 0:
        pass
    else:
        for i in range(4):
            t.fd(a)
            t.rt(90)
            stvorce(n - 1, a / 3)
            # skúste: stvorce(n - 1, a * 0.45)

turtle.delay(0)
t = turtle.Turtle()
stvorce(4, 300)
_images/12_9.png

Uvedomte si, že toto nie je chvostová rekurzia.

Tesne pred rekurzívnym volaním otočíme korytnačku o 30 stupňov a po návrate z rekurzie týchto 30 stupňov vrátime:

import turtle

def stvorce(n, d):
    if n > 0:
        for i in range(4):
            t.fd(d)
            t.rt(90)
            t.lt(30)
            stvorce(n - 1, d / 3)
            t.rt(30)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
stvorce(5, 300)
_images/12_10.png

Sierpiňského trojuholník

Rekurzívny obrázok na rovnakom princípe ako boli vnorené štvorce ale trojuholníkového tvaru navrhol poľský matematik Sierpiňský ešte v roku 1915:

import turtle

def trojuholniky(n, a):
    if n > 0:
        for i in range(3):
            t.fd(a)
            t.rt(120)
            trojuholniky(n - 1, a / 2)

turtle.delay(0)
t = turtle.Turtle()
#t.speed(0)
t.rt(60)
trojuholniky(6, 400)
_images/12_11.png

Zaujímavé je to, že táto rekurzívna krivka sa dá nakresliť aj jedným ťahom (po každej čiare sa prejde len raz). Porozmýšľajte ako.

Snehová vločka

Ďalej ukážeme veľmi známu rekurzívnu krivku - snehovú vločku (známu tiež ako Kochova krivka):

import turtle

def vlocka(n, d):
    if n == 0:
        t.fd(d)
    else:
        vlocka(n - 1, d / 3)
        t.lt(60)
        vlocka(n - 1, d / 3)
        t.rt(120)
        vlocka(n - 1, d / 3)
        t.lt(60)
        vlocka(n - 1, d / 3)

def sneh_vlocka(n, d):
    for i in range(3):
        vlocka(n, d)
        t.rt(120)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
t.lt(120)
sneh_vlocka(4, 300)
_images/12_12.png

Ak namiesto jedného volania funkcie vlocka() zapíšeme nakreslenie aj všetkých predchádzajúcich úrovní krivky, dostávame tiež zaujímavú kresbu:

import turtle

def vlocka(n, d):
    if n == 0:
        t.fd(d)
    else:
        vlocka(n - 1, d / 3)
        t.lt(60)
        vlocka(n - 1, d / 3)
        t.rt(120)
        vlocka(n - 1, d / 3)
        t.lt(60)
        vlocka(n - 1, d / 3)

def sneh_vlocka(n, d):
    for i in range(3):
        vlocka(n, d)
        t.rt(120)

turtle.delay(0)
t = turtle.Turtle()
#t.speed(0)
t.lt(120)
for i in range(5):
    sneh_vlocka(i, 300)
_images/12_13.png

Ďalšie fraktálové krivky

Špeciálnou skupinou rekurzívnych kriviek sú fraktály (pozri aj na wikipédii). Už pred érou počítačov sa s nimi „hrali“ aj významní matematici (niektoré krivky podľa nich dostali aj svoje meno, aj snehová vločka je fraktálom a vymyslel ju švédsky matematik Koch). Zjednodušene by sme mohli povedať, že fraktál je taká krivka, ktorá sa skladá z viacerých svojich zmenšených kópií. Keby sme sa na nejakú jej časť pozreli lupou, videli by sme opäť skoro tú istú krivku. Napr. aj binárne stromy a aj snehové vločky sú fraktály.

C-krivka

Začneme veľmi jednoduchou, tzv. C-krivkou:

import turtle

def ckrivka(n, s):
    if n == 0:
        t.fd(s)
    else:
        ckrivka(n - 1, s)
        t.lt(90)
        ckrivka(n - 1, s)
        t.rt(90)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
t.ht()
ckrivka(9, 4)    # skúste aj: ckrivka(13, 2)
_images/12_14.png

Dračia krivka

C-krivke sa veľmi podobá Dračia krivka, ktorá sa skladá z dvoch „zrkadlových“ funkcií: ldrak a pdrak. Všimnite si zaujímavú vlastnosť týchto dvoch rekurzívnych funkcií: prvá rekurzívne volá samu seba ale aj druhú a druhá volá seba aj prvú. Našťastie Python toto zvláda veľmi dobre:

import turtle

def ldrak(n, s):
    if n == 0:
        t.fd(s)
    else:
        ldrak(n - 1, s)
        t.lt(90)
        pdrak(n - 1, s)

def pdrak(n, s):
    if n == 0:
        t.fd(s)
    else:
        ldrak(n - 1, s)
        t.rt(90)
        pdrak(n - 1, s)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
t.ht()
ldrak(12, 6)
_images/12_15.png

Dračiu krivku môžeme nakresliť aj len jednou funkciou - táto bude mať o jeden parameter u viac a to, či je to ľavá alebo pravá verzia funkcie:

import turtle

def drak(n, s, u=90):
    if n == 0:
        t.fd(s)
    else:
        drak(n - 1, s, 90)
        t.lt(u)
        drak(n - 1, s, -90)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
t.ht()
drak(14, 2)
_images/12_16.png

Hilbertova krivka

V literatúre je veľmi známou Hilbertova krivka, ktorá sa tiež skladá z dvoch zrkadlových častí (ako dračia krivka) a preto ich definujeme jednou funkciou a parametrom u (t.j. uhol pre ľavú a pravú verziu):

import turtle

def hilbert(n, s, u=90):
    if n > 0:
        t.lt(u)
        hilbert(n - 1, s, -u)
        t.fd(s)
        t.rt(u)
        hilbert(n - 1, s, u)
        t.fd(s)
        hilbert(n - 1, s, u)
        t.rt(u)
        t.fd(s)
        hilbert(n - 1, s, -u)
        t.lt(u)

turtle.delay(0)
t = turtle.Turtle()
t.speed(0)
t.ht()
hilbert(5, 7)          # vyskúšajte: hilbert(7, 2)
_images/12_17.png

Ďalšie inšpirácie na rekurzívne krivky môžete nájsť na wikipédii.



Cvičenia

L.I.S.T.

  1. Zisti ručne bez Pythonu, čo urobí táto rekurzívna funkcia.

    • def hviezdicky(n):
          if n == 0:
              pass
          else:
              print ("*" * n)
              hviezdicky(n - 1)
      
      hviezdicky(6)
      
    • prekontroluj Pythonom


  1. Keďže funkcia z predchádzajúceho príkladu je chvostová rekurzia, prepíš ju bez rekurzie len pomocou cyklu.

    • def hviezdicky_nerek(n):
          ...
      
      hviezdicky_nerek(6)
      
    • Otestuj pre rôzne n, či dáva rovnaké výsledky ako rekurzívna verzia.


  1. Ručne bez spúšťania zisti čo robí táto funkcia:

    • rekurzívna funkcia:

      def alpha(pismeno):
          if pismeno == 'A':
              return 'A'
          else:
              return pismeno + alpha(chr(ord(pismeno) - 1))
      
      print(alpha('H'))
      

  1. Ručne bez spúšťania zisti, čo urobí funkcia test(m):

    • def test(n):
          s = 0
          while n:
              s += n + test(n - 1)
              n -= 1
          return s
      
      print(test(3))
      
    • prekontroluj svoj výsledok spustením v Pythone

    • čo je v tejto funkcii triviálny prípad?


  1. Nasledujúca rekurzívna funkcia prechádza prvky postupnosti (zoznamu, n-tice alebo znakového reťazca):

    • def pocet_a(post):
          if len(post) == 0:
              return 0
          if post[0] == 'a':
              return 1 + pocet_a(post[1:])
          return pocet_a(post[1:])
      
    • všimni si, že v každom rekurzívnom prechode skontroluje ďalší prvok postupnosti a ďalej sleduje len postupnosť bez tohto prvého prvku; zisti bez počítača, čo vráti pre:

      pocet_a([1, 2, 'a', 4, 'A', 'a', 7])
      pocet_a('Bratislava')
      

  1. Napíš funkciu sucet(zoznam), ktorá vráti (return) súčet prvkov daného zoznamu, pritom prvky zoznamu, ktoré nie sú celými číslami, ignoruje. Nepoužívaj globálne premenné.

    • zapíš najprv nerekurzívne pomocou cyklu

    • potom ako rekurzívnu funkciu bez cyklov

    • napr.

      >>> sucet([1, 3, 4.0, 5, '6', 7])
      16
      
    • pri rekurzívnej funkcii si uvedom:

      • prázdny zoznam dá súčet 0 (triviálny prípad)

      • ak je prvým prvkom celé číslo, vypočítam (rekurzívne) súčet všetkých prvkov okrem prvého a k tomuto súčtu pripočítam prvý prvok zoznamu - tento súčet vrátim (return) ako výsledok funkcie

      • inak vypočítam súčet všetkých prvkov okrem prvého a toto bude výsledkom funkcie (return)


  1. Napíš funkciu prevod(retazec), ktorá z daného reťazca vyrobí celé číslo. Predpokladaj, že v reťazci sú len desiatkové cifry nejakého čísla a medzery, ktoré sa ale budú ignorovať. Nepoužívaj funkciu int() na prevod reťazca na číslo ani globálne premenné.

    • funkciu zapíš bez cyklu len pomocou rekurzie

    • napr.

      >>> prevod(' 2  01 8  ')
      2018
      
    • pri rekurzívnej funkcii si uvedom:

      • prázdny reťazec vráti výsledok 0 (triviálny prípad)

      • ak je posledným znakom nejaká cifra (znak medzi '0' a '9'), urobím (rekurzívne) prevod zvyšku reťazca (bez posledného znaku), tento prevod vynásobím 10 a pripočítam poslednú cifru (ako číslo) - tento súčet vrátim (return) ako výsledok funkcie

      • inak urobím (rekurzívne) prevod zvyšku reťazca (bez posledného znaku - ten je zrejme medzera) a toto bude výsledkom funkcie (return)


  1. Napíš rekurzívnu funkciu palindrom(postupnost), ktorá z ľubovoľnej postupnosti zistí (vráti True alebo False), či je to palindrom. Rieš to pomocou rekurzie: budeš kontrolovať zhodu prvého a posledného prvku postupnosti a potom aj postupnosť bez prvého a posledného prvku. Nepoužívaj globálne premenné.

    • napr.

      >>> palindrom('tahat')
      True
      >>> palindrom([1, 2, 3, 3, 2, 1])
      True
      

  1. Napíš funkciu min_max(zoznam), ktorá pre neprázdny zoznam vráti (return) dvojicu hodnôt (najmenší, najväčší) prvok. Funkcia nepoužíva štandardné funkcie min a max. Nepoužívaj globálne premenné.

    1. najprv rieš bez rekurzie pomocou jedného for-cyklu, svoje riešenie skontroluj napr.

      >>> min_max([5, 7, 2, 9, 4])
      (2, 9)
      
    2. vyrieš rekurzívne bez cyklov


  1. Napíš funkciu kontrola(zoznam), ktorá zistí (vráti True alebo False), či sú prvky v danom zozname v rastúcom poradí, t.j. pre každé i má platiť zoznam[i] <= zoznam[i + 1]

    1. najprv to zapíš nerekurzívne while-cyklom, pričom podmienkou v cykle bude iba len(zoznam) > 1; zrejme budeš v cykle skracovať tento zoznam o prvý prvok

    2. potom to zapíš rekurzívne bez cyklu tak, že skontroluješ prvé dva prvky a ak spĺňajú podmienku, rekurzívne to otestuješ aj pre zoznam bez prvého prvku - toto riešenie by malo fungovať pre kratšie zoznamy, napr. zoz = list(range(500)), ale nebude fungovať pre dlhší zoznam zoz = list(range(500)) + list(range(500, 1000)); vieš prečo?

    3. prepíš rekurzívnu verziu takto:

      • ak má zoznam aspoň dva prvky, vypočítaj index stred = len(zoznam) // 2

      • skontroluj, či zoznam[stred - 1] <= zoznam[stred] a ak áno, rekurzívne skotroluj prvú aj druhú polovicu zoznamu

    • Nepoužívaj globálne premenné.


  1. Napíš funkciu prvky(zoznam), ktorá z ľubovoľného zoznamu, ktorý môže obsahovať aj iné (vnorené) zoznamy, vráti zoznam (typu list) všetkých prvkov (nezoznamov), ktoré sa v týchto zoznamoch nachádzajú. Nepouži cyklus ale rekurziu. Nepoužívaj globálne premenné.

    • otestujte napr.

      >>> prvky([2, [['4a']], [1, [2, 3.14]], 8])
      [2, '4a', 1, 2, 3.14, 8]
      >>> prvky([[[], []], []])
      []
      

  1. Do funkcie strom, pomocou ktorej korytnačka nakreslí binárny strom, dopíš kreslenie farebných bodiek (t.dot(10, farba)) na koncoch všetkých vetvičiek. Farbu každej bodky zvoľ náhodne z ('green', 'red', 'yellow').

    • def strom(d):
          t.fd(d)
          if d > 10:
              t.lt(40)
              strom(d * 0.7)
              t.rt(75)
              strom(d * 0.6)
              t.lt(35)
          t.bk(d)
      
      t.lt(90)
      strom(100)
      
    • napr.

      _images/12_12c.png

  1. Ručne na papieri zisti, aké obrázky nakreslí korytnačka pre rôzne volania funkcie.

    • rekurzívna funkcia:

      def obrazok(n, d):
          if n == 0:
              t.fd(d)
          else:
              for u in 90, 180, 90, 0:
                  obrazok(n - 1, d)
                  t.lt(u)
      
    • postupne odkrokuj (bez počítača):

      obrazok(0, 50)
      obrazok(1, 50)
      obrazok(2, 50)
      obrazok(3, 50)
      
    • postupne skontroluj v Pythone tieto aj ďalšie:

      obrazok(4, 20)
      obrazok(5, 10)
      

  1. Napíš funkciu stvorce(n, d), pomocou ktorej korytnačka nakreslí takýto rekurzívny obrázok:

    • pre n = 0 nekreslí nič (napr. pass)

    • pre väčšie n nakreslí štvorec so stranou d pričom v každom vrchole tohto štvorca rekurzívne zavolá stvorce s menším n aj d (napr. stvorce(n - 1, d / 3))

    • napr.

      _images/12_14c.png


5. Domáce zadanie

L.I.S.T.

Napíšte pythonovský skript, v ktorom zadefinujete štyri funkcie na prácu so zoznamami. Vstupom pre všetky tieto funkcie bude zoznam, ktorý môže obsahovať čísla, reťazce, ale aj ďalšie podzoznamy. Tieto podzoznamy môžu opäť obsahovať ďalšie podzoznamy, atď. Napríklad aj takýto zoznam ['a', ['dom', [2], 3], [], [[[2]]], 'b'] môže byť vstupom do vašich funkcií.

zoznam_prvkov()

Funkcia zoznam_prvkov(zoznam) vráti sploštený zoznam prvkov daného zoznamu, teda taký, ktorý už neobsahuje žiadne podzoznamy. Napr.

>>> print(zoznam_prvkov([1, 2, 3, [4, 5], 6, [[[7]]], [], 8]))
[1, 2, 3, 4, 5, 6, 7, 8]
>>> print(zoznam_prvkov(['a', ['dom', [2], 3], [], [[[2]]], 'b']))
['a', 'dom', 2, 3, 2, 'b']
>>> print(zoznam_prvkov([[], [[[]]], []]))
[]
>>> zoz = [[[7]], 8]
>>> print(zoznam_prvkov(zoz))
[7, 8]
>>> zoz
[[[7]], 8]

Pôvodný zoznam pri tom ostane bez zmeny.

splosti()

Funkcia splosti(zoznam) sploští daný vstupný zoznam. Na rozdiel od predchádzajúcej funkcie táto nič nevracia, len modifikuje vstupný zoznam. Napr.

>>> zoz = [[[7]], 8]
>>> print(splosti(zoz))
None
>>> zoz
[7, 8]
>>> p = [1, 2, 3, [4, 5], 6, [[[7]]], [], 8]
>>> splosti(p)
>>> p
[1, 2, 3, 4, 5, 6, 7, 8]

nahradeny_zoznam()

Funkcia nahradeny_zoznam(zoznam, hodnota1, hodnota2) vráti kópiu pôvodného zoznamu, v ktorom budú všetky prvky vstupného zoznamu s hodnotou hodnota1 nahradené hodnotou hodnota2. Ak sú nejakými prvkami opäť zoznamy, tak bude hodnota1 nahradená hodnotou2 aj v týchto zoznamoch, aj ich podzoznamoch atď. Napr.

>>> zoz = [[[7]], 8]
>>> print(nahradeny_zoznam(zoz, 7, 'a'))
[[['a']], 8]
>>> zoz
[[[7]], 8]
>>> print(nahradeny_zoznam([1, 2, 3, [1, 2], 3, [[[1]]], [], 2], 1, 'x'))
['x', 2, 3, ['x', 2], 3, [[['x']]], [], 2]
>>> print(nahradeny_zoznam([3, [33, [333, [13], 13]], 36], 3, 'q'))
['q', [33, [333, [13], 13]], 36]
>>> print(nahradeny_zoznam([3, [33, [333, [13], 13]], 36], [13], 'm'))
[3, [33, [333, 'm', 13]], 36]

nahrad()

Funkcia nahrad(zoznam, hodnota1, hodnota2) nahradí v danom zozname zoznam všetky prvky s hodnotou hodnota1 hodnotou hodnota2. Ak sú nejakými prvkami opäť zoznamy, tak nahrádza aj v týchto zoznamoch, aj v ich podzoznamoch atď. Funkcia nič nevracia, len modifikuje vstupný zoznam. Napr.

>>> zoz = [[[7]], 8]
>>> print(nahrad(zoz, 7, 'a'))
None
>>> zoz
[[['a']], 8]
>>> p = [1, 2, 3, [1, 2], 3, [[[1]]], [], 2]
>>> nahrad(p, 1, 'x')
>>> p
['x', 2, 3, ['x', 2], 3, [[['x']]], [], 2]
>>> p = [1, 2, 3, [1, 2], 3, [[[1]]], [], 2]
>>> nahrad(p, 4, 'z')
>>> p
[1, 2, 3, [1, 2], 3, [[[1]]], [], 2]
>>> p = ['a', ['dom', [2], 3], [], [[[2]]], 'b']
>>> nahrad(p, 2, 'abc')
>>> p
['a', ['dom', ['abc'], 3], [], [[['abc']]], 'b']

Nemeňte mená funkcií a parametrov. Zrejme využijete rekurziu.

Váš odovzdaný program s menom riesenie5.py musí začínať tromi riadkami komentárov:

# 5. zadanie: zoznamy
# autor: Janko Hraško
# datum: 20.11.2018

Projekt riesenie5.py odovzdávajte na úlohový server https://list.fmph.uniba.sk/ najneskôr do 23:00 28. novembra, kde ho môžete nechať otestovať. Testovač bude spúšťať vaše funkcie s rôznymi vstupmi. Odovzdať projekt aj ho testovať môžete ľubovoľný počet krát. Môžete zaň získať 10 bodov.