REKURSIOON - Recursion (0)

REKURSIOON - Recursion
Otsene ja kaudne rekursioon ehk iseenesessepöördumine
Otsene: Kaudne:
┌->┌>PROCEDURE P(...); PROCEDURE P(...); FORWARD ;
│ 2 . . . .
│ └-- P(...); ┌-->PROCEDURE Q(...); ║
1 . . . │ . . . ║
│ END; │ ┌-- P(...); ║ Q
│ . . . 2 │ . . . ║
│ │ 3 ║
└--- P(...); │ │ END; ║
│ │
┌---┼>└>PROCEDURE P(...); ║
│ │ . . . ║
│ └---- Q(...); ║ P
1 . . . ║
│ END; ║
│ . . .
└-------P(...);
Joonis 1. Rekursioon ehk iseenesessepöördumine
Rekursioon: magasini kasutamisnäide
On teada, et alamprogrammi rekursiivsetel välja­kutsetel looda­vad lokaalmuutujate pôlvkonnad paigutatakse pinudesse ja need hävitatakse tagasipöördumistel alamprogram­mist. Järgnevas vaatle­me pinumehhanismi lähemalt. Me teeme seda lihtsa alam­program­mi -- rekursiivse faktoriaalfunkt­siooni näitel. Rekur­siooni käsitlust alustame üldisemast.
Rekursiivsed definitsioonid ja algoritmid
Rekursiivsel defineerimisel määratletakse defineeritav ob­jekt (suurus) iseenda "lihtsama" ("väiksemamastaabilise") eksemplari kaudu. Selline definitsioon määrab protsessi. Selleks, et prot­ sess oleks lôplik, peab definitsioonis esi­nema lihtne mittere­kur­siivne erijuht.
Faktoriaalfunktsiooni rekursiivse definitsiooni vôime anda järgmisena:
┌ 1, kui n = 0,
n! = ┤
└ n*(n - 1)!, kui n > 0
Mitterekursiivseks erijuhuks on siin 0! = 1. Protsess n! leid­mi­seks kajastub n = 4 puhul joonisel 2.
│ 4! = 4*3!  4! = 4*3! = 4*6 = 24
│ 3! = 3*2! │ 3! = 3*2! = 3*2 = 6
│ 2! = 2*1! │ 2! = 2*1! = 2*1 = 2
│ 1! = 1*0! │ 1! = 1*0! = 1*1 = 1
 0! = 1 │ 0! = 1
Joonis 2. Protsess 4! leidmisel
Protsess kulgeb kahes etapis , tinglikult öeldes algul alla­poo­le ja seejärel ülespoole.
Rekursiivse definitsiooni protsessilise iseloomu tôttu vôib kerges­ti tuletada rekursiivse algoritmi suuruse n! leidmi­seks:
IF n = 0 THEN Fakt := 1 IF n = 0 THEN Fakt := 1
a := n - 1 vôi Fakt := n * Fakt(n - 1)
b := Fakt(a)
Fakt := n * b
Neil algoritmidel on môte, kui loeme Fakt'i esinemist omis­tuse vasakul poolel täitmise lôpetamiseks (ei pruugi tähen­dada al­go­ritmi täielikku lôppu) ja paremal poolel ( algo ­ritmis alla kriip­sutatud) rekursiivse täitmise uuestialus­tamiseks.
Rekursiivne alamprogramm on rekursiivse algoritmi esitus konk­reetses keeles, meil Turbo Pascalis. Faktoriaalfunkt­siooni vôime kirja panna väga lihtsana:
FUNCTION Fakt(N: Byte): Longint;
BEGIN
IF N = 0 THEN
BEGIN Fakt := 1; Exit ; END;
Fakt := N * Fakt(N - 1);
END;
Järgneva analüüsi huvides on siiski otstarbekas kirjutada see funktsioon vähem kompaktsena.
Näide. Esitame n! arvutamise rekursiivse funktsiooni sellise­na, kus vahetulemid N - 1 ja Fakt(N - 1) omistatakse abimuutu­jatele A ja B:
FUNCTION Fakt(N: Byte): Longint;
VAR
A: Byte;
B: Longint;
BEGIN
IF N = 0 THEN
BEGIN Fakt := 1; Exit; END;
A := N - 1;
B := Fakt(A);
Fakt := (A + 1) * B;
END;
See funktsioonivariant kirjeldab adekvaatsemalt süsteemi tege­likku tööd funktsiooni täitmisel. Nimelt loob trans­laator oma­ette mäluväljad mitte üksnes alamprogrammi lokaalmuutujatele, vaid ka avaldistes esinevate tehete tulemi­tele. Ka need kan­takse pinu ­desse. Seega saame näite vii­mast varianti analüü­sides ôige pildi süsteemi toimingutest pinudega.
Teine näide: Fibonacci arvud.
Jada: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377...
Fibo(0) = 0, Fibo(1) = 1, Fibo(n + 2) = Fibo(n + 1) + Fibo(n) (n >= 0), s.t. iga järgmine element on kahe eelmise summa.
Ajaloost. Jada vôttis esmakordselt kasutusele Leonardo Fibonac­ci (Pisano = Pisast). Ta elas XIII ja XIV sajandi vahetusel. Tema "Arvutamise raamatus" on kuulus küülikute paljunemise ülesanne:
Mitu küülikupaari tekib ühest paarist aasta jooksul, kui

