 | V OSA sisukord |  |
5.2 REKURSIOON: SISSEJUHATUS
Funktsioonist kordavalt
Oleme kasutanud erinevaid funktsioone - osa on olnud Pythonis juba valmis, aga oleme neid ka ise funktsioone defineerinud. Kursusel Programmeerimise alused oli 5. nädal funktsioonidele pühendatud.
Meenutame, et funktsioon tagastab väärtuse, mis määratakse võtmesõna return abil. Kui seda ei tehta, siis tagastatakse spetsiaalne väärtus None (eesti keeles "mitte miski"). "Väärtusetud" funktsioonid ei pruugi muidugi väärtusetud olla - nende roll on lihtsalt midagi ära teha, nt print väljastab oma argumendi(d) ekraanile, kuid ei tagasta midagi.
Olgu meil järgmine programm
def summa(a, b):
return a + b
def topelt_summa(a, b):
return 2 * summa(a, b)
print(summa(3, 4))
Näeme, et funktsioon summa on kutsutud välja funktsiooni topelt_summa definitsioonis ja ka põhiprogrammis (funktsiooni print argumendina). Veel saab funktsiooni välja kutsuda Thonny käsureaaknas (Shell):
>>> summa(5, 7) 12
Rekursiivne väljakutse
Eespool kutsuti üks funktsioon välja teise funktsiooni definitsioonis. Tegelikult saab funktsiooni välja kutsuda tema enda definitsioonis. Sellisel juhul on tegemist rekursiivse väljakutsega. Rekursioon on funktsioonide defineerimise viis, kus defineeritav funktsioon kutsub välja iseennast (kuid mitte sama argumendi väärtusega).
Rekursioon sobib hästi just selliste ülesannete lahendamiseks, kus tervikülesannet saab jaotada mingis mõttes väiksemateks samasugusteks ülesanneteks. Oluline on, et lõpuks oleks need "väiksemad" ülesanded nii väikesed, et nende lahendamine oleks väga lihtne.
Üks tuntumaid rekursiooni näiteid 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 kokku lepitud, et 0! = 1, samuti 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!. 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
Programselt saaks me seda definitsiooni kirjeldada niimoodi:
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))
Korrektsetes rekursiivsetes funktsioonides on alati mitu haru. Protsessi lõppemiseks peab vähemalt üks haru olema ilma rekursiivse väljakutseta. Seda haru nimetatakse rekursiooni baasiks. Rekursiivse väljakutsega haru nimetatakse rekursiooni sammuks. Rekursiivsete väljakutsetega võib olla ka mitu haru. Samuti võib harva olla kasulik määrata mitu erinevat rekursiooni baasi.
Mõned näited
Sarnaselt tsüklile võimaldab rekursioon kirjeldada korduvtäidetavaid protsesse.
Mänguliselt saab rekursiooni ja ka teisi programmeerimise kontruktsioone harjutada mängus Lightbot. Tasemetel 3.1 ja 3.2 saabki hakkama ainult nii, et protseduur iseennast välja kutsub.
Proovige, mida teeb järgmine programm.
def rek_fun(n):
if n > 0:
print("Põhi!")
else:
print(n)
rek_fun(n + 2)
rek_fun(-7)
Proovige programmi muuta ja käivitage uuesti. Näiteks võib n > 0 asendada mõne muu tingimusega või muuta ridade print(n) ja rek_fun(n + 2) järjekorda.
Rekursiivne funktsioon on tegelikult tavaline Pythoni funktsioon. Seega võib tal olla ka mitu argumenti.
Rekursiooni kasutatakse laialdaselt programmeerimises, arvutiteaduses ja matemaatikas, samuti keeleteaduses, muusikas, kunstis jne.
Kunstis võib välja tuua näiteks Maurits Cornelis Escheri (1898-1972) tööd.
| V OSA sisukord | |