Rekurzija

Rekurzija je način rešavanja nekog problema korišćenjem rešenja istog problema manje složenosti (dimenzije, veličine). To u praksi znači da rekurzivna implementacija algoritma podrazumeva (direktno ili indirektno) samopozivanje funkcije sa promenjenim argumentima. Moć rekurzije leži u tome što se rešenja teških problema mogu iskazati kroz jednostavne veze.

U nastavku ćemo kroz neke klasične primere videti kako možemo implementirati rekurziju u Haskelu. Primer su poređani od jednostavnijih ka složenijim, i demonstriraju različite oblike rekurzije. Neke druge rekurzivne tehnike ćemo upoznati kasnije kroz Haskel.

Aritmetička suma

Zadatak 1. Napisati funkciju zbir :: Int -> Int koja vraća zbir prvih n prirodnih brojeva.

Funkciju zbir je lako implementirati u nekom imperativnom jeziku pomoću jedne petlje. Međutim, u Haskelu ne postoji pojam petlje, te moramo iskoristiti tehniku rekurzije. To podrazumeva da pri nalaženju rešenja koristimo rešenje istog problema manje složenosti. Konkretno u ovom slučaju prilikom nalaženja zbira brojeva koristimo zbir manje brojeva. Ako napišemo izraz za zbir, rešenje će nam se samo ukazati: zbir n = 1 + 2 + ... + (n - 1) + n Kao što vidimo, u zbiru prvih n prirodnih brojeva, pojavljuje se zbir prvih n - 1 brojeva. Stoga se rešenje u kodu samo nameće: zbir n = zbir (n - 1) + n

Dakle da bismo izračunali, na primer, zbir prvih 5 prirodnih brojeva, izračunaćemo zbir prva 4 prirodna broja i dodati 5 na taj zbir. Da bismo izračunali zbir prva 4 prirodna broja, izračunaćemo zbir prva tri prirodna broja i dodati 4 na taj zbir, itd.. U jednom trenutku ćemo stići do toga da nam je potreban vrednost zbir 0 (zbir nula prirodnih brojeva - prazan zbir). U tom slučaju, nećemo više koristiti vezu koju smo opisali, već ćemo prosto vratiti 0. Takav slučaj, slučaj u kom ne koristimo rekurzivnu definiciju, nazivamo bazni slučaj. Prema tome, funkcija za računanje zbira prvih n brojeva može se ovako zapisati:

zbir :: Int -> Int
zbir n
    | n == 0    = 0
    | otherwise = zbir (n - 1) + n

Pogledajmo na primeru kako napisani program radi. Svaki korak u narednom nizu predstavlja ili izračunavanje ili poziv funkcije zbir: \[\begin{aligned} \mathtt{zbir} \; \mathtt 3 &= \mathtt{zbir \; (3 - 1) + 3} \\ & = \mathtt{zbir \; 2 + 3} \\ & = (\mathtt{zbir \; (2 - 1) + 2) + 3} \\ & = (\mathtt{zbir \; 1 + 2) + 3} \\ & = ((\mathtt{zbir \; (1 - 1) + 1) + 2) + 3} \\ & = ((\mathtt{zbir \; 0 + 1) + 2) + 3} \\ & = \mathtt{(((0 + 1) + 2) + 3 = 6} \end{aligned} \]

Ipak, postoji jedan mali problem sa konstruisanom funkcijom: ako bismo potražili npr. zbir (-3), funkcija bi ušla u beskonačnu rekurziju. Zaista, za računanje vrednosti zbir (-3) bilo bi potrebno izračunati zbir (-4), a za zbir (-4) bi bilo potrebno izračunati zbir (-5), i tako u nedogled. Da bismo sprečili beskonačnu rekurziju, za sve brojeve <= 0, vratićemo 0 kao rezultat. Stoga definišemo funkciju zbir tako da vraća 0 za negativne argumente:

zbir :: Int -> Int
zbir n
    | n <= 0 = 0
    | otherwise = zbir (n - 1) + n

faktorijel' n
    | n <= 0 = 1
    | otherwise = faktorijel' (n - 1) * n

Zadatak 3. Napisati rekurzivnu funkciju koja računa sumu prvih \(k+1\) članova aritmetičkog niza čiji je prvi član \(a\), a korak (razlika između dva susedna člana niza) \(d\). Tačnije napisati rekurzivnu funkciju koja računa sumu \[a+(a+d)+(2+2d)+\cdots+(a+dk).\]

Par-nepar

Zadatak 4. Implementirati funkciju paran :: Int -> Bool koja proverava da li je broj prirodan paran. Pretpostaviti da će argument funkcije biti pozitivan broj.

Korišćenjem funkcije mod, možemo dati odmah sledeće rešenje

paran :: Int -> Bool
paran n = 0 == mod n 2

Problem možemo rešiti i rekurzivno. Znamo da je broj 0 paran, i ta činjenica predstavlja bazu rekurzije. Za svaki drugi prirodan broj n znamo da je paran ako i samo ako je n - 1 neparan. Stoga možemo definisati dve funkcije paran i neparan koje će se međusobno pozivati:

paran :: Int -> Bool
paran 0 = True
paran n = not (neparan (n - 1))

neparan :: Int -> Bool
neparan 0 = False
neparan n = not (paran (n - 2))

Demonstrirajmo izvršavanje koda na jednom primeru: \[\begin{aligned} \mathtt{paran} \; 3 &= \, \mathtt{not} \, (\mathtt{neparan} \; 2)\\ & = \, \mathtt{not} \, (\mathtt{not} \, (\mathtt{paran} \; 1)) \\ & = \, \mathtt{not} \, (\mathtt{not} \, (\mathtt{not} \, (\mathtt{neparan} \; 0))) \\ & = \, \mathtt{not} \, (\mathtt{not} \, (\mathtt{not} \, \mathtt{False})) = \mathtt{False} \end{aligned} \]

Primetimo da navedene funkcije nisu definisane za negativne brojeve.

Zadatak 5. Izmeniti funkcije paran i neparan tako da i za negativne brojeve vraćaju ispravne rezultate.

Zadatak 6. Definisati rekurzivnu funkciju ostatak3 :: Int -> Int koja određuje ostatak broja pri deljenju sa \(3\).

Zadatak 7. Definisati rekurzivnu funkciju ostatak :: Int -> Int -> Int koja određuje ostatak prilikom deljenja prvog argumenta sa drugim argumentom.

Fibonačijev niz

Italijanski srednjovekovni matematičar Leonardo iz Pize je objavio knjigu Liber Abaci¹. Knjiga je bila priručnik za trgovce, a za nas je interesantno da je u jednom od mnogobrojnih primera Fibonači prezentovao račun koji se bavi rastom populacije zečeva na nekoj lokaciji koja do data nije imala zečeve. Nije mnogo važno kako je Fibonači došao do rezultata, ali se ispostavilo da je broj parova zečeva na kraju svakog meseca redom \(1\), \(1\), \(2\), \(3\), \(5\), \(8\), itd... Zapravo, na kraju svakog meseca jednak broju zečeva na kraju prošlog meseca uvećanog za broj zečeva sa kraja pretposlednjeg meseca.

Danas definicija Fibonačijevog niza nema mnogo veze za zečevima, a niz se konstruiše po sledećem principu: prva dva člana Fibonačijevog niza su \(1\) i \(1\). Svaki naredni član Fibonačijevog niza je zbir prethodna dva člana.

Po navedenom principu, treći član Fibonačijevog niza je \(2\) (jer je \(2 = 1 + 1\)), četvrti član je \(3\) (jer je \(3 = 1 + 2\)), peti član je \(5\) (jer je \(5 = 2 + 3\)), šesti član je \(8\) (jer je \(8 = 3 + 5\)), i tako dalje...

Konstruisanje Haskel funkcije fib koja za prosleđeni argument n vraća \(n\)-ti Fibonačijev broj (\(n\)-ti element Fibonačijevog niza) je neznatno složenije nego što su bili prethodni primeri. U ovom slučaju vrednost fib n zavisi od fib (n - 1) i fib (n - 2) te je stoga potrebno navesti dva bazna slučaja².

fib :: Int -> Int
fib n
    | n == 1    = 1 
    | n == 2    = 1
    | otherwise = fib (n - 1) + fib (n - 2)

Zadatak 8. Takozvani Tribonačijev niz se konstruiše na sledeći način: prva tri člana Tribonačijevog niza su \(1\). Svaki naredni član Tribonačijevog niza je zbir prethodna tri člana. Implementirati funkciju koja računa \(n\)-ti Tribonačijev broj.

Euklidov algoritam

Rekurzija može delovati komplikovano kada se prvi susretnemo sa njom, ali je ideja o rekurziji veoma prirodna i veoma stara. Još je Euklid u petom veku pre nove ere u knjizi Elementi izneo nekoliko rekurzivnih postupaka (algoritama). Najpoznatiji je svakako postupak za traženje najvećeg zajedničkog delioca, koji danas nosi naziv Euklidov algoritam.

Kao što samo ime kaže, najveći zajednički delilac (NZD) prirodnih brojeva \(a\) i \(b\) je prirodni broj \(d\) takav da deli \(a\) i \(b\), i pritom je \(d\) najveći broj sa takvom osobinom.

Euklidov algoritam se zasniva na veoma jednostavnoj činjenici: Ako je \(d\) NZD brojeva \(a\) i \(b\), pri čemu je \(a \gt b\), tada je \(d\) NZD brojeva \(b\) i \(a - b\). Zaista, \(d\) deli razliku \(a - b\) jer deli i umanjenik i umanjilac, pa \(d\) jeste zajednički delilac brojeva \(b\) i \(a - b\). Broj \(d\) je najveći broj koji deli i \(b\) i \(a - b\), jer ako bi postojao još veći broj \(d'\) koji deli i \(b\) i \(a - b\) tada bi \(d'\) delio i brojeve \(b\) i \(a = (a -b) + b\), a već znamo da je \(d\) najveći takav broj.

Dakle, ako je \(a > b\) tada je dovoljno naći NZD od \(b\) i \(a - b\). Ako je \(a < b\) tada je po istom argumentu dovoljno naći NZD od \(a\) i \(b - a\). A ako je \(a = b\) tada je NZD od \(a\) i \(b\) jednak baš broju \(a\), jer je svaki broj deljiv samim sobom i ni jedan veći broj ga ne deli. Rekurzivna implementacija je sada u potpunosti jasna:

nzd :: Int -> Int -> Int
nzd a b
    | a == b  = a
    | a >  b  = nzd (a - b) b
    | a <  b  = nzd a (b - a)

Navedeni primer nam ukazuje da ponekad se može desiti da jedan argument umanjujemo više puta za istu vrednost. Broj takvih oduzimanja nije bitan, već samo ostatak koji se dobija na kraju. Da ne bismo neefikasno rekurzivno pozivali funkciju, možemo da podelimo argumente po modulu. Na primer, ako je \(a = nb +r\) za neke prirodne brojeve \(n\) i \(r\), pri čemu je \(n \ge 1\) i \(0\le r \lt b\), tada se oduzimanjem \(n\) puta vrednosti \(b\) od \(a\) dobija ostatak \(r\). Stoga, najveći zajednički delilac brojeva \(a\) i \(b\) je najveći zajednički delilac brojeva \(b\) i \(r\) (jer je³ \(r = a - nb\)). Ovo nas dovodi do malo drugačije i efikasnije implementacije.

Neka je \(r\) ostatak deljenja \(a\) sa \(b\). Ako je \(r\) nula, to znači da je \(a\) deljivo sa \(b\), pa sledi da je NZD ova dva broja bаš \(b\). U suprotnom, dovoljno je potražiti NZD brojeva \(b\) i \(r\). Ovo nas dovodi do narednog koda:

nzd' :: Int -> Int -> Int
nzd' a b = if r == 0 then b else nzd' b r
    where r = mod a b

susret :: Int -> Int -> Int -> Bool
susret p 0 0 = p == 0
susret p m 0 = mod p m == 0
susret p 0 n = mod p n == 0
susret p m n = mod p (gcd n m) == 0

Hanojske kule

Francuski matematičar Edvard Lukas⁴ je krajem devetnaestog veka smislio igru koja je danas poznata kao Hanojske kule⁵.

Igru igra jedan igrač na sledeći način: Postavljena su tri vertikalna štapa koja označavamo sa \(A\), \(B\) i \(C\), i dato je \(n\) diskova različite veličine. Diskovi su probušeni u centru tako da se štap može provući kroz rupu u disku. Na početku igre, diskovi su složeni po veličini na štapu \(A\), od najmanjeg na vrhu do najvećeg na dnu (videti narednu ilustraciju). Igrač u svakom potezu može napraviti jedan potez koji se sastoji samo od pomeranja jednog diska sa jednog štapa na drugi štap. Pritom, disk koji se pomera uvek mora da bude gornji disk na nekom štapu i ne sme se postaviti na manji disk. Cilj je pomeriti diskove tako da se svi diskovi nalaze na štapu \(C\).

Za osobu nije teško da sama dođe do rešenja nakon malo početnog igranja. Ali je na prvi pogled veoma teško napisati program koji formira rešenje za proizvoljan broj diskova.

Prvo ćemo utvrditi kako želimo da prezentujemo rešenje, i koji ulazni parametri su potrebni. Rešenje možemo predstaviti kao listu poteza, od kojih je svaki potez uređen par karaktera koji označavaju štap sa kog i štap na koji prebacujemo disk. Na primer, uređen par ('A', 'B') predstavlja potez u kom se sa prvi disk sa štapa \(A\) prebacuje na štap \(B\). Sa druge strane, rešenje zadatka zavisi samo od broja diskova \(n\). Stoga, naš zadatak je da napišemo funkciju kule :: Int -> (Char, Char) koja pronalazi jedno rešenje⁶.

Naravno, problem ćemo rešiti rekurzivno. Kako problem suštinski zavisi samo od broja diskova, rekurziju ćemo vršiti po \(n\). U najjednostavnijem slučaju, kad je \(n=1\), jasno je da je rešenje jednočlana lista [('A', 'C')], tj. par koji se sastoji od početnog i krajnjeg diska. Pretpostavimo zato da je \(n>1\) i da znamo da rešimo slučajeve za manje diskova. Tada možemo postupiti na sledeći način: prvih \(n-1\) diskova ćemo prebaciti sa početnog na pomoćni (\(B\)) štap, zatim ćemo prebaciti najveći disk sa početnog na krajnji, i na kraju ćemo pomeriti \(n-1\) diskova sa pomoćnog na krajni štap. Ova strategija je prikazana na narednoj ilustraciji.

Kao što vidimo u rekurzivnom koraku \(n-1\) diskova prebacujemo prvo sa štapa \(A\) na štap \(B\). Stoga za rekurzivni poziv, osim broja diskova, mora biti navedeno i sa kog štapa i na koji štap se diskovi prebacuju. Naravno, rešenje ne može koristiti samo dva štapa⁷, već se mora iskoristiti i onaj treći štap kao pomoćni. Stoga funkcija za rekurzivno pronalaženje rešenja uzima četiri parametra: broj diskova, početni štap, krajnji štap i pomoćni štap. Ova rekurzivna funkcija će imati potpis pomeri :: Int -> Char -> Char -> Char -> [(Char, Char)]. Ako je funkcija pomeri implementirana, tada "glavnu" funkciju kule možemo jednostavno implementirati:

kule :: Int -> (Char, Char)
kule n = pomeri n 'A' 'C' 'B'

Potrebno je još implementirati funkciju pomeri, ali to je sasvim jednostavno ako uzmemo u obzir opis rešenja koje smo izložili:

pomeri :: Int -> Char -> Char -> Char -> [(Char, Char)]
pomeri 1 pocetak kraj _       = [(pocetak, kraj)]
pomeri n pocetak kraj pomocni = p1 ++ [(pocetak, kraj)] ++ p2
    where
        p1 = pomeri (n - 1) pocetak pomocni kraj
        p2 = pomeri (n - 1) pomocni kraj pocetak

Zadatak 10. Od koliko poteza se sastoji rešenje koje daje ovaj algoritam? Možete li matematičkom indukcijom da dokažete pravilnost?

Složenost rekurzivnih algoritama

Lepota rekurzivnih algoritama leži u tome što programer na jednostavan način može implementirati komplikovane funkcionalnosti. Programiranje baznog slučaja i rekurzivnog koraka su dovoljni da bi se i naizgled nemogući problemi jednostavno rešili. Primeri i zadaci koji su navedeni u ovoj lekciji bi trebalo da demonstriraju tu elegantnost.

Ipak, lepota rekurzivnih funkcija dolazi po ceni da su one često manje efikasne od odgovarajućih nerekurzivnih funkcija.

zbir' :: Int -> Int
zbir' n = div (n * (n+1)) 2

fib' :: Int -> Int
fib' n = round ((a^n - b^n)/t)
    where t = sqrt 5
          a = (1 + t)/2
          b = (1 - t)/2

Kao što vidimo u prethodnim primerima, implementacija nerekurzivnih funkcija je ponekad značajno složenija nego implementacija rekurzivnih jer su neophodna dodatna znanja iz matematike i teorije algoritama. Sa druge strane, nerekurzivne funkcije mogu posedovati znatno bolju vremensku i prostornu složenost. Prema tome, na programeru je da odluči na koji način će pristupiti problemu: da li je prihvatljivo žrtvovati performanse zarad jednostavnije definicije? Odgovor na ovo pitanje je nemoguće dati jer zavisi od konteksta. U svakom slučaju, tehnika rekurzije je odličan izbor za prvi korak pri rešavanju problema koji deluje značajno teško. Često kada se algoritam savlada rekurzijom, nerekurzivno rešenje postane mnogo jasnije.

Totalne i parcijalne funkcije

Po matematičkoj definiciji funkcije, vrednost \(f(x)\) mora biti definisana za svako \(x\) koje pripada domenu funkcije \(f\). Tako na primer, funkcija \(f(x)=1/x\) ne može za domen imati ceo skup realnih brojeva \(\mathbb R\), već u najboljem slučaju⁸ \(\mathbb R\setminus\{0\}\). Slično, funkcija korenovanja \(s(x)=\sqrt{x}\) može za domen imati samo podskup skupa pozitivnih brojeva⁹.

U računarstvu je malo drugačije. Funkcija tipa A -> B u Haskelu ne mora biti definisana za sve vrednosti tipa A. To smo videli na primeru prve definicije funkcije koja sabira aritmetičku sumu \(1 + \cdots + n\):

zbir :: Int -> Int
zbir n
    | n == 0    = 0
    | otherwise = zbir (n - 1) + n

Za negativne argumente funkcija zbir ulazi u beskonačnu petlju, pa samim tim izraz zbir x nije definisan za svaku vrednost x :: Int.

Funkciju koja nije definisana za svaku vrednost domena, nazivamo parcijalna funkcija, dok funkciju koja je definisana za svaku vrednost domena nazivamo totalna funkcija. Prema tome, pojam funkcija u matematici odgovara pojmu totalnih funkcija u računarstvu.

Rekurzivne funkcije su čest primer funkcija koje nisu totalne, ali ne i jedini¹⁰. Najjednostavniji način za definisanje nerekurzivne parcijalne funkcije je upotrebom podudaranja oblika (ili ograđenih izraza), pri čemu nisu obrađeni svi mogući oblici argumenta:

p :: Int -> Int
p 0 = 1

ghci> p 10
*** Exception: <interactive>:3:1-16: Non-exhaustive patterns in function p

Izuzetak je stanje programa koje označava da je došlo do greške¹¹, i ne predstavlja validnu vrednost.

Postavlja se pitanje, zašto jezik poput Haskela dozvoljava da radimo sa parcijalnim funkcijama? Zašto se umesto toga ne ograničimo na totalne funkcije kao u matematici? Razlog tome je što je nemoguće kreirati programski jezik koji ne bi sadržao parcijalne funkcije a koji bi i dalje bio dovoljno ekspresivan za izražavanje svakog algoritma.

Iako sistem tipova u Haskelu može značajno olakšati rad sa parcijalnim funkcijama (videćemo ovo kroz kasnije lekcije), programer uvek mora biti svestan do kakvih problema može doći. Što se tiče rekurzivnih algoritama, bitno je uočiti slučajeve kada rekurzivni algoritam može ući u beskonačnu petlju, a zatim izmenom tog algoritma obezbediti da do beskonačne petlje nikad ne dođe.

Zadaci

Zadatak 11. Napisati funkciju koja određuje \(n\)-ti stepen broja.

Zadatak 12. Napisati funkciju koja određuje zbir neparnih cifara prirodnog broja.

Zadatak 13. Napisati funkciju koja određuje količnik dva prirodna broja na \(k\) decimala.

Zadatak 14. Napisati funkciju koja određuje binomni koeficijent \(n \choose k\).

Zadatak 15. Za nisku a kažemo da deli nisku s ako je s oblika a ++ a ++ ... ++ a. Na primer, niska "Abc" deli nisku "AbcAbcAbc". Takođe, smatra se da prazna niska "" deli svaku nisku. Napisati funkciju nzd :: [Char] -> [Char] -> [Char] koja određuje najveći zajednički delilac dve niske, odnosno najdužu nisku koja deli obe niske.

Zadatak 16. Spratovi jedne zgrade se kreče u zeleno, plavo ili crveno. Svaki sprat se kreči u jednu od te tri boje. Na koliko načina je moguće okrečiti zgradu, ako važi pravilo da se dva susedna sprata ne smeju okrečiti istom bojom.

Zadatak 17. Za proizvoljan prirodan broj \(n\) definišemo njegov Kolacov niz na sledeći način: \(x_0 = n\), \(x_{m+1} = x_m / 2\) ako je \(x_n\) parno, odnosno \(x_{m+1} = 3 x_m + 1\) ako je \(x_m\) neparno. Pritom ako je \(x_{m+1} = 1\) niz se prekida. Na primer Kolacov niz za \(n = 12\) je \(12, 6, 3, 10, 5, 16, 8, 4, 2, 1\). Pretpostavlja se da će se Kolacov niz svakog prirodnog broja eventualno prekinuti, tj. da će se pojaviti \(1\) u njemu. Naći prirodan broj manji od \(10000\) koji ima najduži Kolacov niz.

Zadatak 18. Metoda polovljenja intervala je numerička metoda određivanja korena neprekidne funkcija tipa \(\mathbb R\to \mathbb R\). Posmatrajmo interval \([a, b]\). Ako za funkciju \(f\) važi da je \(f(a) < 0\) i \(f(b) > 0\) (ili da je \(f(a) > 0\) i \(f(b) < 0\)) za neke brojeve \(a < b\), tada zbog neprekidnosti znamo da postoji \(x\), \(a < x < b\), takvo da je \(f(x) = 0\). Uzmimo \(c = (a + b) / 2\). Ako je \(f(c) \ne 0\) postupak možemo da ponovimo za jedan od intervala \([a , c]\) ili \([c, b]\) (naravno, ako je \(f(c) = 0\), postupak prekidamo). Na ovaj način dobijamo niz intervala čija dužina se prepolovljava, i za koje znamo da sadrže barem jedno rešenje jednačine \(f(x) = 0\). Stoga, u \(n\) koraka možemo odrediti koren jednačine sa greškom manjom od \((b-a)/2^n\). Koristeći ovaj metod, naći koren polinoma \(p(x) = 2x^3-4x^2-6x+2\) na intervalu \([1, 4]\) sa greškom ne većom od \(0.001\).