Materjalid koostas ja kursuse viib läbi
Tartu Ülikooli arvutiteaduse instituudi programmeerimise õpetamise töörühm
Kilpkonn joonistab rekursiivselt puid
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 lisamaterjalide 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! Võite kasvõi lihtsalt pilte vaadata.
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, 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 maalähedased 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 on 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.
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
left(90)
puu(100)
exitonclick()
Loobume sümmeetriast
Eelmine puu oli meil väga korrapärane ja sümmeetriline. Loobume sellest, et puu peaks sümmeetriline olema. Muudame programmi nii, et enam ei pöörataks 45 kraadi vasakule, 90 paremale ja 45 vasakule. Olgu näiteks vasakule pöörded 40 ja 50 kraadi.
from turtle import *
def puu(pikkus):
if pikkus < 5:
forward(pikkus)
back(pikkus)
else:
forward(pikkus)
left(40) # Pöörame nüüd hoopis 40 kraadi
puu(0.6 * pikkus)
right(90)
puu(0.6 * pikkus)
left(50) # ja siin 50 kraadi
back(pikkus)
left(90)
puu(100)
exitonclick()
Näeme, et puu on tõesti natuke ebasümmeetriline.
Päriselt puudel muidugi kõik harud ühepikkused pole. Proovime meiegi nii, et ühes harus oleks tegur endiselt 0,6 aga teisel hoopis 0,5.
from turtle import *
def puu(pikkus):
if pikkus < 5:
forward(pikkus)
back(pikkus)
else:
forward(pikkus)
left(40)
puu(0.6 * pikkus) # Tegur endiselt 0.6
right(90)
puu(0.5 * pikkus) # Tegur on nüüd 0.5
left(50)
back(pikkus)
left(90)
puu(100)
exitonclick()
Juhuslik puu
Väga põnevaid võimalusi annab juhuslike arvude kasutamine. Nii annab sama programm erineval korral erinevaid tulemusi. Muudame programmi nii, et iga haru joonistamisel määratakse tegur, millega pikkus korrutatakse, juhuslikult. Funktsiooniga randrange(6,8) saame juhusliku arvu 6 või 7. Selleks, et saada 0,6 või 0,7 jagame arvuga 10.
from turtle import *
from random import * # Juhuslike arvude moodul
def puu(pikkus):
if pikkus < 5:
forward(pikkus)
back(pikkus)
else:
forward(pikkus)
left(40)
puu(randrange(6,8) / 10 * pikkus) # Tegur on 0.6 või 0.7
right(90)
puu(randrange(6,8) / 10 * pikkus) # Tegur on 0.6 või 0.7
left(50)
back(pikkus)
left(90)
puu(100)
Ühel juhul tuli selline puu.
Teeme nüüd programmi, mis paneb mitu juhusliku suurusega puud kõrvuti.
from turtle import *
from random import *
def puu(pikkus):
if pikkus < 5:
forward(pikkus)
back(pikkus)
else:
forward(pikkus)
left(45)
puu(randrange(6,8) / 10 * pikkus)
right(90)
puu(randrange(6,8) / 10 * pikkus)
left(45)
back(pikkus)
def mets(puudearv):
i = 0
left(90)
while i < puudearv:
pendown()
puu(randrange(20,60)) # Juhusliku pikkusega puu
penup()
right(90)
forward(randrange(100,150)) # Puude vahe on ka juhuslik
left(90)
i = i + 1
mets(4)
exitonclick()
Antud juhul on siis nelja puuga mets.
Korrast kaoseni
Kuigi me mitmeid asju muutsime ja lasime isegi juhuslikult arvutada, meenutasid saadud kujundid ikkagi puid. Teeme nüüd näiliselt suhteliselt väikese muudatuse, nimelt muudame ühe pööramise 45 kraadi asemel 44 kraadiks. Tõenäoliselt me silmaga nendel nurkadel vahet ei teeks.
from turtle import *
from random import *
def puu(pikkus):
if pikkus < 5:
forward(pikkus)
back(pikkus)
else:
forward(pikkus)
left(44)
puu(randrange(6,8) / 10 * pikkus)
right(90)
puu(randrange(6,8) / 10 * pikkus)
left(45)
back(pikkus)
left(90)
puu(100)
exitonclick()
Mis aga juhtub kujundiga?
Näeme, et puuga enam tegemist pole. Väike muudatus viis meid hoopis teise kujundi juurde. Fraktalite puhul nii kipubki olema, et vahel on väike muudatus väga olulise tähendusega.