{"id":58,"date":"2019-02-27T08:54:48","date_gmt":"2019-02-27T08:54:48","guid":{"rendered":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvaraarendus\/chapter\/lisalugemine-rekursioonist-pohjalikumalt\/"},"modified":"2020-07-22T14:04:09","modified_gmt":"2020-07-22T14:04:09","slug":"lisalugemine-rekursioonist-pohjalikumalt","status":"publish","type":"chapter","link":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/chapter\/lisalugemine-rekursioonist-pohjalikumalt\/","title":{"raw":"Lisalugemine: Rekursioonist p\u00f5hjalikumalt","rendered":"Lisalugemine: Rekursioonist p\u00f5hjalikumalt"},"content":{"raw":"

Thonny harrastab rekursiooni<\/h1>\n

Rekursiivse funktsiooni toimimisest ei pruugi olla lihtne aru saada. V\u00f5tame n\u00e4itlikustamisel appi Thonny silumisv\u00f5imalused. Tavaliselt oleme programmi k\u00e4ivitanud ja see on oma t\u00f6\u00f6 praktiliselt silmapilkselt \u00e4ra teinud. N\u00fc\u00fcd aga kasutame v\u00f5imalust Run --> Debug current script<\/code>, mille abil saame programmi t\u00f6\u00f6d sammukaupa j\u00e4lgida. J\u00e4rgmise sammu tegemiseks on mitu v\u00f5imalust. Esialgu on sobiv kasutada varianti Step into (F7)<\/code>.<\/p>\n

Vaatame eelmises peat\u00fckis toodud faktoriaali arvutamise programmi.<\/p>\n\n

\n
\n
def faktoriaal(n):\n    if n == 0:\n        return 1\n    else:\n        return n * faktoriaal(n-1)\n\nprint(faktoriaal(4))<\/pre>\n<\/div>\n<\/div>\n
Kui paneksime programmi tavap\u00e4raselt t\u00f6\u00f6le (Run --> Run current script (F5)<\/code>), siis saaksime vastuse 24, kuid vahepealse t\u00f6\u00f6 kohta infot mitte. Run<\/code> --> Debug current script<\/code> abil aga v\u00e4rvub osa koodist kollaseks, mis n\u00e4itab, kuhu programmi t\u00e4itmine on j\u00f5udnud. Esimese sammuna v\u00e4rvub funktsiooni kirjeldus - see funktsioon \"\u00f5pitakse\" selgeks.<\/p>\n\n
<\/div>\n
\"\"<\/div>\n
Kui sammhaaval edasi minna (Step into (F7)<\/code>), siis j\u00f5uame varsti seisuni, kus faktoriaal(4)<\/code> arvutamiseks ilmub uus aken:<\/p>\n\n
<\/div>\n
\"\"<\/div>\n
See demonstreerib, et funktsiooni rakendamine on k\u00fcllaltki iseseisev. Kui n\u00fc\u00fcd edasi \"sammuda\", siis varsti tuleb arvutada faktoriaal(3)<\/code>, isegi enne, kui faktoriaal(4)<\/code> l\u00f5plikult leitud saab. Sellega ilmub uus aken:<\/p>\n\n
<\/div>\n
\"\"<\/div>\n
Edasi sammudes ilmub j\u00e4rjest uusi aknaid, kuni l\u00f5puks j\u00f5uame faktoriaal(0)<\/code>, mis ometigi konkreetse tulemuse (1) tagastab.<\/p>\n\n
<\/div>\n
\"\"<\/div>\n
N\u00fc\u00fcd hakkavad aknad j\u00e4rjest sulguma, sest funktsioonid saavad j\u00e4rjest oma vajalikud andmed k\u00e4tte ning suudavad nende abil oma t\u00f6\u00f6 l\u00f5petada. L\u00f5puks j\u00f5uab ekraanile tulemus 24.<\/p>\n
Sarnaselt saab l\u00e4bi m\u00e4ngida ka teised programmid, mille t\u00f6\u00f6st h\u00e4sti aru ei saa.<\/p>\n\n
Rekursiivne v\u00e4ljakutse<\/h1>\n
Rekursiivsetes funktsioonides v\u00f5ib rekursiivne v\u00e4ljakutse paikneda erinevates kohtades. N\u00e4iteks j\u00e4rgmises programmis on see vastava haru viimane tegevus:<\/p>\n\n
\n
\n
def print_alla(n):\n    if n <= 0:\n        print(\"Stop!\")\n    else:\n        print(n)\n        print_alla(n - 1)<\/pre>\n<\/div>\n<\/div>\n
P\u00fc\u00fca enne programmi k\u00e4ivitamist ennustada, mis ilmub ekraanile j\u00e4rgmistel juhtudel:<\/p>\n\n
\n
\n
print_alla(4)\nprint_alla(0)\nprint_alla(-4)<\/pre>\n<\/div>\n<\/div>\n
N\u00e4eme, et lause print(n)<\/code><\/code> on enne rekursiivset v\u00e4ljakutset ja ekraanile v\u00e4ljastatakse n<\/code> v\u00e4\u00e4rtus, mis on just selles konkreetses print_alla<\/code><\/code> v\u00e4ljakutses. Kuna iga j\u00e4rgmine v\u00e4ljakutse on \u00fche v\u00f5rra v\u00e4iksema argumendiga (n - 1<\/code>), siis ilmuvad ka arvud ekraanile kahanevas j\u00e4rjekorras.<\/p>\n
Muudame n\u00fc\u00fcd print(n)<\/code> ja print_alla(n - 1)<\/code><\/code> j\u00e4rjekorda:<\/p>\n\n
\n
def print_kuhu(n):\n    if n <= 0:\n        print(\"Stop!\")\n    else:\n        print_kuhu(n - 1)\n        print(n)<\/pre>\n<\/div>\n
P\u00fc\u00fca enne erinevate argumentidega k\u00e4ivitamist ennustada, mis ekraanile ilmub:<\/p>\n\n
\n
print_kuhu(4)\nprint_kuhu(0)\nprint_kuhu(-4)<\/pre>\n<\/div>\n
Paneme t\u00e4hele, et n\u00fc\u00fcd on print(n)<\/code><\/code> p\u00e4rast rekursiivset v\u00e4ljakutset. Seega enne, kui midagi ekraanile v\u00e4ljastatakse, \"avanevad\" k\u00f5ik print_kuhu<\/code> v\u00e4ljakutsed. L\u00f5puks ilmub print_kuhu(0)<\/code><\/code> toimel ekraanile Stop!<\/code>. Seej\u00e4rel hakkavad v\u00e4ljakutsed j\u00e4rjest \"sulguma\". Vahetult oma t\u00f6\u00f6 l\u00f5pus v\u00e4ljastab v\u00e4ljakutse ekraanile n<\/code> v\u00e4\u00e4rtuse, mis selles v\u00e4ljakutses hetkel on. Oluline on m\u00e4rgata, et igas v\u00e4ljakutses on n<\/code> v\u00e4\u00e4rtus teiste omadest s\u00f5ltumatu.<\/p>\n
Selles programmis ilmusid arvud ekraanile kasvavas j\u00e4rjekorras. V\u00f5ib \u00f6elda, et enne rekursiivset v\u00e4ljakutset tehtavad tegevused toimuvad \"kahanevalt\". P\u00e4rast rekursiivset v\u00e4ljakutset tehtavad tegevused toimuvad \"kasvavalt\":<\/p>\n\n
\n
\n
def print_ules(n):\n    if n <= 0:\n        print(\"Stop!\")\n    else:\n        print_ules(n-1)\n        print(n)<\/pre>\n<\/div>\n<\/div>\n
Mis juhtub siis, kui v\u00e4ljastamise k\u00e4sk on nii enne kui ka p\u00e4rast rekursiivset v\u00e4ljakutset?<\/p>\n\n
def print_alla_ules(n):\n    if n <= 0:\n        print(\"Stop!\")\n    else:\n        print(n)\n        print_alla_ules(n - 1)\n        print(n)<\/pre>\n
Rekursioon s\u00f5nede ja j\u00e4rjenditega<\/h1>\n
Senised rekursioonide n\u00e4ited on p\u00f5hiliselt olnud seotud arvudega. N\u00fc\u00fcd vaatleme ka teisi andmet\u00fc\u00fcpe. N\u00e4iteks saab rekursiivselt kontrollida, kas s\u00f5ne on palindroom - algusest v\u00f5i l\u00f5pust loetult sama. Kontrollimisel kasutatakse asjaolu, et s\u00f5ne on palindroom juhul, kui tema esimene ja viimane s\u00fcmbol on sama ning nende vahele j\u00e4\u00e4v alams\u00f5ne on samuti palindroom. Nii saamegi rekursiivse funktsiooni, kus baasiks on \u00fches\u00fcmboliline v\u00f5i t\u00fchi s\u00f5ne, mida saame lugeda palindroomiks. Alams\u00f5ne leidmiseks on kasutatud viilutamist: s[1:-1]<\/code><\/code> puhul on alams\u00f5ne alguse indeks (kaasa arvatud) 1 ja l\u00f5pu indeks (v\u00e4lja arvatud) -1.<\/p>\n\n
\n
\n
def on_palindroom(s):\n    if len(s) <= 1:\n        return True\n    else:\n        return s[0] == s[-1] and on_palindroom(s[1:-1])<\/pre>\n<\/div>\n<\/div>\n
J\u00e4rjendi pikkuse leidmiseks on olemas spetsiaalne funktsioon len<\/code><\/code>.<\/p>\n
Kirjutame n\u00fc\u00fcd ise funktsiooni, millega j\u00e4rjendi pikkust leida. Vaatleme kahte varianti - \u00fcks ts\u00fckliga ja teine rekursiooniga.<\/p>\n
Ts\u00fckliga liidetakse loendurile igat j\u00e4rjendi elementi vaadeldes 1:<\/p>\n\n
\n
\n
def pikkus(loend):\n    i = 0\n    for c in loend:\n        i += 1\n    return i<\/pre>\n<\/div>\n<\/div>\n
Rekursiooniga kasutame baasina asjaolu, et t\u00fchja listi pikkus on 0. Muul juhul on listi pikkus 1 pluss sellise alamlisti pikkus, kust on v\u00e4lja j\u00e4etud esimene element.<\/p>\n\n
\n
\n
def rpikkus(loend):\n    if loend == []:\n        return 0\n    else:\n        return 1 + rpikkus(loend[1:])<\/pre>\n<\/div>\n<\/div>\n
L\u00f5puks tuleme arvude juurde tagasi ja vaatleme astendamise funktsiooni. Baasi saame teadmisest, et iga arv astmes 0 on 1. Igal rekursiooni sammul arvutatakse arvu \u00fche v\u00f5rra v\u00e4iksem aste.<\/p>\n\n
\n
\n
def aste(n, m):\n    if m == 0:\n        return 1\n    else:\n        return n * aste(n, m-1)<\/pre>\n<\/div>\n<\/div>","rendered":"
Thonny harrastab rekursiooni<\/h1>\n
Rekursiivse funktsiooni toimimisest ei pruugi olla lihtne aru saada. V\u00f5tame n\u00e4itlikustamisel appi Thonny silumisv\u00f5imalused. Tavaliselt oleme programmi k\u00e4ivitanud ja see on oma t\u00f6\u00f6 praktiliselt silmapilkselt \u00e4ra teinud. N\u00fc\u00fcd aga kasutame v\u00f5imalust Run --> Debug current script<\/code>, mille abil saame programmi t\u00f6\u00f6d sammukaupa j\u00e4lgida. J\u00e4rgmise sammu tegemiseks on mitu v\u00f5imalust. Esialgu on sobiv kasutada varianti Step into (F7)<\/code>.<\/p>\n
Vaatame eelmises peat\u00fckis toodud faktoriaali arvutamise programmi.<\/p>\n
\n
\n
def faktoriaal(n):\n    if n == 0:\n        return 1\n    else:\n        return n * faktoriaal(n-1)\n\nprint(faktoriaal(4))<\/pre>\n<\/div>\n<\/div>\n
Kui paneksime programmi tavap\u00e4raselt t\u00f6\u00f6le (Run --> Run current script (F5)<\/code>), siis saaksime vastuse 24, kuid vahepealse t\u00f6\u00f6 kohta infot mitte. Run<\/code> –> Debug current script<\/code> abil aga v\u00e4rvub osa koodist kollaseks, mis n\u00e4itab, kuhu programmi t\u00e4itmine on j\u00f5udnud. Esimese sammuna v\u00e4rvub funktsiooni kirjeldus – see funktsioon “\u00f5pitakse” selgeks.<\/p>\n
<\/div>\n
\"\"<\/div>\n
Kui sammhaaval edasi minna (Step into (F7)<\/code>), siis j\u00f5uame varsti seisuni, kus faktoriaal(4)<\/code> arvutamiseks ilmub uus aken:<\/p>\n
<\/div>\n
\"\"<\/div>\n
See demonstreerib, et funktsiooni rakendamine on k\u00fcllaltki iseseisev. Kui n\u00fc\u00fcd edasi “sammuda”, siis varsti tuleb arvutada faktoriaal(3)<\/code>, isegi enne, kui faktoriaal(4)<\/code> l\u00f5plikult leitud saab. Sellega ilmub uus aken:<\/p>\n
<\/div>\n
\"\"<\/div>\n
Edasi sammudes ilmub j\u00e4rjest uusi aknaid, kuni l\u00f5puks j\u00f5uame faktoriaal(0)<\/code>, mis ometigi konkreetse tulemuse (1) tagastab.<\/p>\n
<\/div>\n
\"\"<\/div>\n
N\u00fc\u00fcd hakkavad aknad j\u00e4rjest sulguma, sest funktsioonid saavad j\u00e4rjest oma vajalikud andmed k\u00e4tte ning suudavad nende abil oma t\u00f6\u00f6 l\u00f5petada. L\u00f5puks j\u00f5uab ekraanile tulemus 24.<\/p>\n
Sarnaselt saab l\u00e4bi m\u00e4ngida ka teised programmid, mille t\u00f6\u00f6st h\u00e4sti aru ei saa.<\/p>\n
Rekursiivne v\u00e4ljakutse<\/h1>\n
Rekursiivsetes funktsioonides v\u00f5ib rekursiivne v\u00e4ljakutse paikneda erinevates kohtades. N\u00e4iteks j\u00e4rgmises programmis on see vastava haru viimane tegevus:<\/p>\n
\n
\n
def print_alla(n):\n    if n <= 0:\n        print(\"Stop!\")\n    else:\n        print(n)\n        print_alla(n - 1)<\/pre>\n<\/div>\n<\/div>\n
P\u00fc\u00fca enne programmi k\u00e4ivitamist ennustada, mis ilmub ekraanile j\u00e4rgmistel juhtudel:<\/p>\n
\n
\n
print_alla(4)\nprint_alla(0)\nprint_alla(-4)<\/pre>\n<\/div>\n<\/div>\n
N\u00e4eme, et lause print(n)<\/code><\/code> on enne rekursiivset v\u00e4ljakutset ja ekraanile v\u00e4ljastatakse n<\/code> v\u00e4\u00e4rtus, mis on just selles konkreetses print_alla<\/code><\/code> v\u00e4ljakutses. Kuna iga j\u00e4rgmine v\u00e4ljakutse on \u00fche v\u00f5rra v\u00e4iksema argumendiga (n - 1<\/code>), siis ilmuvad ka arvud ekraanile kahanevas j\u00e4rjekorras.<\/p>\n
Muudame n\u00fc\u00fcd print(n)<\/code> ja print_alla(n - 1)<\/code><\/code> j\u00e4rjekorda:<\/p>\n
\n
def print_kuhu(n):\n    if n <= 0:\n        print(\"Stop!\")\n    else:\n        print_kuhu(n - 1)\n        print(n)<\/pre>\n<\/div>\n
P\u00fc\u00fca enne erinevate argumentidega k\u00e4ivitamist ennustada, mis ekraanile ilmub:<\/p>\n
\n
print_kuhu(4)\nprint_kuhu(0)\nprint_kuhu(-4)<\/pre>\n<\/div>\n
Paneme t\u00e4hele, et n\u00fc\u00fcd on print(n)<\/code><\/code> p\u00e4rast rekursiivset v\u00e4ljakutset. Seega enne, kui midagi ekraanile v\u00e4ljastatakse, “avanevad” k\u00f5ik print_kuhu<\/code> v\u00e4ljakutsed. L\u00f5puks ilmub print_kuhu(0)<\/code><\/code> toimel ekraanile Stop!<\/code>. Seej\u00e4rel hakkavad v\u00e4ljakutsed j\u00e4rjest “sulguma”. Vahetult oma t\u00f6\u00f6 l\u00f5pus v\u00e4ljastab v\u00e4ljakutse ekraanile n<\/code> v\u00e4\u00e4rtuse, mis selles v\u00e4ljakutses hetkel on. Oluline on m\u00e4rgata, et igas v\u00e4ljakutses on n<\/code> v\u00e4\u00e4rtus teiste omadest s\u00f5ltumatu.<\/p>\n
Selles programmis ilmusid arvud ekraanile kasvavas j\u00e4rjekorras. V\u00f5ib \u00f6elda, et enne rekursiivset v\u00e4ljakutset tehtavad tegevused toimuvad “kahanevalt”. P\u00e4rast rekursiivset v\u00e4ljakutset tehtavad tegevused toimuvad “kasvavalt”:<\/p>\n
\n
\n
def print_ules(n):\n    if n <= 0:\n        print(\"Stop!\")\n    else:\n        print_ules(n-1)\n        print(n)<\/pre>\n<\/div>\n<\/div>\n
Mis juhtub siis, kui v\u00e4ljastamise k\u00e4sk on nii enne kui ka p\u00e4rast rekursiivset v\u00e4ljakutset?<\/p>\n
def print_alla_ules(n):\n    if n <= 0:\n        print(\"Stop!\")\n    else:\n        print(n)\n        print_alla_ules(n - 1)\n        print(n)<\/pre>\n
Rekursioon s\u00f5nede ja j\u00e4rjenditega<\/h1>\n
Senised rekursioonide n\u00e4ited on p\u00f5hiliselt olnud seotud arvudega. N\u00fc\u00fcd vaatleme ka teisi andmet\u00fc\u00fcpe. N\u00e4iteks saab rekursiivselt kontrollida, kas s\u00f5ne on palindroom – algusest v\u00f5i l\u00f5pust loetult sama. Kontrollimisel kasutatakse asjaolu, et s\u00f5ne on palindroom juhul, kui tema esimene ja viimane s\u00fcmbol on sama ning nende vahele j\u00e4\u00e4v alams\u00f5ne on samuti palindroom. Nii saamegi rekursiivse funktsiooni, kus baasiks on \u00fches\u00fcmboliline v\u00f5i t\u00fchi s\u00f5ne, mida saame lugeda palindroomiks. Alams\u00f5ne leidmiseks on kasutatud viilutamist: s[1:-1]<\/code><\/code> puhul on alams\u00f5ne alguse indeks (kaasa arvatud) 1 ja l\u00f5pu indeks (v\u00e4lja arvatud) -1.<\/p>\n
\n
\n
def on_palindroom(s):\n    if len(s) <= 1:\n        return True\n    else:\n        return s[0] == s[-1] and on_palindroom(s[1:-1])<\/pre>\n<\/div>\n<\/div>\n
J\u00e4rjendi pikkuse leidmiseks on olemas spetsiaalne funktsioon len<\/code><\/code>.<\/p>\n
Kirjutame n\u00fc\u00fcd ise funktsiooni, millega j\u00e4rjendi pikkust leida. Vaatleme kahte varianti – \u00fcks ts\u00fckliga ja teine rekursiooniga.<\/p>\n
Ts\u00fckliga liidetakse loendurile igat j\u00e4rjendi elementi vaadeldes 1:<\/p>\n
\n
\n
def pikkus(loend):\n    i = 0\n    for c in loend:\n        i += 1\n    return i<\/pre>\n<\/div>\n<\/div>\n
Rekursiooniga kasutame baasina asjaolu, et t\u00fchja listi pikkus on 0. Muul juhul on listi pikkus 1 pluss sellise alamlisti pikkus, kust on v\u00e4lja j\u00e4etud esimene element.<\/p>\n
\n
\n
def rpikkus(loend):\n    if loend == []:\n        return 0\n    else:\n        return 1 + rpikkus(loend[1:])<\/pre>\n<\/div>\n<\/div>\n
L\u00f5puks tuleme arvude juurde tagasi ja vaatleme astendamise funktsiooni. Baasi saame teadmisest, et iga arv astmes 0 on 1. Igal rekursiooni sammul arvutatakse arvu \u00fche v\u00f5rra v\u00e4iksem aste.<\/p>\n
\n
\n
def aste(n, m):\n    if m == 0:\n        return 1\n    else:\n        return n * aste(n, m-1)<\/pre>\n<\/div>\n<\/div>\n","protected":false},"author":3,"menu_order":2,"template":"","meta":{"pb_show_title":"on","pb_short_title":"","pb_subtitle":"","pb_authors":[],"pb_section_license":""},"chapter-type":[],"contributor":[],"license":[],"class_list":["post-58","chapter","type-chapter","status-publish","hentry"],"part":55,"_links":{"self":[{"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapters\/58","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\/3"}],"version-history":[{"count":1,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapters\/58\/revisions"}],"predecessor-version":[{"id":59,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapters\/58\/revisions\/59"}],"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\/58\/metadata\/"}],"wp:attachment":[{"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/wp\/v2\/media?parent=58"}],"wp:term":[{"taxonomy":"chapter-type","embeddable":true,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/pressbooks\/v2\/chapter-type?post=58"},{"taxonomy":"contributor","embeddable":true,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/wp\/v2\/contributor?post=58"},{"taxonomy":"license","embeddable":true,"href":"https:\/\/web.htk.tlu.ee\/digitaru\/tarkvara2\/wp-json\/wp\/v2\/license?post=58"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}