| < eelmine | 12. nädala sisukord | järgmine > |
12.3 REKURSIOONIST DETAILSEMALT
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 programmitööd sammukaupa jälgida. Järgmise sammu tegemiseks on mitu võimalust. Esialgu on sobiv kasutada varianti Step into (F7).
Vaatame sedasama faktoriaali arvutamise programmi.
def faktoriaal(n):
if n == 0:
return 1
else:
return n * faktoriaal(n-1)
print(faktoriaal(4))
Kui paneksime kohe tööle Run --> Run current script (F5) saaksime vastuse 24 ja 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. Näiteks esimese sammuna värvub funktsiooni kirjeldus - see funktsioon "õpitakse" selgeks.
Kui nüüd sammhaaval edasi minna (Step into (F7)), siis jõuame varsti seisuni, kus faktoriaal(4) arvutamiseks ilmub uus aken.
See demonstreeribki, et funktsiooni rakendamine on küllaltki iseseisev. Kui nüüd edasi "sammuda", siis varsti tuleb arvutada faktoriaal(3). Seda veel enne, kui faktoriaal(4) lõplikult leitud saab. Ja nii 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 vajalikud andmed arvutamiseks on järjest olemas. Lõpuks tuleb ka oodatud 24 ekraanile.
Soovitav on mängida selliselt läbi ka teised programmid, millest võib-olla muidu hästi aru ei saa.
Rekursiivne väljakutse
Rekursiivsetes funktsioonides võib rekursiivne väljakutse olla erinevates kohtades. Näiteks järgmises programmis on see viimase tegevusena vastavas harus.
def print_alla(n):
if n <= 0:
print("Stop!")
else:
print(n)
print_alla(n - 1)
Enne programmi käivitamist püüdke 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üüdke enne 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 siis print_kuhu(0) toimel ilmub ekraanile Stop!. Nüüd hakkavad väljakutsed "sulguma", aga vahetult oma töö lõpus väljastatakse ekraanile n väärtus, mis selles väljakutses hetkel on. Oluline on, et igas väljakutses on n väärtus sõltumatu.
Niisiis ekraanile tekivad arvud 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 aga juhtub siis, kui väljastamise käsk on nii enne kui 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 rekursiooninäited on põhiliselt olnud arvudega seotud. 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, kui tema esimene ja viimane sümbol on sama ning nende vahelejääv alamsõne on 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 (kaasaarvatud) 1 ja lõpu indeks (väljaarvatud) -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. Siin harjutame ise sarnaste funktsioonide defineerimist, et teiste samalaadsete ülesannetega ka paremini toime tulla. Vaatleme kahte varianti - üks tsükliga ja teine rekursiooniga.
Tsüklis liidetakse loendurile igat elementi vaadeldes 1.
def pikkus(loend):
i = 0
for c in loend:
i += 1
return i
Rekursiooni korral kasutatame baasina asjaolu, et tühja listi pikkus on 0. Muidu aga on listi pikkus 1, millele on liidetud 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 ikkagi 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)
| < eelmine | 12. nädala sisukord | järgmine > |