4 Induktivna i rekurzivna konstrukcija algoritama

U poglavlju 1.4.2 je već diskutovano da u osnovni većine računarskih algoritama krije se ideja da se problemi rešavaju tako što se prethodno reše potproblemi istog oblika, ali manje dimenzije. Ovo je u veoma tesnoj vezi sa principom matematičke indukcije sa jedne i principom rekurzije sa druge strane.

4.1 Matematička indukcija

Matematička indukcija, u svom osnovnom obliku, je sledeći način dokazivanja osobina prirodnih brojeva. Neka je \(P\) proizvoljno svojstvo koje se može formulisati za prirodne brojeve¹. Tada važi

\[(P(0) \wedge (\forall n)(P(n) \Rightarrow P(n+1))) \Rightarrow (\forall n)(P(n))\]

Indukcija je tesno povezana sa skupom prirodnih brojeva, jer je taj skup definisan induktivno, kao najmanji skup koji zadovoljava naredna induktivna pravila:

baza:

nula je prirodan broj;

korak:

sledbenik svakog prirodnog broja je prirodan broj.

Na sličan način, moguće je induktivno predstaviti i druge skupove (tj. tipove podataka).

Nisku (karaktera) moguće je definisati na sledeći način: (baza) prazna niska predstavlja nisku i (korak) dodavanjem karaktera na kraj neke niske dobija se niska.

Slično tome, dekadni zapis prirodnog je ili (baza) zapis dekadne cifre ili (korak) zapis prirodnog broja na koji je nadovezan zapis dekadne cifre sa desne strane.

I aritmetički izrazi (termovi) se mogu definisati induktivno.

baza:

prosti izrazi (konstante i promenljive) su izrazi;

korak:

složeniji izrazi se dobijaju od jednostavnijih primenom aritmetičkih operatora (+, *, \(\ldots\)) ili zagrada.

I neke relacije mogu biti definisane induktivno. Na primer, relacija predak može se definisati na sledeći način:

baza:

roditelj osobe je predak te osobe;

korak:

roditelj bilo kog pretka neke osobe takođe je predak te osobe.

Relacija predak je onda najmanja relacija (u smislu inkluzije) koja zadovoljava ovako zadata pravila (predak nije nijedna osoba za koju se primenom ovih pravila ne može izvesti da je predak).

Indukcija, dakle, nije samo metod za dokazivanje teorema nad prirodnim brojevima, već opštiji princip koji nam daje mogućnost da od jednostavnijih objekata izgradimo složenije, krenuvši od nekih baznih i primenjujući zadata pravila proširenja.

4.2 Rekurzija

Rekurzija je veoma srodan (ali suprotno usmeren) pristup matematičkoj indukciji, u kojem se neka funkcija definiše na osnovu jednog ili više baznih slučajeva i na osnovu pravila koja složene slučajeve svode na jednostavnije. Većina savremenih programskih jezika dopušta definisanje rekurzivnih funkcija – funkcija može da pozove samu sebe, pri čemu korisnik treba da bude siguran da će se taj lanac rekurzivnih poziva u nekom trenutku zaustaviti (obično tako što će svaki naredni rekurzivni poziv biti za manju vrednost parametra).

int faktorijel(int n) {
  if (n == 0) return 1;
  else return n * faktorijel(n-1);
}

Izostanak bilo baznog koraka (koji obezbeđuje “zaustavljanje” primene definicije) bilo rekurzivnog koraka čini definiciju nepotpunom².

4.3 Odnos indukcije i rekurzije

Indukcijom se od jednostavnijih objekata dobijaju složeniji, dok se rekurzijom izračunavanje složenijih objekta svodi na izračunavanje jednostavnijih. Na primer, u induktivnoj definiciji prirodnih brojeva koristila se činjenica da je sledbenik prirodnog broja prirodan broj, a u rekurzivnoj definiciji smo izračunavanje vrednosti faktorijela sveli na izračunavanje vrednosti faktorijela prethodnika.

Zbog jake povezanosti indukcije i rekurzije govori se i o induktivno/rekurzivnoj konstrukciji algoritama, koja podrazumeva da se rešenje problema veće dimenzije pronalazi korišćenjem rešenja problema istog oblika, ali manje dimenzije. Pritom za početne dimenzije problema rešenje je potrebno izračunati direktno, bez svođenja na manje potprobleme. Ako se prilikom svođenja dimenzija problema uvek smanjuje, konstruisani algoritmi će se uvek zaustavljati.

• Implementacija može biti takva da promenljive unutar petlje iterativno ažuriraju svoje vrednosti krenuvši od vrednosti rešenja elementarnih problema, pa do vrednosti rešenja zadatog problema. Pošto je ovo prilično slično principu matematičke indukcije, kažemo da je algoritam definisan induktivno.

• Implementacija može biti takva da funkcija koja rešava polazni problem poziva sebe da bi rešila manje potprobleme (osim kod elementarnih problema, koji se direktno rešavaju) i tada kažemo da je algoritam definisan rekurzivno.

4.4 Primitivna i opšta rekurzija

Princip dokazivanja matematičkom indukcijom je u vezi sa induktivnom definicijom skupa prirodnih brojeva – to je najmanji skup koji sadrži nulu i zatvoren je za operaciju sledbenika. Stoga je algoritme za rad sa prirodnim brojevima moguće definisati tako da u slučaju izlaska iz rekurzije razrešavaju slučaj nule, dok u slučaju nekog broja većeg od nule (sledbenika nekog broja) rekurzivno svode problem na slučaj njegovog prethodnika. Ovakav tip rekurzije, koji direktno odgovara induktivnoj definiciji tipa podataka, naziva se primitivna rekurzija.

Kada u obzir uzmemo induktivnu definiciju dekadnog zapisa prirodnog broja (u kojoj bazu čine jednocifreni brojevi, a višecifreni brojevi se dobijaju dopisivanjem cifre zdesna na već postojeći dekadni zapis), lako možemo definisati primitivno rekurzivne funkcije takve da izlaz iz rekurzije predstavljaju jednocifreni brojevi, dok se slučaj višecifrenog broja razrešava svođenjem na broj sa odsečenom poslednjom cifrom. Ako je broj \(n\) predstavljen podatkom celobrojnog tipa, poslednju cifru možemo odrediti izrazom n%10, a možemo je ukloniti izrazom n/10.

int zbir_cifara(int n) {
  if (n < 10)
    return n;
  return zbir_cifara(n / 10) + n % 10;
}

Dualni pristup – razlaganje broja na prvu cifru i na ostale cifre – u ovom slučaju nije pogodan, zbog toga što ovakvo razlaganje nije moguće sprovesti jednostavnim matematičkim operacijama.

Funkcije koje obrađuju niske se takođe mogu definisati rekurzivno, tako da pri izlasku iz rekurzije obrađuju slučaj prazne niske, dok slučaj neprazne niske dužine \(n\) rešavaju tako što rekurzivno razreše njen prefiks dužine \(n-1\) i onda rezultat iskombinuju sa poslednjim elementom niske.

int broj_razmaka(const string& s, int n) {
   if (n == 0) return 0;
   if (s[n-1] == ' ')
      return 1 + broj_razmaka(s, n-1);
   else
      return broj_razmaka(s, n-1);
}

int broj_razmaka(const string& s) {
   return broj_razmaka(s, s.length());
}

B("ab c d") = B("ab c ") = 1 + B("ab c") = 1 + B("ab ") =
2 + B("ab") = 2 + B("a") =  2 + B("") = 2

