Rekursioon
Funktsioonist kordavalt
Oleme kasutanud erinevaid funktsioone – osa neist on olnud Pythonis valmis või oleme need importinud mõnest moodulist, teised oleme ise defineerinud.
Meenutame, et funktsioon tagastab väärtuse, mis määratakse võtmesõna return abil. Kui seda ei tehta, siis tagastatakse spetsiaalne väärtus None (eesti keeles “mitte miski”). Ilma tagastusväärtuseta funktsioonide roll on lihtsalt midagi ära teha, nt print väljastab oma argumendi(d) ekraanile, kuid ei tagasta midagi.
Olgu meil järgmine programm:
def summa(a, b):
return a + b
def topelt_summa(a, b):
return 2 * summa(a, b)
print(summa(3, 4))
Näeme, et funktsioon summa on kutsutud välja funktsiooni topelt_summa
definitsioonis ja ka põhiprogrammis (funktsiooni print argumendina). Veel saab funktsiooni välja kutsuda Thonny käsureaaknas (Shell):
>>> summa(5, 7) 12
Rekursiivne väljakutse
Eespool kutsuti üks funktsioon välja teise funktsiooni definitsioonis. Tegelikult saab funktsiooni välja kutsuda tema enda definitsioonis. Sellisel juhul on tegemist rekursiivse väljakutsega. Rekursioon on funktsioonide defineerimise viis, kus defineeritav funktsioon kutsub välja iseennast (kuid erineva argumendi väärtusega).
Rekursioon sobib hästi selliste ülesannete lahendamiseks, kus tervikülesannet saab jaotada “väiksemateks” samasugusteks ülesanneteks. Oluline on, et lõpuks oleks need “väiksemad” ülesanded nii väikesed, et nende lahendamine oleks väga lihtne.
Üks tuntumaid rekursiooni näiteid on faktoriaali arvutamine. Positiivse täisarvu n faktoriaal (tähistus n!) on n esimese positiivse täisarvu korrutis. Näiteks 4! = 1 · 2 · 3 · 4 = 24. Eraldi on kokku lepitud, et 0! = 1, samuti 1! = 1. Rekursiivsena saab faktoriaali leidmist kirjeldada nii, et iga järgmise arvu faktoriaali saame esitada eelmise arvu faktoriaali abil. Näiteks 4! = 4 · 3! ja omakorda 3! = 3 · 2! ning 2! = 2 · 1!. Lõpuks 1! = 1 või kui tahame ka 0 mängu võtta, siis võime öelda ka, et 1! = 1 · 0! ja 0! = 1. Üldistatult saame kaks olukorda:
- n! = 1, kui n = 0
- n! = n · (n-1)!, kui n > 0
Programselt saame selle funktsiooni kirja panna järgnevalt:
def faktoriaal(n):
if n == 0: # Rekursiooni baas
return 1
else: # Rekursiooni samm
return n * faktoriaal(n-1)
print(faktoriaal(4))
print(faktoriaal(0))
print(faktoriaal(400))
Korrektses rekursiivses funktsioonis on alati mitu haru. Protsessi lõppemiseks peab vähemalt üks haru olema ilma rekursiivse väljakutseta. Seda haru nimetatakse rekursiooni baasiks. Rekursiivse väljakutsega haru nimetatakse rekursiooni sammuks. Rekursiivsete väljakutsetega võib olla ka mitu haru. Samuti võib harva olla kasulik määrata mitu erinevat rekursiooni baasi.
Enesekontroll
Mõned näited
Sarnaselt tsüklile võimaldab rekursioon kirjeldada korduvtäidetavaid protsesse.
Mänguliselt saab rekursiooni ja ka teisi programmeerimise kontruktsioone harjutada mängus Lightbot. Tasemetel 3.1 ja 3.2 saabki hakkama ainult nii, et protseduur iseennast välja kutsub.
Proovi, mida teeb järgmine programm.
def rek_fun(n):
if n > 0:
print("Põhi!")
else:
print(n)
rek_fun(n + 2)
rek_fun(-7)
Proovi programmi muuta ja käivita uuesti. Näiteks võib n > 0 asendada mõne muu tingimusega või muuta ridade print(n) ja rek_fun(n + 2) järjekorda.
Rekursiivne funktsioon on tegelikult tavaline Pythoni funktsioon. Seega võib tal olla ka mitu argumenti.
Enesekontroll
Rekursiooni kasutatakse laialdaselt programmeerimises, arvutiteaduses ja matemaatikas, samuti keeleteaduses, muusikas, kunstis jne.
Kunstis võib välja tuua näiteks Maurits Cornelis Escheri (1898-1972) tööd.
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)
Meenutusi funktsioonist
Programmeerimises on äärmiselt tähtis uute alamprogrammide loomine. Tegelikult suuresti selles programmeerimine seisnebki. Pythonis nimetetakse alamprogramme funktsioonideks. Varasemas oleme funktsioone juba paljudes kohtades rakendanud ehk välja kutsunud. Kui funktsioon on defineeritud, aga seda pole veel rakendatud, siis on tegemist nagu ükskõik millise tarbeeseme või masinaga, mis on küll olemas, aga mida (veel) ei kasutata.
Eespool oleme funktsioone rakendanud n-ö põhiprogrammis, aga ka teiste funktsioonide kirjeldustes. Näiteks järgmises programmis on põhiprogrammis kaks korda rakendatud funktsiooni ruut. Funktsiooni ruut kirjelduses aga on kasutatud funktsioone forward ja left.
from turtle import *
def ruut(): # Defineerime funktsiooni nimega ruut
i = 0
while i < 4:
forward(100)
left(90)
i = i + 1
ruut() # Kutsume funktsiooni ruut välja. Kilpkonn joonistab ruudu küljega 100 pikslit
right(45) # Pöörame paremale 45°
ruut() # Kutsume uuesti funktsiooni ruut välja
exitonclick()
Rekursioon
Tegelikult saab funktsiooni välja kutsuda ka selle sama funktsiooni sisemuses. Esialgu võib see tunduda võõras – kuidas siis saab nii olla, et nagu õpetaksime mingit uut asja tegema sellesama asja abil, mida praegu õpetame?! Tegemist on rekursiooniga – arvutiteaduse ühe alusmõistega. Reeglina rekursiooni algkursusel ei käsitleta, siingi on see silmaringi materjalide hulgas. Kuna aga tegemist on niivõrd kena ja põneva teemaga, siis ei saa jätta ka selle kursuse huvilisi sellest ilma. Küll aga palun mitte nukrutseda, kui mingid kohad selles osas liiga keerulised tunduvad. Jätke need julgesti vahele! Nädala lõputestis siiski ühtteist on vaja teada.
Rekursioon sobib eriti hästi selliste ülesannete lahendamiseks, kus tervikülesanne koosneb mingis mõttes sarnastest, kuid väiksematest alamülesannetest. Kui põhiülesannet piisavalt kaua alamülesanneteks jagades muutuvad alamülesanded nii väikeseks, et väiksemaks enam minna ei saa või ei taha, siis võiks püüda seda protsessi rekursiivselt esitada.
Klassikaline rekursiooni näide on faktoriaali arvutamine. Positiivse täisarvu n faktoriaal (tähistus n!) on n esimese positiivse täisarvu korrutis. Näiteks 4! = 1 · 2 · 3 · 4 = 24. Eraldi on kokkulepitud, et 0! = 1. Muidugi ka 1! = 1. Rekursiivsena saab faktoriaali leidmist kirjeldada nii, et iga järgmise arvu faktoriaali saame esitada eelmise arvu faktoriaali abil. Näiteks 4! = 4 · 3! ja omakorda 3! = 3 · 2! ning 2! = 2 · 1!. No ja 1! = 1 või kui tahame 0 ka mängu võtta, siis võime öelda ka, et 1! = 1 · 0! ja 0! = 1. Üldistatult saame kaks haru:
- n! = 1, kui n = 0
- n! = n · (n-1)!, kui n > 0
Programm aga on siis selline.
def faktoriaal(n):
if n == 0: # Rekursiooni baas
return 1
else: # Rekursiooni samm
return n * faktoriaal(n-1)
print(faktoriaal(4))
print(faktoriaal(0))
print(faktoriaal(400))
Rekursiivsetes programmides ongi alati mitu haru. Selleks, et protsess üldse kunagi lõppeks, peab vähemalt üks haru olema ilma rekursiivse väljakutseta. Seda haru nimetatakse rekursiooni baasiks. Rekursiivse väljakutsega (st sellesama funktsiooni väljakutsumisega) haru nimetatakse rekursiooni sammuks.
Rekursiooniga on seotud mitmed elulised teemad, näiteks küülikute paljunemise modelleerimine Fibonacci arvude abil jpm. Meie läheme aga visuaalsemate teemade juurde – hakkame vaatlema puid.
Korrapärane puu
Olgu meie eesmärgiks saada selline puu.
Natuke terasemal vaatlemisel märkame, et puu iga haru on ise ka omakorda samasugune puu, aga väiksem. Tolle väiksema puu iga haru on jällegi veel väiksem puu. Selliseid kujundeid, kus osa on terviku sarnane, nimetatakse fraktaliteks.
Teoreetiliselt võime lõpmatult joonistada puule väiksemaid oksi, aga praktiliselt poleks sel mõtet ja piiri seadmiseks võtame appi rekursiooni baasi. Näiteprogrammis jõuame rekursiooni baasini, kui järjekordse puu “tüve” pikkus on väiksem kui 5. Sellisel juhul joonistamegi ainult tüve, milleks liigume vastava arvu samme edasi ja kohe tagasi.
Rekursiooni sammu puhul aga joonistame tüve ja kaks haru, mis on omakorda ka puud, aga väiksemad (korrutame teguriga 0,6). Harude joonistamise eel, vahel ja järel tuleb kilpkonna ka sobivalt pöörata.
Palun pange see programm tööle, näete ka, kui kaua kilpkonnal see joonistamine aega võtab. Selleks, et joonis kiiremini tekiks, võib kasutada funktsioone delay(0) ja speed(10).
from turtle import *
def puu(pikkus):
if pikkus < 5: # Rekursiooni baas
forward(pikkus) # Ainult tüvi
back(pikkus)
else: # Rekursiooni samm
forward(pikkus) # Tüvi
left(45)
puu(0.6 * pikkus) # Haru, mis on väiksem puu
right(90)
puu(0.6 * pikkus) # Teine haru, mis on ka väiksem puu
left(45)
back(pikkus) # Tüvepidi tagasi
delay(0)
speed(10)
left(90)
puu(100)
exitonclick()
Videod
Rekursioon I: https://panopto.ut.ee/Panopto/Pages/Viewer.aspx?id=adfad889-a245-439c-9b82-ac7800b17785
Rekursioon II: https://panopto.ut.ee/Panopto/Pages/Viewer.aspx?id=dd6910ed-9eaa-4f49-b4ec-ac7800cbeed6
Kasutatud allikad: