| < eelmine | 12. nädala sisukord | järgmine > |
12.8 REKURSIOONI TÜÜPE. HARGNEV REKURSIOON
Sissejuhatus
Eelmises peatükis vaatasime näiteid, kus sama ülesanne oli lahendatud kord tsükliga, kord rekursiooniga. Me ei rääkinud sellest, kumba varianti on mõistlikum kasutada. Siin saab eristada programmi kirjutamise ja programmi täitmise aspekti. Programmi täitmise mõttes kipub tsükliga programm rekursioonist kiirem olema. Programmi kirjutamise mõttes aga võib vastavalt ülesandele tsükkel või rekusioon mugavam olla. Mõnedes eeltoodud näidetes võis rekursioon olla küllaltki kunstlik, samas faktoriaali puhul oli rekursioon üsna loomulik, eriti kui valem juba sellisel rekursiivsust soosival kujul oli. Edasi vaatleme veel näiteid, kus programmi on mugavam rekursiivselt kirjutada.
Alustame kahendotsingust, seejärel vaatame hargnevat rekursiooni ja vastastikkust rekursiooni. Senistes näidetes kutsuti funktsiooni kehas seda funktsiooni ennast välja ülimalt üks kord. Tegemist oli lineaarse rekursiooniga, kuna rekursiivsete väljakutsete kontrollvoog oli lineaarne ahel. Võimalikud on aga ka keerukamad rekursiivse väljakutse mustrid. Näiteks hargneva rekursiooni e puurekursiooni puhul kutsutakse funktsiooni "samal tasemel" rekursiivselt välja rohkem kui üks kord. Vastastikuse rekursiooni korral kutsub üks funktsioon küll teist, see teine aga jälle esimest välja.
Kahendotsing
Kellegi või millegi otsimine on elus üsna kesksel kohal. Erinevatel eluetappidel võivad otsingute eesmärgid olla erinevad. Võib-olla sellest materjalilõigust pole otsest abi elu mõtte, armastuse, kurja juure, lohutuse, vea, töökoha otsimisel, aga kaudselt äkki on. Näiteks soovitus püüda vältida otsimist sealt, kus otsitavat kindlasti pole, on ju üsna universaalne.
Olgu meil täisarvude järjend, mille elemendid on sorteeritud mittekahanevalt. Otsimise eesmärke saab erinevaid püstitada, näiteks
- kas etteantud arv on järjendis;
- millises kohas etteantud arv järjendis asub;
- millise elemendi ette etteantud arv järjendisse sobib.
Meie funktsioon otsib, millise indeksiga elemendi ette sobib etteantud arv. Kui on kõigist suurem, siis tagastada indeks, mis võrdne järjendi pikkusega.
Kasutamegi siin ideed, et otsime ainult sealt, kust on mõtet otsida. Nimelt muutujad algus ja lõpp näitavad, millises järjendi osas otsida tuleb. Esialgu on piirkonnaks kogu järjend. Edasi aga leitakse keskel asuv elemendi indeks (kesk = (algus + lõpp) // 2) ning vastavalt sellele, kumba poolde etteantud arv kuulub, jätkatakse just seal otsimist. Igal järgmisel rekursiivsel väljakutsel muutub piirkond väiksemaks, kuni lõpuks on vaatluse all üks element. See ongi rekursiooni baasiks.
def otsi_koht(järjend, x, algus, lõpp):
if algus >= lõpp:
if järjend[algus] < x:
return algus + 1 #
else:
return algus
kesk = (algus + lõpp) // 2
if järjend[kesk] < x:
return otsi_koht(järjend, x, kesk + 1, lõpp)
else:
return otsi_koht(järjend, x, algus, kesk - 1)
a = [1, 4, 5, 6, 7, 7, 23, 45]
print(otsi_koht(a, 7, 0, len(a) - 1))
Hargnev rekursioon e puurekursioon
Vahel öeldakse, et rekursiooni on üldse mõtet kasutada, kui ühel tasemel kutsub funktsioon end välja rohkem kui üks kord.
Kui samal tasemel on rohkem kui üks rekursiivne väljakutse, siis programmi töö graafiline esitus meenutab puud. Näitlikustamiseks võimegi vaadelda puud joonistavat funktsiooni.
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)
Tõepoolest on siin samal tasemel kaks rekursiivset väljakutset puu(randint(6, 7) / 10 * pikkus). Antud juhul on need täpselt samasugused, aga üldiselt ei pruugi olla.
Järgmisel joonisel on puu joonistamine veel pooleli.
Rekursiooni paremaks mõistmiseks võiks järgmise funktsiooni töö käsitsi (või Thonnyga) sammhaaval läbi mängida.
def rekFun(x, y):
print(y)
if x < 0:
return y
else:
return rekFun(x - 1, y + 2) + rekFun(x - 2, y + 3)
print(rekFun(2, 0))
Fibonacci arvud
Sageli tuuakse hargneva rekursiooni näitena Fibonacci arvude arvutamise. Vaatleme seda meiegi.
def fibonacci(n):
if n == 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n - 1) + fibonacci(n - 2)
Näeme, et siingi kutsutakse funktsioon samal tasemel rekursiivselt kaks korda välja.
Fibonacci arvudega on seotud ka küülikute paljunemise ülesanne. Küülikupaaril sünnib iga kuu kaks järglast (emane ja isane). Kahe kuu vanusena hakkavad küülikud ise järglasi saama. Kui palju on küülikuid 12 kuu pärast, kui algul oli üks paar?
Fibonacci arvud on seotud ka kuldlõikega ja taimede ning käbide ehitusega.
Vastastikune rekursioon
Vastastikuse rekursiooni korral ei kutsugi funktsioon otse end rekursiivselt välja. Välja kutsutakse teine funktsioon, mis aga omakorda kutsub välja esimese. Järgmine näites liigutakse baasi poole funktsioone pidi kordamööda.
def paaris(n):
if n == 0:
return True
else:
return paaritu(n - 1)
def paaritu(n):
if n == 0:
return False
else:
return paaris(n - 1)
Kui seda programmi paaris(5) korral Thonnyga läbi mängida, näeme järgmist pilti.
| < eelmine | 12. nädala sisukord | järgmine > |