Funktsioonist kordavalt

Oleme kasutanud erinevaid funktsioone – osa neist on olnud Pythonis valmis või oleme need importinud mõnest moodulist, teised oleme ise defineerinud. Meeldetuletuseks on programmeerimise õpiku 6. peatükk 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”). Ilma tagastusväärtuseta funktsioonide 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 erineva argumendi väärtusega).

Rekursioon sobib hästi selliste ülesannete lahendamiseks, kus tervikülesannet saab jaotada “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!. Lõpuks 1! = 1 või kui tahame ka 0 mängu võtta, siis võime öelda ka, et 1! = 1 · 0! ja 0! = 1. Üldistatult saame kaks olukorda:

• n! = 1, kui n = 0
• n! = n · (n-1)!, kui n > 0

Programselt saame selle funktsiooni kirja panna järgnevalt:

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))

Korrektses rekursiivses funktsioonis 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.

Proovi, 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)

Proovi programmi muuta ja käivita 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.

Enesekontroll (1 ülesanne)

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.