{"id":559,"date":"2020-12-28T19:22:04","date_gmt":"2020-12-28T19:22:04","guid":{"rendered":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/?post_type=chapter&#038;p=559"},"modified":"2020-12-28T19:57:37","modified_gmt":"2020-12-28T19:57:37","slug":"rekursioon-ja-kilpkonnagraafika","status":"publish","type":"chapter","link":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/chapter\/rekursioon-ja-kilpkonnagraafika\/","title":{"raw":"Lisalugemine. Rekursioon ja kilpkonnagraafika","rendered":"Lisalugemine. Rekursioon ja kilpkonnagraafika"},"content":{"raw":"<h1>Meenutusi funktsioonist<\/h1>\r\nProgrammeerimises on \u00e4\u00e4rmiselt t\u00e4htis uute alamprogrammide loomine. Tegelikult suuresti selles programmeerimine seisnebki. Pythonis nimetetakse alamprogramme funktsioonideks. Varasemas oleme funktsioone juba paljudes kohtades rakendanud ehk v\u00e4lja kutsunud. Kui funktsioon on defineeritud, aga seda pole veel rakendatud, siis on tegemist nagu \u00fcksk\u00f5ik millise tarbeeseme v\u00f5i masinaga, mis on k\u00fcll olemas, aga mida (veel) ei kasutata.\r\n\r\nEespool oleme funktsioone rakendanud n-\u00f6 p\u00f5hiprogrammis, aga ka teiste funktsioonide kirjeldustes. N\u00e4iteks j\u00e4rgmises programmis on p\u00f5hiprogrammis kaks korda rakendatud funktsiooni ruut. Funktsiooni ruut kirjelduses aga on kasutatud funktsioone <em>forward<\/em> ja <em>left<\/em>.\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">from turtle import *\r\n\r\ndef ruut(): # Defineerime funktsiooni nimega ruut\r\ni = 0\r\nwhile i &lt; 4:\r\nforward(100)\r\nleft(90)\r\ni = i + 1\r\n\r\nruut() # Kutsume funktsiooni ruut v\u00e4lja. Kilpkonn joonistab ruudu k\u00fcljega 100 pikslit\r\nright(45) # P\u00f6\u00f6rame paremale 45\u00b0\r\nruut() # Kutsume uuesti funktsiooni ruut v\u00e4lja\r\n\r\nexitonclick()<\/pre>\r\n<h1>Rekursioon<\/h1>\r\nTegelikult saab funktsiooni v\u00e4lja kutsuda ka selle sama funktsiooni sisemuses. Esialgu v\u00f5ib see tunduda v\u00f5\u00f5ras - kuidas siis saab nii olla, et nagu \u00f5petaksime mingit uut asja tegema sellesama asja abil, mida praegu \u00f5petame?! Tegemist on rekursiooniga - arvutiteaduse \u00fche alusm\u00f5istega. Reeglina rekursiooni algkursusel ei k\u00e4sitleta, siingi on see silmaringi materjalide hulgas. Kuna aga tegemist on niiv\u00f5rd kena ja p\u00f5neva teemaga, siis ei saa j\u00e4tta ka selle kursuse huvilisi sellest ilma. K\u00fcll aga palun mitte nukrutseda, kui mingid kohad selles osas liiga keerulised tunduvad. J\u00e4tke need julgesti vahele! N\u00e4dala l\u00f5putestis siiski \u00fchtteist on vaja teada.\r\n\r\nRekursioon sobib eriti h\u00e4sti selliste \u00fclesannete lahendamiseks, kus tervik\u00fclesanne koosneb mingis m\u00f5ttes sarnastest, kuid v\u00e4iksematest alam\u00fclesannetest. Kui p\u00f5hi\u00fclesannet piisavalt kaua alam\u00fclesanneteks jagades muutuvad alam\u00fclesanded nii v\u00e4ikeseks, et v\u00e4iksemaks enam minna ei saa v\u00f5i ei taha, siis v\u00f5iks p\u00fc\u00fcda seda protsessi rekursiivselt esitada.\r\n\r\nKlassikaline rekursiooni n\u00e4ide on faktoriaali arvutamine. Positiivse t\u00e4isarvu n faktoriaal (t\u00e4histus n!) on n esimese positiivse t\u00e4isarvu korrutis. N\u00e4iteks 4! = 1 \u00b7 2 \u00b7 3 \u00b7 4 = 24. Eraldi on kokkulepitud, et 0! = 1. Muidugi ka 1! = 1. Rekursiivsena saab faktoriaali leidmist kirjeldada nii, et iga j\u00e4rgmise arvu faktoriaali saame esitada eelmise arvu faktoriaali abil. N\u00e4iteks 4! = 4 \u00b7 3! ja omakorda 3! = 3 \u00b7 2! ning 2! = 2 \u00b7 1!. No ja 1! = 1 v\u00f5i kui tahame 0 ka m\u00e4ngu v\u00f5tta, siis v\u00f5ime \u00f6elda ka, et 1! = 1 \u00b7 0! ja 0! = 1. \u00dcldistatult saame kaks haru:\r\n<ul>\r\n \t<li>n! = 1, kui n = 0<\/li>\r\n \t<li>n! = n \u00b7 (n-1)!, kui n &gt; 0<\/li>\r\n<\/ul>\r\nProgramm aga on siis selline.\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">def faktoriaal(n):\r\n    if n == 0: # Rekursiooni baas\r\n        return 1\r\n    else: # Rekursiooni samm\r\n        return n * faktoriaal(n-1)\r\n\r\nprint(faktoriaal(4))\r\nprint(faktoriaal(0))\r\nprint(faktoriaal(400))<\/pre>\r\nRekursiivsetes programmides ongi alati mitu haru. Selleks, et protsess \u00fcldse kunagi l\u00f5ppeks, peab v\u00e4hemalt \u00fcks haru olema ilma rekursiivse v\u00e4ljakutseta. Seda haru nimetatakse rekursiooni baasiks. Rekursiivse v\u00e4ljakutsega (st sellesama funktsiooni v\u00e4ljakutsumisega) haru nimetatakse rekursiooni sammuks.\r\n\r\nRekursiooniga on seotud mitmed elulised teemad, n\u00e4iteks k\u00fc\u00fclikute paljunemise modelleerimine Fibonacci arvude abil jpm. Meie l\u00e4heme aga visuaalsemate teemade juurde - hakkame vaatlema puid.\r\n<h1>Korrap\u00e4rane puu<\/h1>\r\nOlgu meie eesm\u00e4rgiks saada selline puu.\r\n\r\n<img class=\"alignnone size-full wp-image-577\" src=\"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-content\/uploads\/sites\/18\/2020\/12\/puu100.png\" alt=\"\" width=\"301\" height=\"267\" \/>\r\n\r\nNatuke terasemal vaatlemisel m\u00e4rkame, et puu iga haru on ise ka omakorda samasugune puu, aga v\u00e4iksem. Tolle v\u00e4iksema puu iga haru on j\u00e4llegi veel v\u00e4iksem puu. Selliseid kujundeid, kus osa on terviku sarnane, nimetatakse fraktaliteks.\r\n\r\nTeoreetiliselt v\u00f5ime l\u00f5pmatult joonistada puule v\u00e4iksemaid oksi, aga praktiliselt poleks sel m\u00f5tet ja piiri seadmiseks v\u00f5tame appi rekursiooni baasi. N\u00e4iteprogrammis j\u00f5uame rekursiooni baasini, kui j\u00e4rjekordse puu \"t\u00fcve\" pikkus on v\u00e4iksem kui 5. Sellisel juhul joonistamegi ainult t\u00fcve, milleks liigume vastava arvu samme edasi ja kohe tagasi.\r\n\r\nRekursiooni sammu puhul aga joonistame t\u00fcve ja kaks haru, mis on omakorda ka puud, aga v\u00e4iksemad (korrutame teguriga 0,6). Harude joonistamise eel, vahel ja j\u00e4rel tuleb kilpkonna ka sobivalt p\u00f6\u00f6rata.\r\n\r\nPalun pange see programm t\u00f6\u00f6le, n\u00e4ete ka, kui kaua kilpkonnal see joonistamine aega v\u00f5tab. Selleks, et joonis kiiremini tekiks, v\u00f5ib kasutada funktsioone delay(0) ja speed(10).\r\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">from turtle import *\r\n\r\ndef puu(pikkus): \r\n    if pikkus &lt; 5: # Rekursiooni baas\r\n        forward(pikkus) # Ainult t\u00fcvi\r\n        back(pikkus)\r\n    else: # Rekursiooni samm\r\n        forward(pikkus) # T\u00fcvi\r\n        left(45)\r\n        puu(0.6 * pikkus) # Haru, mis on v\u00e4iksem puu\r\n        right(90)\r\n        puu(0.6 * pikkus) # Teine haru, mis on ka v\u00e4iksem puu\r\n        left(45)\r\n        back(pikkus) # T\u00fcvepidi tagasi\r\n\r\ndelay(0)\r\nspeed(10) \r\nleft(90)\r\npuu(100)\r\n\r\nexitonclick()<\/pre>\r\nRohkem saad lugeda rekursioonist ja kilpkonnagraafikast:\r\n\r\n<a href=\"https:\/\/courses.cs.ut.ee\/2017\/eprogalused\/spring\/Main\/Silmaring-rekursioon\">https:\/\/courses.cs.ut.ee\/2017\/eprogalused\/spring\/Main\/Silmaring-rekursioon<\/a>","rendered":"<h1>Meenutusi funktsioonist<\/h1>\n<p>Programmeerimises on \u00e4\u00e4rmiselt t\u00e4htis uute alamprogrammide loomine. Tegelikult suuresti selles programmeerimine seisnebki. Pythonis nimetetakse alamprogramme funktsioonideks. Varasemas oleme funktsioone juba paljudes kohtades rakendanud ehk v\u00e4lja kutsunud. Kui funktsioon on defineeritud, aga seda pole veel rakendatud, siis on tegemist nagu \u00fcksk\u00f5ik millise tarbeeseme v\u00f5i masinaga, mis on k\u00fcll olemas, aga mida (veel) ei kasutata.<\/p>\n<p>Eespool oleme funktsioone rakendanud n-\u00f6 p\u00f5hiprogrammis, aga ka teiste funktsioonide kirjeldustes. N\u00e4iteks j\u00e4rgmises programmis on p\u00f5hiprogrammis kaks korda rakendatud funktsiooni ruut. Funktsiooni ruut kirjelduses aga on kasutatud funktsioone <em>forward<\/em> ja <em>left<\/em>.<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">from turtle import *\r\n\r\ndef ruut(): # Defineerime funktsiooni nimega ruut\r\ni = 0\r\nwhile i &lt; 4:\r\nforward(100)\r\nleft(90)\r\ni = i + 1\r\n\r\nruut() # Kutsume funktsiooni ruut v\u00e4lja. Kilpkonn joonistab ruudu k\u00fcljega 100 pikslit\r\nright(45) # P\u00f6\u00f6rame paremale 45\u00b0\r\nruut() # Kutsume uuesti funktsiooni ruut v\u00e4lja\r\n\r\nexitonclick()<\/pre>\n<h1>Rekursioon<\/h1>\n<p>Tegelikult saab funktsiooni v\u00e4lja kutsuda ka selle sama funktsiooni sisemuses. Esialgu v\u00f5ib see tunduda v\u00f5\u00f5ras &#8211; kuidas siis saab nii olla, et nagu \u00f5petaksime mingit uut asja tegema sellesama asja abil, mida praegu \u00f5petame?! Tegemist on rekursiooniga &#8211; arvutiteaduse \u00fche alusm\u00f5istega. Reeglina rekursiooni algkursusel ei k\u00e4sitleta, siingi on see silmaringi materjalide hulgas. Kuna aga tegemist on niiv\u00f5rd kena ja p\u00f5neva teemaga, siis ei saa j\u00e4tta ka selle kursuse huvilisi sellest ilma. K\u00fcll aga palun mitte nukrutseda, kui mingid kohad selles osas liiga keerulised tunduvad. J\u00e4tke need julgesti vahele! N\u00e4dala l\u00f5putestis siiski \u00fchtteist on vaja teada.<\/p>\n<p>Rekursioon sobib eriti h\u00e4sti selliste \u00fclesannete lahendamiseks, kus tervik\u00fclesanne koosneb mingis m\u00f5ttes sarnastest, kuid v\u00e4iksematest alam\u00fclesannetest. Kui p\u00f5hi\u00fclesannet piisavalt kaua alam\u00fclesanneteks jagades muutuvad alam\u00fclesanded nii v\u00e4ikeseks, et v\u00e4iksemaks enam minna ei saa v\u00f5i ei taha, siis v\u00f5iks p\u00fc\u00fcda seda protsessi rekursiivselt esitada.<\/p>\n<p>Klassikaline rekursiooni n\u00e4ide on faktoriaali arvutamine. Positiivse t\u00e4isarvu n faktoriaal (t\u00e4histus n!) on n esimese positiivse t\u00e4isarvu korrutis. N\u00e4iteks 4! = 1 \u00b7 2 \u00b7 3 \u00b7 4 = 24. Eraldi on kokkulepitud, et 0! = 1. Muidugi ka 1! = 1. Rekursiivsena saab faktoriaali leidmist kirjeldada nii, et iga j\u00e4rgmise arvu faktoriaali saame esitada eelmise arvu faktoriaali abil. N\u00e4iteks 4! = 4 \u00b7 3! ja omakorda 3! = 3 \u00b7 2! ning 2! = 2 \u00b7 1!. No ja 1! = 1 v\u00f5i kui tahame 0 ka m\u00e4ngu v\u00f5tta, siis v\u00f5ime \u00f6elda ka, et 1! = 1 \u00b7 0! ja 0! = 1. \u00dcldistatult saame kaks haru:<\/p>\n<ul>\n<li>n! = 1, kui n = 0<\/li>\n<li>n! = n \u00b7 (n-1)!, kui n &gt; 0<\/li>\n<\/ul>\n<p>Programm aga on siis selline.<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">def faktoriaal(n):\r\n    if n == 0: # Rekursiooni baas\r\n        return 1\r\n    else: # Rekursiooni samm\r\n        return n * faktoriaal(n-1)\r\n\r\nprint(faktoriaal(4))\r\nprint(faktoriaal(0))\r\nprint(faktoriaal(400))<\/pre>\n<p>Rekursiivsetes programmides ongi alati mitu haru. Selleks, et protsess \u00fcldse kunagi l\u00f5ppeks, peab v\u00e4hemalt \u00fcks haru olema ilma rekursiivse v\u00e4ljakutseta. Seda haru nimetatakse rekursiooni baasiks. Rekursiivse v\u00e4ljakutsega (st sellesama funktsiooni v\u00e4ljakutsumisega) haru nimetatakse rekursiooni sammuks.<\/p>\n<p>Rekursiooniga on seotud mitmed elulised teemad, n\u00e4iteks k\u00fc\u00fclikute paljunemise modelleerimine Fibonacci arvude abil jpm. Meie l\u00e4heme aga visuaalsemate teemade juurde &#8211; hakkame vaatlema puid.<\/p>\n<h1>Korrap\u00e4rane puu<\/h1>\n<p>Olgu meie eesm\u00e4rgiks saada selline puu.<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-577\" src=\"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-content\/uploads\/sites\/18\/2020\/12\/puu100.png\" alt=\"\" width=\"301\" height=\"267\" srcset=\"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-content\/uploads\/sites\/18\/2020\/12\/puu100.png 301w, https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-content\/uploads\/sites\/18\/2020\/12\/puu100-65x58.png 65w, https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-content\/uploads\/sites\/18\/2020\/12\/puu100-225x200.png 225w\" sizes=\"auto, (max-width: 301px) 100vw, 301px\" \/><\/p>\n<p>Natuke terasemal vaatlemisel m\u00e4rkame, et puu iga haru on ise ka omakorda samasugune puu, aga v\u00e4iksem. Tolle v\u00e4iksema puu iga haru on j\u00e4llegi veel v\u00e4iksem puu. Selliseid kujundeid, kus osa on terviku sarnane, nimetatakse fraktaliteks.<\/p>\n<p>Teoreetiliselt v\u00f5ime l\u00f5pmatult joonistada puule v\u00e4iksemaid oksi, aga praktiliselt poleks sel m\u00f5tet ja piiri seadmiseks v\u00f5tame appi rekursiooni baasi. N\u00e4iteprogrammis j\u00f5uame rekursiooni baasini, kui j\u00e4rjekordse puu &#8220;t\u00fcve&#8221; pikkus on v\u00e4iksem kui 5. Sellisel juhul joonistamegi ainult t\u00fcve, milleks liigume vastava arvu samme edasi ja kohe tagasi.<\/p>\n<p>Rekursiooni sammu puhul aga joonistame t\u00fcve ja kaks haru, mis on omakorda ka puud, aga v\u00e4iksemad (korrutame teguriga 0,6). Harude joonistamise eel, vahel ja j\u00e4rel tuleb kilpkonna ka sobivalt p\u00f6\u00f6rata.<\/p>\n<p>Palun pange see programm t\u00f6\u00f6le, n\u00e4ete ka, kui kaua kilpkonnal see joonistamine aega v\u00f5tab. Selleks, et joonis kiiremini tekiks, v\u00f5ib kasutada funktsioone delay(0) ja speed(10).<\/p>\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"python\">from turtle import *\r\n\r\ndef puu(pikkus): \r\n    if pikkus &lt; 5: # Rekursiooni baas\r\n        forward(pikkus) # Ainult t\u00fcvi\r\n        back(pikkus)\r\n    else: # Rekursiooni samm\r\n        forward(pikkus) # T\u00fcvi\r\n        left(45)\r\n        puu(0.6 * pikkus) # Haru, mis on v\u00e4iksem puu\r\n        right(90)\r\n        puu(0.6 * pikkus) # Teine haru, mis on ka v\u00e4iksem puu\r\n        left(45)\r\n        back(pikkus) # T\u00fcvepidi tagasi\r\n\r\ndelay(0)\r\nspeed(10) \r\nleft(90)\r\npuu(100)\r\n\r\nexitonclick()<\/pre>\n<p>Rohkem saad lugeda rekursioonist ja kilpkonnagraafikast:<\/p>\n<p><a href=\"https:\/\/courses.cs.ut.ee\/2017\/eprogalused\/spring\/Main\/Silmaring-rekursioon\">https:\/\/courses.cs.ut.ee\/2017\/eprogalused\/spring\/Main\/Silmaring-rekursioon<\/a><\/p>\n","protected":false},"author":17,"menu_order":3,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-559","chapter","type-chapter","status-publish","hentry"],"part":55,"_links":{"self":[{"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapters\/559","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapters"}],"about":[{"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/wp\/v2\/types\/chapter"}],"author":[{"embeddable":true,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/wp\/v2\/users\/17"}],"version-history":[{"count":6,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapters\/559\/revisions"}],"predecessor-version":[{"id":579,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapters\/559\/revisions\/579"}],"part":[{"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/parts\/55"}],"metadata":[{"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapters\/559\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/wp\/v2\/media?parent=559"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapter-type?post=559"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/wp\/v2\/contributor?post=559"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/wp\/v2\/license?post=559"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}