Thonny harrastab rekursiooni

Rekursiivse funktsiooni toimimisest ei pruugi olla lihtne aru saada. Võtame näitlikustamisel appi Thonny silumisvõimalused. Tavaliselt oleme programmi käivitanud ja see on oma töö praktiliselt silmapilkselt ära teinud. Nüüd aga kasutame võimalust Run --> Debug current script, mille abil saame programmi tööd sammukaupa jälgida. Järgmise sammu tegemiseks on mitu võimalust. Esialgu on sobiv kasutada varianti Step into (F7).

Vaatame eelmises peatükis toodud faktoriaali arvutamise programmi.

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

print(faktoriaal(4))

Kui paneksime programmi tavapäraselt tööle (Run --> Run current script (F5)), siis saaksime vastuse 24, kuid vahepealse töö kohta infot mitte. Run –> Debug current script abil aga värvub osa koodist kollaseks, mis näitab, kuhu programmi täitmine on jõudnud. Esimese sammuna värvub funktsiooni kirjeldus – see funktsioon “õpitakse” selgeks.

Kui sammhaaval edasi minna (Step into (F7)), siis jõuame varsti seisuni, kus faktoriaal(4) arvutamiseks ilmub uus aken:

See demonstreerib, et funktsiooni rakendamine on küllaltki iseseisev. Kui nüüd edasi “sammuda”, siis varsti tuleb arvutada faktoriaal(3), isegi enne, kui faktoriaal(4) lõplikult leitud saab. Sellega ilmub uus aken:

Edasi sammudes ilmub järjest uusi aknaid, kuni lõpuks jõuame faktoriaal(0), mis ometigi konkreetse tulemuse (1) tagastab.

Nüüd hakkavad aknad järjest sulguma, sest funktsioonid saavad järjest oma vajalikud andmed kätte ning suudavad nende abil oma töö lõpetada. Lõpuks jõuab ekraanile tulemus 24.

Sarnaselt saab läbi mängida ka teised programmid, mille tööst hästi aru ei saa.

Rekursiivne väljakutse

Rekursiivsetes funktsioonides võib rekursiivne väljakutse paikneda erinevates kohtades. Näiteks järgmises programmis on see vastava haru viimane tegevus:

def print_alla(n):
    if n <= 0:
        print("Stop!")
    else:
        print(n)
        print_alla(n - 1)

Püüa enne programmi käivitamist ennustada, mis ilmub ekraanile järgmistel juhtudel:

print_alla(4)
print_alla(0)
print_alla(-4)

Näeme, et lause print(n) on enne rekursiivset väljakutset ja ekraanile väljastatakse n väärtus, mis on just selles konkreetses print_alla väljakutses. Kuna iga järgmine väljakutse on ühe võrra väiksema argumendiga (n - 1), siis ilmuvad ka arvud ekraanile kahanevas järjekorras.

Muudame nüüd print(n) ja print_alla(n - 1) järjekorda:

def print_kuhu(n):
    if n <= 0:
        print("Stop!")
    else:
        print_kuhu(n - 1)
        print(n)

Püüa enne erinevate argumentidega käivitamist ennustada, mis ekraanile ilmub:

print_kuhu(4)
print_kuhu(0)
print_kuhu(-4)

Paneme tähele, et nüüd on print(n) pärast rekursiivset väljakutset. Seega enne, kui midagi ekraanile väljastatakse, “avanevad” kõik print_kuhu väljakutsed. Lõpuks ilmub print_kuhu(0) toimel ekraanile Stop!. Seejärel hakkavad väljakutsed järjest “sulguma”. Vahetult oma töö lõpus väljastab väljakutse ekraanile n väärtuse, mis selles väljakutses hetkel on. Oluline on märgata, et igas väljakutses on n väärtus teiste omadest sõltumatu.

Selles programmis ilmusid arvud ekraanile kasvavas järjekorras. Võib öelda, et enne rekursiivset väljakutset tehtavad tegevused toimuvad “kahanevalt”. Pärast rekursiivset väljakutset tehtavad tegevused toimuvad “kasvavalt”:

def print_ules(n):
    if n <= 0:
        print("Stop!")
    else:
        print_ules(n-1)
        print(n)

Mis juhtub siis, kui väljastamise käsk on nii enne kui ka pärast rekursiivset väljakutset?

def print_alla_ules(n):
    if n <= 0:
        print("Stop!")
    else:
        print(n)
        print_alla_ules(n - 1)
        print(n)

Rekursioon sõnede ja järjenditega

Senised rekursioonide näited on põhiliselt olnud seotud arvudega. Nüüd vaatleme ka teisi andmetüüpe. Näiteks saab rekursiivselt kontrollida, kas sõne on palindroom – algusest või lõpust loetult sama. Kontrollimisel kasutatakse asjaolu, et sõne on palindroom juhul, kui tema esimene ja viimane sümbol on sama ning nende vahele jääv alamsõne on samuti palindroom. Nii saamegi rekursiivse funktsiooni, kus baasiks on ühesümboliline või tühi sõne, mida saame lugeda palindroomiks. Alamsõne leidmiseks on kasutatud viilutamist: s[1:-1] puhul on alamsõne alguse indeks (kaasa arvatud) 1 ja lõpu indeks (välja arvatud) -1.

def on_palindroom(s):
    if len(s) <= 1:
        return True
    else:
        return s[0] == s[-1] and on_palindroom(s[1:-1])

Järjendi pikkuse leidmiseks on olemas spetsiaalne funktsioon len.

Kirjutame nüüd ise funktsiooni, millega järjendi pikkust leida. Vaatleme kahte varianti – üks tsükliga ja teine rekursiooniga.

Tsükliga liidetakse loendurile igat järjendi elementi vaadeldes 1:

def pikkus(loend):
    i = 0
    for c in loend:
        i += 1
    return i

Rekursiooniga kasutame baasina asjaolu, et tühja listi pikkus on 0. Muul juhul on listi pikkus 1 pluss sellise alamlisti pikkus, kust on välja jäetud esimene element.

def rpikkus(loend):
    if loend == []:
        return 0
    else:
        return 1 + rpikkus(loend[1:])

Lõpuks tuleme arvude juurde tagasi ja vaatleme astendamise funktsiooni. Baasi saame teadmisest, et iga arv astmes 0 on 1. Igal rekursiooni sammul arvutatakse arvu ühe võrra väiksem aste.

def aste(n, m):
    if m == 0:
        return 1
    else:
        return n * aste(n, m-1)