Dualno razlaganje na prvi element i sufiks niske takođe je moguće, pri čemu je onda prilikom svakog rekurzivnog poziva potrebno, pored dužine niske, prosleđivati i poziciju početka sufiksa.

U nekim slučajevima, potrebno je koristiti i naprednije oblike indukcije, kakva je, na primer, totalna indukcija. U tom slučaju, nakon dokazivanja induktivne baze, u okviru induktivnog koraka moguće je pretpostaviti tvrđenje za sve brojeve manje od \(n\) i iz te pretpostavke dokazati tvrđenje za broj \(n\). Slično, pored primitivno rekurzivnih funkcija, postoje i funkcije koje su generalno (opšte) rekurzivne. Tako je, na primer, prilikom razmatranja nekog broja \(n\), dozvoljeno izvršiti rekurzivni poziv za bilo koji broj manji od njega (pa čak i više rekurzivnih poziva za različite prirodne brojeve manje od njega).

Na primer, definicija brzog stepenovanja, opisana u glavi 1, svodi vrednost \(n\) (za parno \(n\)) na vrednost \(n/2\), umesto na \(n-1\), pa je u pitanju primena generalne rekurzije. I prilikom implementacije algoritma koji radi sa nekim nizom, dozvoljeno je vršiti rekurzivne pozive za sve podnizove polaznog niza kraće od njega. Rekurzivna obrada dve polovine niza često vodi boljoj efikasnosti nego primitivno-rekurzivna obrada podniza dobijenog izbacivanjem poslednjeg (ili prvog) elementa niza.

Prilikom upotrebe totalne rekurzije, dopušteno je da se u sklopu jednog poziva funkcije izvrši i više rekurzivnih poziva. Takođe, ponekad bazni slučaj mora da pokriva više od jedne vrednosti. Jedan primer takve funkcije je funkcija koja izračunava elemente Fibonačijevog niza, opisana u poglavlju 4.6.1.

4.5 Realizacija rekurzije

Rekurzija se realizuje u skladu sa opštim mehanizmom izvršavanja funkcija: za svaki rekurzivni poziv stvara se novi stek okvir i u njemu se čuvaju informacije potrebne za izvršavanje funkcije ali i za nastavak izvršavanja programa. Ono što odlikuje rekurzivne pozive je to da za jednu istu funkciju na programskom steku može postojati više stek okvira, obično za različite vrednosti argumenata funkcije. Međutim, u memoriji računara postoji uvek samo jedna kopija kôda funkcije (koja se nalazi u segmentu koda). Naime, za različite instance iste funkcije (tj. za sve aktivne pozive funkcije) potrebno je pamtiti dokle je stalo njihovo izvšavanje ali nije potrebno imati nezavisne kopije kôda funkcije.

Primer 4.5.1. Razmotrimo ponovo funkciju koja računa faktorijel broja:

int faktorijel(int n) {
  if (n == 0) return 1;
  else return n * faktorijel(n-1);
}

Pretpostavimo da je iz funkcije main pozvana funkcija faktorijel sa argumentom \(3\). Tada se na programskom steku nalaze dva stek okvira, jedan za funkciju main, a jedan za funkciju faktorijel sa argumentom \(3\) (slika 16, prva slika s leva). Stek okvir za faktorijel čuva i mesto u kôdu (adresu instrukcije u kodu funkcije main) na koje se treba vratiti kada se završi izvršavanje funkcije faktorijel. Tokom izvršavanja funkcije faktorijel, utvrdi se da \(n\) nije jednako \(0\), te se prelazi na drugu granu grananja, poziva se funkcija faktorijel za \(n=2\) i stvara stek okvir za tu instancu funkcije faktorijel, gde će biti zapamćeno, između ostalog, i gde treba nastaviti izvršavanje funkcije za argument \(3\) (slika 16, druga slika s leva). Analogno se poziva funkcija faktorijel za argument \(1\) i za argument \(0\).

Kada se izvrši funkcija faktorijel za argument \(0\), njen rezultat (vrednost \(1\)) će biti poznat i vraćen pozivaocu (najčešće tako što se upiše u za to namenjen registar), biće obrisan stek okvir za poziv funkcije faktorijel za vrednost \(0\) i biće nastavljeno izvršavanje faktorijel za argument \(1\) (od mesta koje je bilo sačuvano u stek okviru za \(0\)). Ona će zatim pomnožiti tu povratnu vrednost \(1\) sa vrednošću svoje promenljive \(n\) (takođe \(1\)) i rezultat \(1\) će vratiti svom pozivaocu (što je poziv faktorijel za \(n=2\)). Analogno će biti završeno i izvršavanje preostale instance funkcije faktorijel i rezultat \(6\) instance za \(n=3\) biće vraćen funkciji main (najčešće preko registra). Pre nego što bude oslobođen stek okvir za faktorijel za \(n=3\) iz njega će biti pročitano od koje instrukcije treba da se nastavi izvršavanje funkcije main.

4.6 Primeri rekurzivnih funkcija

Prikažimo u nastavku još nekoliko primera rekurzivnih funkcija.

4.6.1 Fibonačijev niz

Jedan od primera koji se često koristi radi ilustracije dobrih i loših strana rekurzije je Fibonačijev niz (0,1,1,2,3,5,8,13,…) u kojem važi da je svaki naredni član jednak zbiru prethodna dva.³ On se može definisati u vidu (opšte) rekurzivne funkcije \(\mathit{fib}\) (primetimo da bazni slučaj pokriva dve vrednosti (\(0\) i \(1\)), a da rekurzivni korak koriste dve prethodne vrednosti niza):

bazni slučaj

\(\mathit{fib}(0) = 0\) i \(\mathit{fib}(1) = 1\) (tj. za \(n = 0\) važi \(\mathit{fib}(n) = 0\) i za \(n = 1\) važi \(\mathit{fib}(n) = 1\))

rekurzivni korak

za \(n > 1\) važi: \(\mathit{fib}(n) = \mathit{fib}(n - 1) + \mathit{fib}(n - 2)\)

Funkcija za izračunavanje \(n\)-tog elementa Fibonačijevog niza može se definisati na sledeći način:

int fib(int n) {
  if (n == 0 || n == 1)
    return n;
  else
    return fib(n-1) + fib(n-2);
}

Ovaj pristup generisanju Fibonačijevih brojeva, iako veoma jednostavan za implementaciju, veoma je neefikasan i biće diskutovani mogući pravci poboljšanja. Primetimo da se za razliku od svih do sada prikazanih rekurzivnih funkcija, u sklopu jednog poziva funkcije vrše dva rekurzivna poziva. Ovo samo po sebi ne mora biti problematično, međutim, u ovom konkretnom slučaju se dešava da se rekurzivni pozivi ponavljaju za iste vrednosti parametara, što je jedan od osnovnih problema naivnih rekurzivnih implementacija i što dovodi do ogromne neefikasnosti.

Zaista, neka \(T(n)\) označava broj instrukcija koje zahteva poziv funkcije fib za ulaznu vrednost \(n\). Za \(n \leq 1\) važi \(T(n)=c_1\), gde je \(c_1\) neka konstanta. Za \(n>1\), važi \(T(n)=T(n-1)+T(n-2)+c_2\), gde je \(c_2\) neka konstanta. Iz \(T(n)=T(n-1)+T(n-2)+c_2\) i \(T(n+1)=T(n)+T(n-1)+c_2\), sledi \(T(n+1)=2T(n)-T(n-2)\). Karakteristična jednačina ove jednačine je \(t^3=2t^2-1\) i njeni koreni su \(1\), \(\frac{1+\sqrt{5}}{2}\) i \(\frac{1-\sqrt{5}}{2}\), pa je opšte rešenje oblika \(T(n)=a\cdot 1^n + b \cdot \left(\frac{1+\sqrt{5}}{2}\right)^n+ c \cdot \left(\frac{1-\sqrt{5}}{2}\right)^n,\) odakle sledi \(T(n)=O(\left(\frac{1+\sqrt{5}}{2}\right)^n)\).

Primer 4.6.1. Funkcije sličnog tipa često se dobijaju kada se tehnika rekurzije primeni na rešavanje nekih problema prebrojavanja. Kao ilustraciju rekurzivnog pristupa rešavanju problema, razmotrimo broj načina da se pravougaona tabla dimenzije \(2 \times k\) poploča pločicama dimenzije \(1 \times 2\) i \(2 \times 1\). Sva popločavanja table dimenzije \(2 \times 4\) prikazana su na narednoj slici (ima ih 5).

Prvo polje na tabli (polje u gornjem levom uglu) mora biti prekriveno dominom. Ona mora biti postavljena ili vertikalno ili horizontalno.

• Ako dominu postavimo vertikalno, ostaje da se pokrije deo table bez prve kolone, što je problem istog oblika, a manje dimenzije, pa se može rešiti rekurzivno.

• Dominu možemo postaviti horizontalno samo ako tabla ima bar dve kolone. Pošto i drugo polje u prvoj koloni mora biti pokriveno, ispod prve moramo postaviti još jednu horizontalnu dominu. Tada preostaje da se pokriju sve kolone table, osim prve dve, što je opet problem istog oblika, ali manje dimenzije, koji se rešava rekurzivno.

Izlaz iz rekurzije predstavlja tabla dimenzije \(2 \times 0\), koja se može popločati samo na jedan način (bez domina) i tabla dimenzije \(2 \times 1\), koja se takođe može popločati samo na jedan način (jednom vertikalnom dominom). Ako \(F(k)\) označava broj popločavanja table \(2\times k\), važi da je \(F(0) = F(1) = 1\) i da je \(F(k) = F(k-1) + F(k-2)\), što je upravo jednačina koja definiše Fibonačijev niz.

4.6.2 Grejovi kodovi

Binarni brojevi sa \(n\) cifara obično se ređaju po veličini (na primer, 000, 001, 010, 011, 100, 101, 110, 111). Alternativno, Grejov kôd⁴ podrazumeva da se binarni brojevi ređaju tako da se svaka dva susedna broja razlikuju tačno na jednom bitu (pri čemu to svojstvo važi i za poslednji i prvi broj u nizu). Trocifreni Grejov kôd može biti 000, 001, 011, 010, 110, 111, 101, 100. Ovo nije jedini trocifreni Grejov kôd, ali se on ipak najčešće razmatra, jer je dobijen vrlo pravilnim, sistematičnim postupkom. Naime, prva četiri broja počinju sa 0, dok naredna četiri broja počinju sa 1. Kada se sa početka prva četiri broja izbriše 0, dobija se dvocifren Grejov kôd 00, 01, 11, 10, dok se brisanjem 1 sa početka naredna četiri broja dobija isti taj Grejov kôd, ali u obratnom poretku. I ovaj dvocifreni Grejov kôd je dobijen na isti način. Prva dva broja počinju sa 0, nakon koje se javlja jednocifreni kôd 0, 1, a druga dva broja počinju sa 1 iza čega se javlja obratan jednocifreni kôd. Čak i za jednocifreni kôd možemo konstantovati isto. Prvi broj počinje sa 0 nakon koje ide Grejov kôd sa nula cifara (koji je prazan), dok drugi broj počinje sa 1 nakon koje ide isti taj kôd sa nula cifara (koji je prazan) u obratnom redosledu.

Definišimo rekurzivnu funkciju koja određuje \(k\)-ti po redu broj \(n\)-tocifrenog Grejovog koda (on sadrži \(2^n\) brojeva i podrazumevaćemo da je \(0 \leq k < 2^n\)). Za \(n=0\) rezultat je prazna niska. U suprotnom, treba izračunati odgovarajući element Grejovog koda sa \(n-1\) cifara i zatim ga dopuniti sleva nulom ili jedinicom. Treba razlikovati slučaj elemenata u prvoj i u drugoj polovini Grejovog koda.

• Kada je element u prvoj polovini, tada je \(0 \leq k < 2^{n-1}\) i funkcija vraća \(k\)-ti element Grejovog koda sa \(n-1\) cifara, dopunjen početnom nulom.

• Kada je element u drugoj polovini, tada je \(2^{n-1} \leq k < 2^n\) i funkcija vraća \(2^n - 1 - k\)-ti element Grejovog koda sa \({n-1}\) cifara, dopunjen početnom jedinicom. Izrazom \(2^n - 1 - k\) se pozicija \(k\) svodi u raspon \([0, 2^{n-1})\) i ujedno se obrće redosled brojeva. Naime, operacijom \(k - 2^{n-1}\) vršimo redukciju intervala \([2^{n-1}, 2^n)\) na interval \([0, 2^{n-1})\). Generalno, prilikom obrtanja redosleda elemenata, svaka pozicija \(p\) u intervalu \([0, m)\) se preslikava u poziciju \(m-p-1\). Stoga se prilikom obrtanja intervala \([0, 2^{n-1})\) pozicija \(k - 2^{n-1}\) slika u \(2^{n-1} - (k - 2^{n-1}) - 1\), no to je jednako \(2^n - 1 - k\).

Izračunavanje stepena dvojke najjednostavnije se vrši bitovskim operacijama. Šiftovanje broja 1 za \(m\) pozicija ulevo ekvivalentno je sa \(n\) uzastopnih množenja sa 2 i izračunava tačno vrednost \(2^m\) (pod pretpostavkom da ne dođe do prekoračenja).

Elementi Grejovog koda mogu se jednostavno predstaviti u obliku niski karaktera. Iako dopisivanje karaktera na početak niske može biti neefikasna operacija, s obzirom na to da su niske sa kojima radimo prilično kratke (najduža ima 32 karaktera), o tom ne moramo da brinemo.

string grej(int n, int k) {
  if (n == 0) return "";
  if (k < (1ul << (n - 1)))
     return ”0” + grej(n - 1, k);
  else
     return ”1” + grej(n - 1, (1ul << n) - 1 - k);
}

Poziv funkcije grej(5, 17) vraća nisku 11001. Zaista, ako obeležimo funkciju skraćemo sa \(G\), važi:

\[\begin{eqnarray*} G(5, 17) &=& "1" + G(4, 14) = "11" + G(3, 1) = "110" + G(2, 1)\\ &=& "1100" + G(1, 1) = "11001" + G(0, 0) = "11001" \end{eqnarray*}\]

4.6.3 Hanojske kule

Problem kula Hanoja⁵ glasi ovako: date su tri kule i na prvoj od njih \(n=64\) diska opadajućih veličina; zadatak je prebaciti sve diskove sa prve na treću kulu (koristeći i drugu) ali tako da nikada nijedan disk ne stoji iznad nekog manjeg.

Za razliku od iterativnog, rekurzivno rešenje ovog problema je prilično jednostavno: ukoliko je \(n=0\), nema diskova koji treba da se prebacuju; inače, prebaci (rekurzivno) \(n-1\) diskova sa polaznog na pomoćnu kulu (korišćenjem dolazne kule kao pomoćne), prebaci najveći disk sa polazne na dolaznu kulu i, konačno, prebaci (rekurzivno) \(n-1\) diskova sa pomoćne na dolaznu kulu (korišćenjem polazne kule kao pomoćne). U nastavku je implementacija ovog rešenja:

void kule(int n, char polazna, char dolazna, char pomocna) {
  if (n > 0) {
    kule(n-1, polazna, pomocna, dolazna);
    printf("Prebaci disk sa kule %c na kulu %c\n", 
                                 polazna, dolazna);
    kule(n-1, pomocna, dolazna, polazna);
  }
}

Poziv navedene funkcije kule(3,'A','C','B') daje sledeći izlaz:

Prebaci disk sa kule A na kulu C
Prebaci disk sa kule A na kulu B
Prebaci disk sa kule C na kulu B
Prebaci disk sa kule A na kulu C
Prebaci disk sa kule B na kulu A
Prebaci disk sa kule B na kulu C
Prebaci disk sa kule A na kulu C

Izračunajmo broj prebacivanja diskova \(T(n)\) koje opisuje navedena funkcija. Važi \(T(0)=0\) i \(T(n)=2T(n-1)+1\). Dakle, jednačina koja opisuje ovaj niz je nehomogena rekurentna jednačina prvog reda. Iz \(T(n)-2T(n-1)=1=T(n-1)-2T(n-2)\) (za \(n>1\)) sledi \(T(n)=3T(n-1)-2T(n-2)\). Ova jednačina je homogena jednačina drugog reda, njena karakteristična jednačina je \(t^2=3t-2\) i njeni koreni su \(2\) i \(1\), pa je opšte rešenje \(\alpha \cdot 2^n + \beta \cdot 1^n\). Rešavanjem sistema dobijenog za \(n=0\) i \(n=1\) sledi \(\alpha=1\) i \(\beta=-1\), pa je \(T(n)= 2^n - 1.\), što određuje eksponencijalnu vremensku složenost ove funkcije.

Razmotrimo sada i prostornu složenost \(S(n)\) funkcije kule. Jedna instanca funkcije kule zauzima (na programskom steku) konstantan prostor \(c\). U okviru funkcije kule u jednom trenutku može izvršavati najviše jedan od dva rekurzivna poziva. Zato za prostornu složenost važi: \(S(n) = S(n-1) + c\) i \(S(0) = c\) (a ne \(S(n) = 2S(n-1) + c\)), odakle se dobija da \(S(n)\) pripada klasi \(O(n)\). Na programskom steku, za ulazni argument \(n\), može se u jednom trenutku naći najviše \(n+1\) stek okvira instanci funkcije kule.

4.6.4 Popunjavanje konture na slici

Često postoji potreba da se sistematično obiđu i obrade elementi nekog skupa koji su međusobno povezani. To, na primer, mogu biti elementi neke matrice, istobojna polja na nekoj slici ili gradovi (koji su povezani ako između njih postoji direktan put) i slično. Obilazak svih elemenata do kojih se može stići od nekog početnog elementa često se sprovodi rekurzivnim algoritmima.

Programi za obradu slika nude alat za popunjavanje (“fill” alatka). Potrebno je izabrati piksel određene boje i čitava oblast slične boje koja je ograničena konturom druge boje ili rubom slike biće obojena zadatom bojom (smatramo da su pikseli susedni ako imaju jednu stranicu zajedničku). Slika @fig:floodfill prikazuje jednu konturu (levo) i rezultat popunjavanja ako je bila izabrana tačka unutar polazne konture (desno).

Razmotrimo pojednostavljenu varijantu problema: smatrajmo obojeni pikseli imaju vrednost \(1\), a ostali imaju vrednost \(0\). U rekurzivnom rešenju (to je, takozvano, flood fill rešenje), kreće se od zadatog piksela, on se boji i onda se ista funkcija poziva za četiri susedna piksela. Za tekući piksel se proverava da li je već obojen ili je van granica slike i ta provera omogućava izlazak iz rekurzije. Slika je predstavljena dvodimenzionim nizom slika koji sadrži nule i jedinice. Jednostavnosti radi pretpostavićemo da je taj niz statički alociran, a da su poznate dimenzije \(m\) i \(n\) dela koji treba obraditi, kao i koordinate početnog polja \(v\) i \(k\).

void floodFill(int slika[MAX_DIM][MAX_DIM], int m, int n, 
               int v, int k) {
  // da li je polje (v,k) van slike?
  if (!(0 <= v && v < m && 0 <= k && k < n)) 
    return;
    
  // da li je polje (v,k) vec obojeno?
  if (slika[v][k]) 
    return;
  
  slika[v][k] = 1;
  floodFill(slika, m, n, v+1, k); 
  floodFill(slika, m, n, v-1, k); 
  floodFill(slika, m, n, v, k-1); 
  floodFill(slika, m, n, v, k+1); 
}

Ako se funkcija pokrene za narednu matricu prikazanu levo i to sa pozicije x=2, y=2, dobija se matrica prikazana desno.

00100100  00111100 
01000100  01111100 
01000100  01111100 
00100100  00111100 
00011111  00011111

Funkcija floodFill ima četiri rekurzivna poziva, te deluje da će lako doći do eksplozije broja polja koja se ispituju. Međutim, ne ulazi se u rekurziju za piksele koji su već obrađeni i obojeni, te je broj piksela koji se obrađuju reda \(O(mn)\) i tolika je i vremenska složenost funkcije floodFill. Stek okvir za funkciju floodFill je konstante veličine, ali je pitanje koliko rekurzivnih poziva može biti aktivno u jednom trenutku, tj. koliko najviše može biti stek okvira na programskom steku. Taj broj je, naravno, ograničen odozgo vrednošću \(mn\), a slika @fig:floodfill2 ilustruje jedan tip situacija u kojma je broj stek okvira reda \(\Theta(mn)\):

U poglavlju 4.9.2 biće prikazano rešenje ovog problema bez korišćenja rekurzije.

4.7 Uzajamna rekurzija

U dosadašnjim primerima, rekurzivne funkcije su pozivale same sebe direktno. Postoji i mogućnost da se funkcije međusobno pozivaju i tako stvaraju uzajamnu rekurziju. Poželjno je da kompilator zna definiciju funkcije pre svakog njenog poziva. Međutim, ako se dve funkcije uzajamno pozivaju, tada to nije moguće (jer u bilo kom redosledu definisanja pre poziva druge funkcije u sklopu prve funkcije definicija te druge funkcije još nije viđena). Pošto je ispravno prevođenje moguće ako se pre poziva zna samo deklaracija (prototip funkcije), rešenje može biti tako što se pre definicija funkcija navedu njihove deklaracije (dovoljno bi bilo navesti i jednu deklaraciju, ali simetrije radi ne smeta da se navedu obe).

Uzajamna rekurzija je ponekad važna tehnika konstrukcije algoritama. Prikažimo to na jednom primeru. Mnogi pojmovi se definišu korišćenjem induktivnih definicija koje posredno zavise jedna od druge. Razmotrimo, na primer, aritmetičke izraze koji sadrže prirodne brojeve i operatore + i *. Svaki izraz je niz sabiraka razdvojenih operatorom + (to uključuje i mogućnost da postoji samo jedan sabirak), svaki sabirak je niz činilaca razdvojenih operatorom * (to uključuje i mogućnost da postoji samo jedan činilac), dok je svaki činilac ili ceo broj ili izraz u zagradama. Dakle, izraz smo definisali preko sabiraka, sabirke preko činilaca, a činioce preko izraza.

