33 Silmaring: Rekursioon

Reeglina rekursiooni algkursusel ei käsitleta, siingi on see silmaringi materjalide hulgas. Kuna tegemist on niivõrd kena ja põneva teemaga, siis ei sobi jätta huvilisi nendest teadmistest ilma. Ei maksa nukrutseda, kui mingid kohad selles osas liiga keerulised tunduvad. Jäta need julgesti vahele!

Rekursioon

Tegelikult saab funktsiooni välja kutsuda ka selle sama funktsiooni sisemuses. Esialgu võib see tunduda võõras – kuidas siis saab nii olla, et me justkui õpetaksime mingit uut asja tegema sellesama asja abil, mida praegu õpetame?! Tegemist on rekursiooniga – arvutiteaduse ühe alusmõistega.

Rekursioon sobib eriti hästi selliste ülesannete lahendamiseks, kus tervikülesanne koosneb mingis mõttes sarnastest, kuid väiksematest alamülesannetest. Kui põhiülesannet piisavalt kaua alamülesanneteks jagades muutuvad alamülesanded nii väikeseks, et väiksemaks minna enam ei saa või ei taha, siis võiks püüda seda protsessi rekursiivselt esitada.

Faktoriaal

Klassikaline rekursiooni näide 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. Muidugi ka 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!. Üldistatult saame kaks haru:

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

Faktoriaali leidmise programm oleks selline:

Näiteprogramm. Faktoriaal

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

Rekursiivsetes programmides on alati mitu haru. Selleks, et protsess üldse kunagi lõppeks, peab vähemalt üks haru olema ilma rekursiivse väljakutseta. Seda haru nimetatakse rekursiooni baasiks. Rekursiivse väljakutsega (st sellesama funktsiooni väljakutsumisega) haru nimetatakse rekursiooni sammuks.

Rekursiooniga on seotud mitmed elulised teemad, näiteks küülikute paljunemise modelleerimine Fibonacci arvude abil jpm. Meie läheme aga visuaalsemate teemade juurde – hakkame vaatlema puid.

Korrapärane puu

Olgu meie eesmärgiks saada selline puu:

Terasel vaatlemisel märkame, et puu iga haru on ise omakorda samasugune puu, aga väiksem. Tolle väiksema puu iga haru on jällegi veel väiksem puu. Selliseid kujundeid, kus osa on terviku sarnane, nimetatakse fraktaliteks.

Teoreetiliselt võime lõpmatult joonistada puule väiksemaid oksi, aga praktiliselt poleks sel mõtet ja piiri seadmiseks võtame appi rekursiooni baasi. Näiteprogrammis jõuame rekursiooni baasini, kui järjekordse puu “tüve” pikkus on väiksem kui 5. Sellisel juhul joonistamegi ainult tüve, milleks liigume vastava arvu samme edasi ja seejärel kohe tagasi.

Rekursiooni sammu puhul aga joonistame tüve ja kaks haru, mis on omakorda ka puud, aga väiksemad (korrutame teguriga 0,6). Harude joonistamise eel, vahel ja järel tuleb kilpkonna ka sobivalt pöörata.

Käivita see programm. Näed ka, kui kaua kilpkonnal see joonistamine aega võtab. Selleks, et joonis kiiremini tekiks, võib kasutada funktsioone delay(0) ja speed(10).

Näiteprogramm. Rekursiivne puu

from turtle import *
 
def puu(pikkus):          
    if pikkus < 5:         # Rekursiooni baas
        forward(pikkus)    # Ainult tüvi
        back(pikkus)
    else:                  # Rekursiooni samm
        forward(pikkus)    # Tüvi
        left(45)
        puu(0.6 * pikkus)  # Haru, mis on väiksem puu
        right(90)
        puu(0.6 * pikkus)  # Teine haru, mis on ka väiksem puu
        left(45)
        back(pikkus)       # Tüvepidi tagasi
 
delay(0)
speed(10)       
left(90)
puu(100)
 
exitonclick()

Loobume sümmeetriast

Eelmine puu oli meil väga korrapärane ja sümmeetriline. Loobume sellest, et puu peaks sümmeetriline olema. Muudame programmi nii, et enam ei pöörataks 45 kraadi vasakule, 90 paremale ja 45 vasakule. Olgu näiteks vasakule pöörded 40 ja 50 kraadi.

Näiteprogramm. Asümmeetriline puu

from turtle import *
 
