| < eelmine | 12. nädala sisukord | järgmine > |
12.7 TSÜKKEL JA REKURSIOON
Eelmisel nädalal tutvusime rekursiooniga. Rekursiivne funktsioon kutsub välja iseenda ja see võib toimuda korduvalt. Varem olime korduva tegevuse puhul kasutanud tsükleid. Selles peatükis püüamegi tsüklit ja rekursiooni kõrvutada - nii mõnegi ülesande lahendame mõlemal moel.
Millal lõpetada?
Korduva tegevuse puhul on oluline piiri pidada - millal ikkagi lõpetada? Tsükli puhul on jätkamise või lõpetamise mõttes tähtis tsükli jätkamistingimus. Tsüklit korratakse seni kui jätkamistingimus veel kehtib. While-tsükli puhul on see tingimus selgelt nähtav, näiteks
while i < len(järjend):
For-tsükli puhul antakse ette teatud kogum elemente, millest iga puhul tuleb tsükli sisu täita. Tingimus siis kontrollib, kas on veel mõni element, mis on vaatamata, näiteks
for i in range(len(järjend))
või
for element in järjend:
Rekursiooni korral kontrollitakse, kas järjekordse väljakutsega on juba jõutud rekursiooni baasini - juhuni, millel on mitterekursiivne lahendus.
Tuletame meelde faktoriaali arvutamise funktsiooni, kus baas on juhul n = 0.
def faktoriaal(n):
if n == 0: # Rekursiooni baas
return 1
else: # Rekursiooni samm
return n * faktoriaal(n - 1)
Tingimust sobivalt vastupidiseks muutes saab harud ka ära vahetada.
def faktoriaal2(n):
if n != 0:
return n * faktoriaal2(n - 1)
else:
return 1
Antud juhtudel võib else-osa sisu lihtsalt tingimuslause järele kirjutada, sest if-osa return nagunii ei luba tingimuslausest edasi.
def faktoriaal(n):
if n == 0: # Rekursiooni baas
return 1
return n * faktoriaal(n - 1) # Rekursiooni samm
def faktoriaal2(n):
if n != 0:
return n * faktoriaal2(n - 1)
return 1
Akumulaator
Faktoriaali saab muidugi arvutada ka tsükli abil. Seda saab teha mitmel moel, alustame for-tsükliga ja nii, et arvutame kasvavate teguritega 1 · 2 · 3 … n
def faktoriaal_tsükliga_for_üles(n):
aku = 1
for i in range(1, n + 1): #1, 2 … n
aku *= i
return aku
Edasi jõuab samale tulemusele hoopis while-tsükkel kahanevate teguritega n · (n - 1) · … 1
def faktoriaal_tsükliga_while_alla(n):
aku = 1
while n != 0:
aku *= n
n -= 1
return aku
Mõlemal juhul kasutatakse muutujat aku, millesse lõpptulemus järjest kogutakse. Vahel nimetatakse sellist muutujat akumulaatoriks. Põhimõtteliselt saab akumulaatorit kasutada ka rekursiooni puhul. Nimelt saame korraldada, et vajalik väärtus antakse edasi argumendi ja tagastamise kaudu. Selleks on kasutusel teine argument, mille nimeks panemegi aku.
def faktoriaal_aku(n, aku):
if n != 0:
return faktoriaal_aku(n - 1, aku * n)
return aku
Kui nüüd see funktsioon välja kutsuda, siis tuleb aku esimene väärtus väljakutses ise määrata.
print(faktoriaal_aku(4, 1))
Kasutades Thonny võimalusi programmi töö läbimängimiseks (Debug current script) näeme, et rekursioonile kohaselt kutsutakse funktsiooni järjest välja ja teine argument tõesti “kogub” vajaliku tulemuse endasse.
Kui teraselt pilti jälgida, siis pole seal päris täpselt see funktsioon, mis ülaltoodud. Nimelt on siin hea kasutada Pythoni võimalust anda funktsiooni argumendile vaikeväärtus.
def faktoriaal_aku(n, aku = 1):
Vaikeväärtust kasutatakse siis, kui sellele argumendile väljakutses väärtust ei anta. Nii vabaneme vajadusest akumulaatori esialgne väärtus ette anda.
print(faktoriaal_aku(4))
Sabarekursioon
Kui nüüd jõutakse baasini, siis hakatakse seda leitud tulemust, antud juhul 24, järjest tagastama. Oluline on, et midagi rohkemat tagasiteel ei juhtugi - return tagastabki igal tasemel selle, mida ta sügavamalt saab
return faktoriaal_aku(n - 1, aku * n)
Mäletatavasti meie algses rekursiivses faktoriaali leidmise funktsioonis just oluline arvutamine toimuski.
return n * faktoriaal(n - 1)
Kui kõik tegevused toimuvad enne rekursiivset väljakutset, siis nimetatakse rekursiooni sabarekursiooniks (tail recursion). Funktsiooni nimetatakse sabarekursiivseks, kui pärast tagastusväärtuse saamist tehakse ainult väärtuse tagastamine.
Sabarekursiooni on suhteliselt lihtne teisendada tavaliseks tsükliks (ja ka vastupidi).
Funktsioon
def faktoriaal_aku(n, aku = 1):
if n != 0:
return faktoriaal_aku(n - 1, aku * n)
return aku
on niisiis sabarekursiivne.
Kuidas aga siis on lood tsükliks teisendamisega?
Võtame võrdluseks while-tsüklit kasutava funktsiooni.
def faktoriaal_tsükliga_while_alla(n):
aku = 1
while n != 0:
aku *= n
n -= 1
return aku
Näeme, et tõesti ongi kõik praktiliselt samal kujul olemas nii ühes tsükli kui rekursiooni variandis.
Järjendi summa näide
Vaatleme nüüd järjendi elementide summa arvutamise ülesannet. Loomulikult on Pythonis juba olemas täpselt selleks ettenähtud funktsioon sum, aga “unustame” selle hetkeks ära. Summat saame nii tsükliliselt kui rekursiivselt leida väga mitmel moel. Esialgu toome mõned tsükliga variandid, näiteks for-tsükliga üle elementide
def summa_tsükkel_element(järjend):
tulemus = 0
for element in järjend:
tulemus += element
return tulemus
ning for-tsükliga üle indeksite
def summa_tsükkel_indeks(järjend):
tulemus = 0
for i in range(len(järjend)):
tulemus += järjend[i]
return tulemus
Nüüd aga kirjutame selle viimase ümber while-tsükliga variandiks.
def summa_tsükkel_i_while(järjend):
tulemus = 0
i = 0
while i < len(järjend):
tulemus += järjend[i]
i += 1
return tulemus
Seda aga saab suhteliselt lihtsalt teisendada sabarekursiivseks.
def summa_sabarekursiivne(järjend, i = 0, tulemus = 0):
if i < len(järjend):
return summa_sabarekursiivne(järjend, i + 1, järjend[i] + tulemus)
return tulemus
Muutujat i oli meil vaja, et teada, mis kohas me järjendis parajasti oleme. Ilma selleta saame siis hakkama, kui pärast järjendi alguselemendi (järjend[0]) liitmise järel edasi juba sellise järjendiga tegutseme, kus alguselement on välja jäetud (järjend[1:])
def summa_while_lõige(järjend):
tulemus = 0
while len(järjend) > 0:
tulemus += järjend[0]
järjend = järjend[1:]
return tulemus
def summa_sabarekursioon_lõige(järjend, tulemus = 0):
if len(järjend) > 0:
return summa_sabarekursioon_lõige(järjend[1:], järjend[0] + tulemus)
return tulemus
| < eelmine | 12. nädala sisukord | järgmine > |