Za obradu izraza u računarstvu često se koristi tehnika poznata pod nazivom rekurzivni spust, koja se zasniva na uzajamnoj rekurziji. Funkcije koje čitaju aritmetički izraz i izračunavaju njegovu vrednosti mogu biti definisane na sledeći način (korišćenjem uzajamne rekurzije). Pretpostavićemo da funkcija procitaj_sledeci_simbol čita sledeći simbol sa ulaza (to može biti cifra, operator, neka zagrada ili kraj ulaza) i u promenljivoj sledeci_simbol beleži o kojoj vrsti simbola se radi, a da prilikom čitanja broja u promenljivu vrednost_broja smesti i njegovu brojnu vrednost. Kada se na ulazu pojavi bilo koji simbol koji ne može biti deo izraza, vraća se oznaka da je prepoznat kraj izraza, učitavanje se prekida i ispisuje se vrednost do tada učitanog izraza. Funkcija main poziva funkciju izraz() i ispisuje vrednost unetog izraza.

// deklaracije funkcija
int izraz();
int sabirak();
int cinilac();

// definicije funkcija
int izraz() {
  int vrednost = sabirak();
  while (sledeci_simbol == PLUS) {
    procitaj_sledeci_simbol();
    vrednost += sabirak();
  }
  return vrednost;
}

int sabirak() {
  int vrednost = cinilac();
  while (sledeci_simbol == PUTA) {
    procitaj_sledeci_simbol();
    vrednost *= cinilac();
  }
  return vrednost;
}

int cinilac() {
  if (sledeci_simbol == BROJ) {
    procitaj_sledeci_simbol();
    return vrednost_broja;
  } else if (sledeci_simbol == OTVORENA_ZAGRADA) {
    procitaj_sledeci_simbol();
    int vrednost = izraz();
    if (sledeci_simbol != ZATVORENA_ZAGRADA)
      prijavi_gresku();
    procitaj_sledeci_simbol();
    return vrednost;
  } else
    prijavi_gresku();
}

int main() {
  procitaj_sledeci_simbol();
  cout << izraz() << endl;
  return 0;
}