def puu(pikkus):
    if pikkus < 5:
        forward(pikkus)    
        back(pikkus)
    else:
        forward(pikkus)
        left(40)           # Pöörame nüüd hoopis 40 kraadi
        puu(0.6 * pikkus)
        right(90)
        puu(0.6 * pikkus)
        left(50)           # ja siin 50 kraadi
        back(pikkus)
 
delay(0)
speed(10)
left(90)
puu(100)
 
exitonclick()

Näeme, et puu on tõesti natuke ebasümmeetriline:

Päris puudel muidugi kõik harud ühepikkused pole. Proovime teha nii, et ühes harus oleks tegur endiselt 0,6 aga teisel hoopis 0,5.

Näiteprogramm. Erineva harupikkustega puu

from turtle import * 
 
def puu(pikkus):
    if pikkus < 5:
        forward(pikkus)
        back(pikkus)
    else:
        forward(pikkus)
        left(40)          
        puu(0.6 * pikkus)  # Tegur endiselt 0.6
        right(90)
        puu(0.5 * pikkus)  # Tegur on nüüd 0.5
        left(50)
        back(pikkus)
 
delay(0)
speed(10)
left(90)
puu(100)
 
exitonclick()

Saame midagi sellist:

Juhuslik puu

Väga põnevaid võimalusi annab juhuslike arvude kasutamine. Nii annab sama programm igal käivitamisel erinevaid tulemusi. Muudame programmi nii, et iga haru joonistamisel määratakse tegur, millega pikkus korrutatakse, juhuslikult. Funktsiooniga randint(6,7) saame juhusliku arvu 6 või 7. Selleks, et saada 0,6 või 0,7 jagame arvuga 10.

Näiteprogramm. Juhusliku harupikkusega puu

from turtle import * 
from random import *      # Juhuslike arvude moodul
 
def puu(pikkus):
    if pikkus < 5:
        forward(pikkus)
        back(pikkus)
    else:
        forward(pikkus)
        left(40)
        puu(randint(6,7) / 10 * pikkus)   # Tegur on 0.6 või 0.7
        right(90)
        puu(randint(6,7) / 10 * pikkus)   # Tegur on 0.6 või 0.7
        left(50)
        back(pikkus)
 
delay(0)
speed(10)
left(90)
puu(100)

exitonclick()

Tulemus võib olla midagi sarnast:

Teeme nüüd programmi, mis paneb mitu juhusliku suurusega puud kõrvuti.

Näiteprogramm. Juhuslike puude mets

from turtle import * 
from random import *
 
def puu(pikkus):
    if pikkus < 5:
        forward(pikkus)
        back(pikkus)
    else:
        forward(pikkus)
        left(45)
        puu(randint(6,7) / 10 * pikkus)
        right(90)
        puu(randint(6,7) / 10 * pikkus)
        left(45)
        back(pikkus)
 
def mets(puudearv):
    i = 0
    left(90)
    while i < puudearv:
 
        pendown()
        puu(randint(20,59))        # Juhusliku pikkusega puu
        penup()
        right(90)
        forward(randint(100,149))  # Puude vahe on ka juhuslik
        left(90)
        i = i + 1
 
delay(0)
speed(10)   
mets(4)
 
exitonclick()

Antud juhul tekib nelja puuga mets:

Korrast kaoseni

Kuigi me mitmeid asju muutsime ja lasime isegi juhuslikult arvutada, meenutasid saadud kujundid ikkagi puid. Teeme nüüd näiliselt suhteliselt väikese muudatuse, nimelt muudame ühe pööramise 45 kraadi asemel 44 kraadiks. Tõenäoliselt me silmaga nendel nurkadel vahet ei teeks.

Näiteprogramm. Kaootiline puu

from turtle import * 
from random import *
 
def puu(pikkus):
    if pikkus < 5:
        forward(pikkus)
        back(pikkus)
    else:
        forward(pikkus)
        left(44)
        puu(randint(6,7) / 10 * pikkus)
        right(90)
        puu(randint(6,7) / 10 * pikkus)
        left(45)
        back(pikkus)
 
delay(0)
speed(10)       
left(90)   
puu(100)
 
exitonclick()

Mis juhtub kujundiga?

Näeme, et puuga enam tegemist pole ning et väike muudatus viis meid hoopis erineva kujundi juurde. Fraktalite puhul kipubki olema nii, et väike muudatus võib olla väga olulise tähendusega.

Litsents

Icon for the Creative Commons Attribution 4.0 International License

Programmeerimine on loodud Eno Tõnisson, Tauno Palts, Merilin Säde, Kaarel Tõnisson jt poolt Creative Commons Attribution 4.0 International License litsentsi alusel, kui pole teisiti märgitud.

Jaga seda raamatut