iga paar annab ühes kuus ühe paari järeltulijaid,

iga uus paar saab suguküpseks ühekuuseks saamisel,

küülikud ei sure kunagi?
Selle ülesande lahendamine viib Fibonacci arvudeni.
Fibonacci arvudel on teadusajaloos tähtis koht. Muu hulgas on nad aparatuuriks algoritmide keerukuse hindamisel.
Fibonacci arvude iteratiivne algoritm Fibo(n) leidmiseks:
IF (N = 0) OR (N = 1) THEN Fibo := N
Eelmine := 0
Järgmine := 1
FOR I := 2 TO N
Abi := Eelmine
Eelmine := Järgmine
Järgmine := Abi + Eelmine
END FOR
Fibo := Järgmine
Rekursiivne definitsioon:
¦ n, kui n = 0 vôi n = 1
Fibo(n) = ¦ Fibo(n - 2) + Fibo(n - 1), kui n > 1
Protsess n = 5 puhul:
F5 = F3 + F4
= F1 + F2 + F4
= ..............................= 5 (Ise teha läbi!)
Rekursiivne algoritm:
┌->┌>IF (N = 0) OR (N = 1) THEN Fibo := N
¦ └ Järgmine := Fibo((N - 1)
└--- Eelmine := Fibo(N - 2)
Fibo := Eelmine + Järgmine
Rekursiivne funktsioon:
FUNCTION Fibo(N: Byte): Longint;
VAR Jargmine, Eelmine: Longint;
BEGIN
IF (N = 0) OR (N = 1) THEN BEGIN Fibo := N; Exit; END;
Jargmine := Fibo(N - 1);
Eelmine := Fibo(N - 2);
Fibo := Eelmine + Jargmine;
END;
Ülesanne: teha ise täitmise analüüs.
Probleemide rekursiivne lahendamine
Kuidas arendada välja rekursiivset algoritmi? See pole eesmärk omaette , seda enam, et enamik probleeme laheneb teisiti lihtsa­malt. Kuid on n.-ö. rekursiivseid probleeme, mille rekursiivne lahendus on loogilisem, elegantsem ja lihtsam.
Kuidas ära tunda, et tasub môelda rekursioonile, s.t. millised on rekursiivse ülesande tunnusjooned? Olgu n! jälle baasnäi­teks, kuigi sellegi ülesande mitterekursiivne lahendus on pa­rem.

palju ühelaadseid operatsioone, mille "mahukus" on erinev: 0!, 1!, 2!, 3!, . . .

saame eristada mitterekursiivset triviaalset erijuhtu : 0! = 1

probleem "keerukamal" juhul on taandatav "lihtsama" juhu lahendamisele: n! = n * (n - 1)!

sel viisil järjest lihtsamale taandamine viib lôpuks tri­viaalse juhuni: 0!-ni
Lahenduskäigu vôime sel juhul rajada oletusele, et me oskame "lihtsamat" juhtu lahendada.
Viies näide. Hanoi tornide ülesanne
a b c
┌┐ ┌┐ ┌┐
¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦
¦ ¦ ¦ ¦ ¦ ¦
┌-┴┴-┐ ¦ ¦ ¦ ¦
┌┴-----┴┐ ¦ ¦ ¦ ¦
┌┴--------┴┐ ¦ ¦ ¦ ¦
┌┴----------┴┐ ¦ ¦ ¦ ¦
┌┴------------┴┐ ¦ ¦ ¦ ¦
┌-┴-------------┴-┐ ┌-------┴┴--------┐ ┌-------┴┴--------┐
└-------------------┘ └--------------------┘ └--------------------┘
Joonis 6. Hanoi tornid
Möödunud sajandil oli see üks populaarsemaid seltskonnamänge.
Tôsta kettad vardalt a vardale c, kasutades b-d (vt. joonis 6):

• korraga tohib liigutada ainult üht ketast -- suvalise varda tippketast;
  
• ketast tohib asetada ainult vardale;
  
• suurem ketas ei tohi sattuda väiksema peale.
  

Legend räägib, et Bramah' kloostris on 3 elevandiluust varrast, millel asub 64 kuldketast. Buda mungad tôstavad ülal­toodud reeglite järgi vahetpidamata kettaid ühelt vardalt teisele. Kui kôik kettad on jôudnud viimasele vardale, saabub maailma lôpp.
Kas probleem vastab "tunnusjoontele"?
(1), (2) ja (3) ilmselt klapivad.
(4): kas vôime tagada ülemineku (n - 1)-lt n-ile?
Näide. n = 5 (vt. joonist 6): kui tôstame n - 1 ketast a-lt c kaudu b-le, saab tôsta 1 ketta a-lt c-le ja 4 ketast b-lt a kaudu c-le. Klapib.
Rekursiivne lahendus on mitterekursiivsest aeglasem, kuid

• on tavaliselt lihtne ja lühike,
  
• tihti on rekursiivne algoritm loomulik ja loogiline (järeldub rekursiivsest definitsioonist ),
  
• üritage lahendada Hanoi tornide probleemi mitterekursiivsena! Kas ônnestub?
  

Rekursiivsed tôestused
Rekursiivsed tôestused on laialt levinud tôestuste vorm. Et ka­sutada rekursiivset tôestust, peavad olema jällegi olemas 4 tunnusjoont (vt. eespool ).
Olgu tarvis leida minimaalne tôstete arv Hanoi tornide ülesan­de lahendamisel.
On lihtne leida, et 1 ketta puhul tuleb teha 1 tôste, 2 ketta puhul 3 ja 3 ketta puhul 7 tôstet. Siit vôime püstitada hüpo­teesi, et n ketta puhul on vaja vähemalt 2n - 1 tôstet. Katsume seda ka tôestada.
Rekursiivsed tôestused koosnevad 2 osast: erijuhu tôestamine ja üldjuhu tôestamine.
Kôigepealt tôestatakse väide ühe konkreetse n korral. Siis näi­datakse, et kui väide kehtib mingi n korral, siis järeldub sel­ lest , et väide kehtib ka n + 1 korral.
Erijuhu tôestamiseks valime n = 1 vôi koguni n = 0, et tôestus oleks triviaalne . Näeme, et triviaalse n korral on tôstete arv tôesti 2n - 1.
Nüüd üldjuht. Olgu n ketta teisaldamiseks vaja 2n - 1 tôstet. n + 1 ketta teisaldamiseks a-lt c-le on vaja algul 2n - 1 tôstet n pealmise ketta teisaldamiseks a-lt b-le, siis 1 tôste alumi­se ketta teisaldamiseks a-lt c-le ja lôpuks veel 2n - 1 tôstet n pealmise ketta teisaldamiseks b-lt c-le, kokku 2n - 1 + 1 + 2n - 1 = 2 * 2n - 1 = 2n+1 - 1 tôstet, mida oligi tarvis tôestada.
Kui rekursiivne programm on tavaliselt aeglasem sama ülesande mitterekursiivsest lahendusest, siis rekursiivne tôestus on ta­valiselt lühem ja lihtsam sama teoreemi mitterekursiivsest tôestusest (proovige näiteks toodud teoreemi tôestada mittere­kursiivselt!)
Millal saabub maailma lôpp
Oletagem, et mungad sooritavad 1 tôste sekundis. Siis kulub neil aega 264 sekundit (-1 pole sealjuures enam oluline). See on umbes 300 miljardit aastat. Arvestades, et maakera vanust hin­natakse 5 miljardile aastale ja elu vanust Maal umbes 1,5 mil­jardile aastale, on see soliidne periood.
Sellest tuleb järeldada, et môni rekursiivne programm vôib töö­tada sôltuvalt ülesande mahust kolossaalselt kaua. Juba 20 ket­ta puhul kulub lahenduseks 6 päeva. Veelkord -- ettevaatust re­kursiooniga!
Toodud koodilõigud on pseudokoodis (alternatiivne ja kohati mugavam kui algoritm).
Materjali originaal asub:
raunz.pri.ee/tty/programmeerimise_p8hikursus.../rekursioon.doc