Program za ulaz (1+2)*(3+45) daje izlaz 144, a za ulaz (1+2. prijavljuje grešku.

4.8 Dobre i loše strane rekurzije

Dobre strane rekurzije su (obično) čitljiv i kratak kod, jednostavan za razumevanje, analizu, dokazivanje korektnosti i održavanje. Ipak, rekurzivna rešenja imaju i mana.

4.8.1 Cena poziva

Prilikom svakog rekurzivnog poziva kreira se novi stek okvir i kopiraju se argumenti funkcije. Kada rekurzivnih poziva ima mnogo, to može biti veoma zahtevno u smislu memorije (a donekle i u smislu vremena). Kako je veličina stek segmenta i na savremenim sistemima relativno mala,⁶ rekurzivne funkcije mogu dovesti do prekoračenja programskog steka i prekida rada programa. Zato je u nekim situacijama poželjno rekurzivno rešenje zameniti iterativnim (vidi poglavlje 4.9). Jedna opšta preporuka je da bi dubina rekurzije trebalo da raste znatno sporije od dimenzije ulaza (jer dimenzija ulaza koja se može obraditi je relativno mala čak i u slučaju kada dubina rekurzije linearno zavisi od dimenzije ulaza).

4.8.2 Suvišna izračunavanja

U nekim slučajevima prilikom razlaganja problema na manje potprobleme dolazi do preklapanja potproblema i do višestrukih rekurzivnih poziva za iste potprobleme.

Razmotrimo, na primer, izvršavanje navedene funkcije koja izračunava elemente Fibonačijevog niza za \(n=5\), prikazano na slici @fig:fibonaci. Funkcija fib je tri puta pozvana za \(n=0\), pet puta za \(n=1\), tri puta za \(n=2\) i tako dalje. Zbog ovoga, izvršava se mnogo suvišnih izračunavanja. Rešenje ovog problema opisano je u poglavlju @sec:dinamicko.

Treba voditi računa o tome da se ponovljena izračunavanja greškom ne uvedu tamo gde ih je veoma jednostavno izbeći. Razmotrimo narednu rekurzivnu implementaciju funkcije za izračunavanje minimuma nepraznog niza.

int minimum(int a[], int n) {
  if (n == 1) return a[0];
  if (a[n-1] < miminum(a, n-1))
     return a[n-1];
  else
     return minimum(a, n-1);
}

U ovoj implementaciji se može desiti da se u istom pozivu dva puta rekurzivno pozove minimum(a, n-1), što dovodi do eksponencijalne složenosti. Ovo se lako može rešiti tako što se rezultat poziva zapamti u pomoćnoj promenljivoj.

int minimum(int a[], int n) {
  if (n == 1) return a[0];
  int M = miminum(a, n-1);
  if (a[n-1] < M)
     return a[n-1];
  else
     return M;
}

Alternativno, možemo upotrebiti i bibliotečku funkciju min, koja pronalazi minimum dva broja.

int minimum(int a[], int n) {
  if (n == 1) return a[0];
  return min(a[n-1], miminum(a, n-1));
}

4.9 Oslobađanje od rekurzije

Svaku rekurzivnu funkciju je moguće implementirati na drugi način tako da ne koristi rekurziju. Opšti postupak za takvo oslobađanje od rekurzije uključuje implementaciju strukture podataka u koju se eksplicitno smeštaju podaci koji se inače smeštaju na programski stek. Pošto je programski stek prilično ograničen, ovim se mogu sprečiti neke greške prekoračenja steka, ali takvi programi i dalje koriste veliku količinu memorije. U mnogim slučajevima, pre svega kada se tokom svakog izvršavanja rekurzivne funkcije izvrši najviše jedan rekurzivni poziv, moguće je osloboditi se rekurzije i bez korišćenja steka.

4.9.1 Repna rekurzija

Naročito je zanimljiv slučaj repne rekurzije, jer se u tom slučaju rekurzija može jednostavno eliminisati na veoma sistematičan način⁷. Rekurzivni poziv je repno rekurzivni ukoliko je vrednost rekurzivnog poziva upravo i konačan rezultat funkcije, tj. nakon rekurzivnog poziva ne izvršava se nikakva dodatna naredba (uključujući ni bilo kakva ispisivanja). Na primer, u funkciji stepen_brzo, poziv return stepen_brzo(x * x, n / 2); jeste, dok poziv return x * stepen_brzo(x, n - 1); nije repno rekurzivan (zato što je po izlasku iz rekurzije neophodno još pomnožiti rezultat sa \(x\)). Za rekurzivnu funkciju kažemo da je repno-rekurzivna ako joj je svaki rekurzivni poziv repni.

Pošto nakon povratka iz repnog rekurzivnog poziva neće biti više potrebni podaci koji se nalaze u tekućem stek okviru, nema potrebe za rekurzivni poziv alocirati novi stek okvir, već rekurzivni poziv može za sve podatke koristiti tekući stek okvir. Na taj način se celokupno izvršavanje repno-rekurzivne funkcije realizuje korišćenjem samo jednog stek okvira. Mnogi kompilatori automatski vrše ovu optimizaciju, a može je izvršiti i programer samostalno, tako što će rekurziju zameniti je petljom u kojoj će se na mestu rekurzivnog poziva, na kraju tekuće iteracije, ažurirati vrednosti promenljivih koje odgovaraju ulaznim parametrima funkcije. Razmotrimo sledeći primer, gde su p, a, b i f proizvoljne funkcije.

void r(int x) {
  if (p(x))
    a(x);
  else {
    b(x);
    r(f(x));
  }
}

Ključni korak je da se pre rekurzivnog koraka vrednosti parametara funkcije (u ovom slučaju parametra x) postave na vrednosti parametara rekurzivnog poziva, a zatim da se kontrola toka izvršavanja nekako prebaci na početak funkcije. Ovo je najjednostavnije (ali ne previše elegantno) uraditi korišćenjem bezuslovnog skoka.

void r(int x) {
pocetak:
  if (p(x))
    a(x);
  else {
    b(x);
    x = f(x); 
    goto pocetak;
  }
}

Daljom analizom moguće je ukloniti bezuslovni skok i dobiti sledeći iterativni kôd.

void r(int x) {
  while (!p(x)) {
    b(x);
    x = f(x);
  }
  a(x);
}

unsigned nzd(unsigned a, unsigned b) {
  if (b == 0)
    return a;
  else
    return nzd(b, a % b);
}

unsigned nzd(unsigned a, unsigned b) {
pocetak:
  if (b == 0)
    return a;
  else {
    unsigned tmp = a % b; a = b; b = tmp;
    goto pocetak;
  }
}

unsigned nzd(unsigned a, unsigned b) {
  while (b != 0) {
    unsigned tmp = a % b; a = b; b = tmp;
  }
  return a;
}

S obzirom na svojstva repne rekurzije, ponekad deluje poželjno rekurzivne funkcije formulisati tako da koriste isključivo repnu rekurziju.

int faktorijel(int n, int acc = 1) {
   if (n == 0) return acc;
   return faktorijel(n-1, acc * n);
}

unsigned fib(unsigned n, unsigned fp, unsigned fpp) {
  if (n == 0)
    return fpp;
  return fib(n-1, fp+fpp, fp);
}

unsigned fib(unsigned n) {
  return fib(n, 1, 0);
}

unsigned fbb(unsigned n) {
  unsigned fp = 1, fpp = 0;
  while (n > 0) {
    int f = fp + fpp;
    fpp = fp; fp = f;
    n--;
  }
  return fpp;
}

Tokom izvršavanja repno-rekurzivnih funkcija parametri se postepeno menjaju od nekih početnih vrednosti (u primeru Fibonačijevih brojeva to su vrednosti \(F_0 = 0\) i \(F_1 = 1\)) pa sve do krajnjih, traženih vrednosti (u primeru Fibonačijevih brojeva to su vrednosti \(F_{n}\) i \(F_{n+1}\)). Takva izmena promenljivih suštinski je iterativna (promenljive se na potpuno isti način menjaju i u iterativnoj verziji, sa petljama) i odgovarajuće repno-rekurzivne funkcije često se nazivaju iterativne funkcije. Pošto je imperativnim jezicima, kakvi su C i C++, takva promena promenljivih karakteristična je za petlje, u njima retko kada pišu repno-rekurzivne funkcije (kada programer osmisli rešenje u kojem se promenljive menjaju na opisani način, on po običaju takvo rešenje odmah formuliše u vidu petlji).

I rekurzija koja nije repno-rekurzivna često se može ukloniti i zameniti jednostavnom iteracijom, ali to nije jednostavno uraditi na sistematičan način, kao u slučaju repne rekuzije.

string grej(int n, int k) {
   string kod = "";
   while (n > 0) {
       if (k < (1ul << (n - 1))) {
          kod += "0";
       } else {
          kod += "1";
          k = (1ul << n) - 1 - k;
       }
       n--;
   }
   return kod;
}

4.9.2 Oslobađanje od rekurzije korišćenje pogodnih struktura podataka

Za mnoge probleme rekurzivno rešenje može biti veoma elegantno ali može biti i zahtevno u smislu potrebnog vremena ili prostora za izvršavanje. Čak i ako rekurzivna funkcija zahteva mali stek okvir, ukoliko ima mnogo rekurzivnih poziva može doći do prepunjavanja steka i prekida izvršavanja programa. Broj rekurzivnih poziva koji može dovesti do prekida izvršavanja programa zavisi od mnogo faktora, ali obično je reda nekoliko desetina hiljada pre nego nekoliko miliona. U situacijama kada je moguće da broj rekurzivnih poziva bude veliki poželjno je rekurzivno rešenje zameniti nerekurzivnim. Kao što je pokazano, u nekim situacijama (za neke forme rekurzije kao što je repna rekurzija) dovoljna je relativno jednostavna transformacija programa. U nekim situacija, međutim, potrebne promene mogu iziskivati potpunu promenu logiku programa i oslanjanje na dodatne pogodne strukture podataka.

void floodFill(int slika[MAX_DIM][MAX_DIM], int m, int n,
               int x, int y) {
  stack<pair<int,int>> s;
  s.push(make_pair(x,y));

  while (!s.empty()) {
    pair<int,int> p = s.top(); 
    s.pop();
    for (int i = 0; i < 4; i++) {
      int x = p.first + smer[i][0];
      int y = p.second + smer[i][1];
      if (0 <= x && x < m && 0 <= y && y < n && !slika[x][y]) {
        s.push(make_pair(x,y));
        slika[x][y] = 1;
      }
    }
  }
}

4.10 Ojačavanje induktivne hipoteze

Prilikom primene induktivno-rekurzivne konstrukcije ponekada se ispostavlja da samo rešenje potproblema manje dimenzije nije dovoljno da bi se rekonstruisalo rešenje polaznog problema, ali da se prilikom rekurzivnog rešavanja potproblema može uraditi i nešto dodatno (na primer, izračunati neke pomoćne informacije) koje nam onda pomažu da rešimo i polazni problem. Dakle, do rešenja je moguće doći zahvaljujući “kreditu” koji smo dobili iz rekurzivnog poziva, ali ne smemo zaboraviti da vratimo taj “dug” tj. da našem pozivaocu pored traženog rešenja problema uradimo i taj dodatni posao (na primer, vratimo te pomoćne informacije) — iako to nije potrebno u polaznom rekurzivnom pozivu, na svim drugim nivoima rekurzije jeste. Takoće, i baza mora biti proširena tako da obuhvati ovaj dodatni posao. Ova tehnika se naziva ojačanje induktivne hipoteze. U slučaju ojačanja induktivne hipoteze, klasičnu shemu

\[A_0 \wedge ((\forall n)(A_n \Rightarrow A_{n+1})) \Rightarrow (\forall n)(A_n)\]

menjamo shemom

\[(A_0 \wedge B_0) \wedge ((\forall n)(A_n \wedge B_n \Rightarrow A_{n+1} \wedge B_{n+1})) \Rightarrow (\forall n)(A_n \wedge B_n).\]

4.10.1 Uparene zagrade

Opišimo rekurzivni algoritam koji proverava da li su zagrade unutar niske koja sadrži samo otvorene i zatvorene zagrade korektno uparene. Ako pristupimo ovom problemu rekurzivno, nisku prirodno razlažemo na prefiks i poslednji karakter. Zadatak ne možemo rešiti tako što će rekurzivni poziv vratiti samo logičku vrednost koja opisuje da li je prefiks niska koja sadrži korektno uparene zagrade. Naime, ako je poslednji karakter ')', cela niska će biti korektna samo ako je prefiks takav da su sve zagrade korektno uparene osim jedne zagrade koja je samo otvorena, ali nije još zatvorena. Zato je potrebno ojačati induktivnu hipotezu i iz rekurzivnog poziva treba da saznamo i da li su zagrade uparene i koliko je otvorenih zagrada još nezatvoreno.

pair<bool, int> uparene(const string& s, int n) {
   // prazna niska je OK i nema viška otvorenih zagrada
   if (n == 0) return {true, 0};
   // rekurzivno obrađujemo prefiks
   auto [ok, otvoreno] = uparene(s, n-1);
   // ako prefiks nije u redu nije ni cela niska
   if (!ok) return {false, 0};
   // poslednji karakter je (
   if (s[n-1] == '(') return {true, otvoreno+1};
   else {
      // poslednji karakter je )
      // greška ja ako nema viška otvorenih zagrada u prefiksu
      if (otvoreno == 0) return {false, 0};
      else return {true, otvoreno - 1};
   }
}

bool uparene(const string& s) {
   auto [ok, otvoreno] = uparene(s, s.size());
   // na kraju ne sme biti viška otvorenih zagrada
   return ok && otvoreno == 0;
}

Naravno, ovaj program se lako može prevesti u iterativnu verziju (koja je jednostavnija i prirodnija). Njena invarijanta direktno odgovara rekurzivnoj konstrukciji koju smo upravo prikazali i koristi istu ojačanu induktivnu hipotezu (u svakom koraku petlje znamo da je do tada obrađen prefiks ispravan i da promeljiva otvoreno sadrži broj otvorenih zagrada u prefiksu).

bool uparene(const string& s) {
   int otvoreno = 0;
   for (char c : s) {
       if (c == '(')
          otvoreno++;
       else { // c == ')'
          if (otvoreno == 0)
             return false;
          otvoreno--;
       }
   }
   return otvoreno == 0;
}

Ilustrujmo ovu tehniku kroz rešenje nekoliko zadataka u kojima ćemo uglavnom upotrebiti induktivnu konstrukciju sa ojačanom induktivnom hipotezom.

Zadatak: Maksimalni zbir segmenta

Ovaj zadatak je ponovljen u cilju ilustrovanja različitih tehnika rešavanja.

Tekst zadatka.

Rešenje

Kadanov algoritam

Pokušavamo da algoritam zasnujemo na induktivnoj konstrukciji.

• Za prazan niz, jedini segment je prazan i njegov je zbir nula (to je ujedno najveći zbir koji se može dobiti).

• Smatramo da umemo da problem rešimo za proizvoljan niz dužine \(n\) i na osnovu toga pokušavamo da rešimo zadatak za niz dužine \(n+1\) (polazni niz proširen jednim dodatnim elementom).

  Segment najvećeg zbira u proširenom nizu se ili ceo sadrži u polaznom nizu dužine \(n\) ili čini sufiks proširenog niza, tj. završava se na poslednjoj poziciji (uključujući i mogućnost da je tu i prazan segment).

  Na osnovu induktivne hipoteze znamo da izračunamo najveći zbir segmenta niza dužine \(n\) i potrebno je da još odredimo maksimalni zbir sufksa proširenog niza. Jedan način da se to uradi je da prilikom svakog proširenja niza iznova analiziramo sve segmente koji se završavaju na tekućoj poziciji, ali čak iako to radimo inkrementalno (krenuvši od praznog sufiksa, pa dodajući unazad jedan po jedan element) najviše što možemo dobiti je algoritam kvadratne složenosti. Ključni uvid je to da najveći zbir sufiksa koji se završava na tekućoj poziciji možemo inkrementalno izračunati znajući najveći zbir sufiksa niza pre proširenja. Najveći zbir nekog nepraznog sufiksa koji se završava na tekućoj poziciji je zbir tekućeg elementa niza i najvećeg zbira nekog sufiksa koji se završava na prethodnoj poziciji. Od njega može biti povoljniji samo prazan sufiks (i to samo ako je prethodni zbir negativan).

Dakle, ojačaćemo induktivnu hipotezu i pretpostaviti da umemo da izračunamo i maksimalni zbir \(M_i\) nekog segmenta prvih \(i\) elemenata niza i maksimalni zbir \(S_i\) nekog sufiksa prvih \(i\) elemenata niza. Važi da je \(M_0 = S_0 = 0\), da je \(S_{i+1} = \max{(S_i+a_i, 0)}\) i \(M_{i+1} = \max{(M_i, S_{i+1})}\).

Implementaciju možemo napraviti iterativnim algoritmom kome je invarijanta da u svakom koraku petlje znamo ove dve vrednosti (maksimum segmenta i maksimum sufiksa). Ovaj algoritam je poznat pod nazivom Kadanov algoritam.

Pošto elemente učitavamo jedan po jedan i ne pamtimo ih istovremeno, memorijska složenost je \(O(1)\). Maksimalni zbir segmenta i sufiksa inkrementalno izračunavamo jednim prolaskom kroz zadate elemente i vremenska složenost je linearna tj. \(O(n)\).

Naglasimo da svaki algoritam u kom se tokom iteracije pamti više različitih statistika do tada obrađenog dela niza zapravo koristi ojačanu induktivnu hipotezu (na primer i rešenje ovog zadatka u kom se pamtila vrednost maksimalnog segmenta, zbira prefiksa i minimalnog zbira prefiksa takođe koristi ojačanu induktivnu hipotezu).

int maxSufiks = 0, maxSegment = maxSufiks;
for (int i = 0; i < n; i++) {
  int x;
  cin >> x;
  maxSufiks += x;
  if (maxSufiks < 0)
    maxSufiks = 0;
  if (maxSufiks > maxSegment)
    maxSegment = maxSufiks;
}  
cout << maxSegment << endl;

#include <iostream>

using namespace std;

int main() {
  ios_base::sync_with_stdio(false);
  int n;
  cin >> n;

  int maxSufiks = 0, maxSegment = maxSufiks;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    maxSufiks += x;
    if (maxSufiks < 0)
      maxSufiks = 0;
    if (maxSufiks > maxSegment)
      maxSegment = maxSufiks;
  }  
  cout << maxSegment << endl;
  
  return 0;
}

Zadatak: Maksimalni zbir nesusednih elemenata niza

Napiši program koji određuje najveći zbir podniza datog niza celih brojeva koji ne sadrži dva uzastopna člana niza.

Opis ulaza

Sa standardnog ulaza se unosi broj članova niza \(n\) (\(1 \leq n \leq 10^5\)), a zatim iz narednog reda članovi niza razdvojeni razmacima.

Opis izlaza

Na standardni izlaz ispisati traženi maksimalni zbir.

Primer 1

Ulaz

6
7 3 2 4 1 5

Izlaz

16

Objašnjenje

Maksimalni zbir je zbir segmenta \(7+4+5=16\).

Primer 2

Ulaz

12
3 -2 4 5 -1 3 -4 -5 4 5 2 -1

Izlaz

17

Rešenje

Zadatak možemo jednostavno rešiti induktivno-rekurzivnom konstrukcijom. Niz možemo razložiti na poslednji element i prefiks pre njega. Da bismo odredili maksimalni zbir nesusednih elemenata niza, analiziraćemo slučaj kada je poslednji element niza deo tog maksimalnog zbira i kada nije (to su jedine dve mogućnosti i jedna od njih je sigurno tačna). Zato je maksimalni zbir nesusednih elemenata niza maksimum sledeća dva zbira:

• prvog, koji se dobija tako što se poslednji element doda na maksimalni zbir nesusednih elemenata prefiksa, pri čemu u tom zbiru ne uključuje pretposlednji element niza (tj. poslednji element prefiksa) i

• drugog, koji se dobija kao maksimalni zbir nesusednih elemenata prefiksa koji može da uključi i pretposlednji element niza (tj. poslednji element prefiksa).

Dakle, osim što pretpostavljamo da umemo da rešimo problem manje dimenzije tj. da za prefiks umemo da odredimo maksimalni zbir nesusednih elemenata, potrebno je da ojačamo induktivnu hipotezu i da za prefiks umemo da odredimo i maksimalni zbir nesusednih elemenata tog prefiksa ako poslednji element prefiksa nije uključen u taj zbir. Naravno, kao i uvek kada se ojačava induktivna hipoteza, “dug” se mora vratiti pa za prefiks proširen dodatnim elementom pored maksimalnog zbira nesusednih elemenata, moramo da umemo da odredimo i maksimalni zbir nesusednih elemenata kada poslednji element nije uključen. Međutim, to nije teško, jer je to upravo maksimalni zbir nesusednih elemenata prefiksa. Maksimalni zbir proširenog niza (bez obzira na to da li uključuje ili ne uključuje poslednji element) određujemo kao maksimum dva opisana zbira (koja na osnovu induktivne hipoteze lako izračunavamo).

Baza je slučaj praznog niza. Maksimalni zbir njegovih nesusednih elemenata u svakoj varijanti jednak je nuli.

Obeležimo sa \(m_k\) maksimalni zbir nesusednih elemenata prvih \(k\) elemenata datog niza. Cilj je da odredimo \(m_n\). Neka je \(m'_k\) maksimali zbir nesusednih elemenata prvih \(k\) elemenata niza u koji nije uključen element \(a_{k-1}\). Važe sledeće rekurentne relacije: \(m_0 = m'_0 = 0\), dok za \(k > 0\), važi \(m'_k = m_{k-1}\) i \(m_k = \max(a_{k-1} + m'_{k-1}, m_{k-1})\).

Složenost ovog algoritma je \(O(n)\).

int maks_zbir_bez = 0;
int maks_zbir = 0;
for (int i = 0; i < n; i++) {
  int x;
  cin >> x;
  int maks_zbir_sa = maks_zbir_bez + x;
  maks_zbir_bez = maks_zbir;
  maks_zbir = max(maks_zbir_bez, maks_zbir_sa);
}
cout << maks_zbir << endl;

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  int maks_zbir_bez = 0;
  int maks_zbir = 0;
  for (int i = 0; i < n; i++) {
    int x;
    cin >> x;
    int maks_zbir_sa = maks_zbir_bez + x;
    maks_zbir_bez = maks_zbir;
    maks_zbir = max(maks_zbir_bez, maks_zbir_sa);
  }
  cout << maks_zbir << endl;
  return 0;
}

Još jedna induktivno-rekurzivna konstrukcija kojom se problem može rešiti podrazumeva da se za svaki prefiks niza odredi maksimalni zbir nesusednih elemenata kada je poslednji element prefiksa uključen i maksimalni zbir nesusednih elemenata kada poslednji element prefiksa nije uključen.

Obeležimo sa \(m^{sa}_k\) maksimalni zbir nesusednih elemenata prvih \(k\) elemenata niza, koji sadrži i element \(a_{k-1}\) i sa \(m^{bez}_k\) maksimalni zbir nesusednih elemenata prvih \(k\) elemenata niza, koji ne sadrži element \(a_{k-1}\). Baza indukcije može biti jednočlan niz i važi \(m^{sa}_1 = a_0\), \(m^{bez}_1 = 0\). Za svaku vrednost \(k > 1\), važi \(m^{sa}_k = a_{k-1} + m^{bez}_{k-1}\) i \(m^{bez}_k = \max(m^{sa}_{k-1}, m^{bez}_{k-1})\). Tražena vrednost jednaka je \(\max(m^{sa}_n, m^{bez}_n)\).

Složenost ovog algoritma je \(O(n)\).

// prvi element se ucitava van petlje zbog inicijalizacije
// to je ujedno i baza indukcije, jednoclani prefiks niza
int x;
cin >> x;
int maks_zbir_bez = 0;
int maks_zbir_sa = x;

// u petlji obradjujemo tekuci element
for (int i = 1; i < n; i++) {
  int x;
  cin >> x;
  int maks_zbir = max(maks_zbir_sa, maks_zbir_bez);
  maks_zbir_sa = maks_zbir_bez + x;
  maks_zbir_bez = maks_zbir;
}
   
cout << max(maks_zbir_bez, maks_zbir_sa) << endl;

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
  int n;
  cin >> n;

  // prvi element se ucitava van petlje zbog inicijalizacije
  // to je ujedno i baza indukcije, jednoclani prefiks niza
  int x;
  cin >> x;
  int maks_zbir_bez = 0;
  int maks_zbir_sa = x;

  // u petlji obradjujemo tekuci element
  for (int i = 1; i < n; i++) {
    int x;
    cin >> x;
    int maks_zbir = max(maks_zbir_sa, maks_zbir_bez);
    maks_zbir_sa = maks_zbir_bez + x;
    maks_zbir_bez = maks_zbir;
  }
   
  cout << max(maks_zbir_bez, maks_zbir_sa) << endl;
   
  return 0;
}

Induktivno-rekurzivna konstrukcija može teći i na sledeći način. Pretpostavljamo da umemo da izračunamo maksimalni zbir nesusednih elemenata svakog prefiksa niza. Ako je prefiks prazan, maksimalni zbir nesusednih elemenata je nula, a ako je jednočlan, tada je jednak većem od broja nula i prvog elementa niza. Ako je prefiks bar dvočlan onda je maksimalni zbir nesusednih elemenata tog prefiksa maksimum maksimalnog zbira prefiksa bez poslednjeg elementa i zbira poslednjeg elementa i maksimalnog zbira bez poslednja dva elementa.

Dakle, dobijamo da je \(m_0 = 0\), \(m_1 = \max(a_0, 0)\) i \(m_i = \max(m_{i-1}, a_{i-1} + m_{i-2})\).

Ova rekurzivna konstrukcija se može isprogramirati rekurzivnom funkcijom. Nažalost, to rešenje je prilično neefikasno.

Složenost ovog rešenja zadovoljava jednačinu \(T(n) = T(n-1) + T(n-2) + O(1)\), \(T(1) = T(0) = 1\), čije je rešenje eksponencijalna funkcija (ista jednačina se javlja i prilikom direktne rekurzivne implementacije izračunavanja elemenata Fibonačijevog niza).

int maksZbir(const vector<int>& a, int n) {
  if (n == 0)
    return 0;
  if (n == 1)
    return max(a[0], 0);
  return max(maksZbir(a, n-1), a[n-1] + maksZbir(a, n-2));
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int maksZbir(const vector<int>& a, int n) {
  if (n == 0)
    return 0;
  if (n == 1)
    return max(a[0], 0);
  return max(maksZbir(a, n-1), a[n-1] + maksZbir(a, n-2));
}

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for (int i = 0; i < n; i++)
    cin >> a[i];
  cout << maksZbir(a, n) << endl;
  return 0;
}

Rekurziju možemo ukloniti i dobiti narednu iterativnu implementaciju.

Složenost ovog algoritma je \(O(n)\).

int maks_zbir_p = 0;
int x;
cin >> x;
int maks_zbir = max(0, x);
for (int i = 2; i <= n; i++) {
  int x;
  cin >> x;
  int tmp = max(maks_zbir, maks_zbir_p + x);
  maks_zbir_p = maks_zbir;
  maks_zbir = tmp;
}
cout << maks_zbir << endl;

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  int maks_zbir_p = 0;
  int x;
  cin >> x;
  int maks_zbir = max(0, x);
  for (int i = 2; i <= n; i++) {
    int x;
    cin >> x;
    int tmp = max(maks_zbir, maks_zbir_p + x);
    maks_zbir_p = maks_zbir;
    maks_zbir = tmp;
  }
  cout << maks_zbir << endl;
  return 0;
}

Sistematičan način oslobađanja neefikasnosti prouzrokovane rekurzijom ovog tipa dolazi u obliku tehnika dinamičkog programiranja, koje je opisano u zasebnom poglavlju.

Poglavlja

• Dodatak: induktivno-rekurzivna konstrukcija