4 Индуктивна и рекурзивна конструкција алгоритама

У поглављу 1.4.2 је већ дискутовано да у основни већине рачунарских алгоритама крије се идеја да се проблеми решавају тако што се претходно реше потпроблеми истог облика, али мање димензије. Ово је у веома тесној вези са принципом математичке индукције са једне и принципом рекурзије са друге стране.

4.1 Математичка индукција

Математичка индукција, у свом основном облику, је следећи начин доказивања особина природних бројева. Нека је \(P\) произвољно својство које се може формулисати за природне бројеве1. Тада важи

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

Индукција је тесно повезана са скупом природних бројева, јер је тај скуп дефинисан индуктивно, као најмањи скуп који задовољава наредна индуктивна правила:

база:
нула је природан број;
корак:
следбеник сваког природног броја је природан број.

На сличан начин, могуће је индуктивно представити и друге скупове (тј. типове података).

Ниску (карактера) могуће је дефинисати на следећи начин: (база) празна ниска представља ниску и (корак) додавањем карактера на крај неке ниске добија се ниска.

Слично томе, декадни запис природног је или (база) запис декадне цифре или (корак) запис природног броја на који је надовезан запис декадне цифре са десне стране.

И аритметички изрази (термови) се могу дефинисати индуктивно.

база:
прости изрази (константе и променљиве) су изрази;
корак:
сложенији изрази се добијају од једноставнијих применом аритметичких оператора (+, *, \(\ldots\)) или заграда.

И неке релације могу бити дефинисане индуктивно. На пример, релација предак може се дефинисати на следећи начин:

база:
родитељ особе је предак те особе;
корак:
родитељ било ког претка неке особе такође је предак те особе.

Релација предак је онда најмања релација (у смислу инклузије) која задовољава овако задата правила (предак није ниједна особа за коју се применом ових правила не може извести да је предак).

Индукција, дакле, није само метод за доказивање теорема над природним бројевима, већ општији принцип који нам даје могућност да од једноставнијих објеката изградимо сложеније, кренувши од неких базних и примењујући задата правила проширења.

4.2 Рекурзија

Рекурзија је веома сродан (али супротно усмерен) приступ математичкој индукцији, у којем се нека функција дефинише на основу једног или више базних случајева и на основу правила која сложене случајеве своде на једноставније. Већина савремених програмских језика допушта дефинисање рекурзивних функција – функција може да позове саму себе, при чему корисник треба да буде сигуран да ће се тај ланац рекурзивних позива у неком тренутку зауставити (обично тако што ће сваки наредни рекурзивни позив бити за мању вредност параметра).

Пример 4.2.1. Вредност факторијела \(n!\) се може описати следећом рекурзивном дефиницијом:

\[\begin{eqnarray*} n! = \begin{cases} 1, & n = 0 \\[6pt] n \cdot (n - 1)!, & n > 0 \end{cases} \end{eqnarray*}\]

Вредност \(4!\) се може израчунати применом ових правила као \(4! = 4\cdot 3! = 4\cdot 3 \cdot 2! = 4\cdot 3 \cdot 2 \cdot 1! = 4\cdot 3 \cdot 2 \cdot 1 \cdot 0! = 4\cdot 3 \cdot 2\cdot 1 \cdot 1 = 24\).

Имплементација у језику C++ директно прати дефиницију.

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

Изостанак било базног корака (који обезбеђује “заустављање” примене дефиниције) било рекурзивног корака чини дефиницију непотпуном2.

4.3 Однос индукције и рекурзије

Индукцијом се од једноставнијих објеката добијају сложенији, док се рекурзијом израчунавање сложенијих објекта своди на израчунавање једноставнијих. На пример, у индуктивној дефиницији природних бројева користила се чињеница да је следбеник природног броја природан број, а у рекурзивној дефиницији смо израчунавање вредности факторијела свели на израчунавање вредности факторијела претходника.

Због јаке повезаности индукције и рекурзије говори се и о индуктивно/рекурзивној конструкцији алгоритама, која подразумева да се решење проблема веће димензије проналази коришћењем решења проблема истог облика, али мање димензије. Притом за почетне димензије проблема решење је потребно израчунати директно, без свођења на мање потпроблеме. Ако се приликом свођења димензија проблема увек смањује, конструисани алгоритми ће се увек заустављати.

4.4 Примитивна и општа рекурзија

Принцип доказивања математичком индукцијом је у вези са индуктивном дефиницијом скупа природних бројева – то је најмањи скуп који садржи нулу и затворен је за операцију следбеника. Стога је алгоритме за рад са природним бројевима могуће дефинисати тако да у случају изласка из рекурзије разрешавају случај нуле, док у случају неког броја већег од нуле (следбеника неког броја) рекурзивно своде проблем на случај његовог претходника. Овакав тип рекурзије, који директно одговара индуктивној дефиницији типа података, назива се примитивна рекурзија.

Када у обзир узмемо индуктивну дефиницију декадног записа природног броја (у којој базу чине једноцифрени бројеви, а вишецифрени бројеви се добијају дописивањем цифре здесна на већ постојећи декадни запис), лако можемо дефинисати примитивно рекурзивне функције такве да излаз из рекурзије представљају једноцифрени бројеви, док се случај вишецифреног броја разрешава свођењем на број са одсеченом последњом цифром. Ако је број \(n\) представљен податком целобројног типа, последњу цифру можемо одредити изразом n%10, а можемо је уклонити изразом n/10.

Пример 4.4.1. Збир цифара броја \(n\) може се израчунати на следећи начин.

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

Ако функцију скраћено обележимо са \(z\), важи \(z(123) = z(12) + 3 = z(1) + 2 + 3 = 1 + 2 + 3 = 6\).

Дуални приступ – разлагање броја на прву цифру и на остале цифре – у овом случају није погодан, због тога што овакво разлагање није могуће спровести једноставним математичким операцијама.

Функције које обрађују ниске се такође могу дефинисати рекурзивно, тако да при изласку из рекурзије обрађују случај празне ниске, док случај непразне ниске дужине \(n\) решавају тако што рекурзивно разреше њен префикс дужине \(n-1\) и онда резултат искомбинују са последњим елементом ниске.

Пример 4.4.2. Наредна рекурзивна функција броји размаке (бланко карактере) у датој ниски.

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());
}

Као што је често обичај, дефинисали смо и тзв. омотач функцију (енгл. wrapper function) чији је једини циљ да исправно иницијализује аргументе почетног рекузивног позива и тако олакша крајњем кориснику употребу рекурзивно дефинисане функције (корисник не мора ни да зна шта је параметар који се прослеђује и мења током рекурзивних позива).

Ако функцију скраћено означимо са \(B\), израчунавање за ниску "ab c d" суштински тече на следећи начин:

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

Да се ниска не би мењала током рекурзивних позива (што би било веома неефикасно), у имплементацији се прослеђује параметар n, који се током рекурзивних позива смањује (на пример, уместо позива B("ab") ефективно се врши позив B("ab c d", 2)).

Дуално разлагање на први елемент и суфикс ниске такође је могуће, при чему је онда приликом сваког рекурзивног позива потребно, поред дужине ниске, прослеђивати и позицију почетка суфикса.

У неким случајевима, потребно је користити и напредније облике индукције, каква је, на пример, тотална индукција. У том случају, након доказивања индуктивне базе, у оквиру индуктивног корака могуће је претпоставити тврђење за све бројеве мање од \(n\) и из те претпоставке доказати тврђење за број \(n\). Слично, поред примитивно рекурзивних функција, постоје и функције које су генерално (опште) рекурзивне. Тако је, на пример, приликом разматрања неког броја \(n\), дозвољено извршити рекурзивни позив за било који број мањи од њега (па чак и више рекурзивних позива за различите природне бројеве мање од њега).

На пример, дефиниција брзог степеновања, описана у глави 1, своди вредност \(n\) (за парно \(n\)) на вредност \(n/2\), уместо на \(n-1\), па је у питању примена генералне рекурзије. И приликом имплементације алгоритма који ради са неким низом, дозвољено је вршити рекурзивне позиве за све поднизове полазног низа краће од њега. Рекурзивна обрада две половине низа често води бољој ефикасности него примитивно-рекурзивна обрада подниза добијеног избацивањем последњег (или првог) елемента низа.

Приликом употребе тоталне рекурзије, допуштено је да се у склопу једног позива функције изврши и више рекурзивних позива. Такође, понекад базни случај мора да покрива више од једне вредности. Један пример такве функције је функција која израчунава елементе Фибоначијевог низа, описана у поглављу 4.6.1.

4.5 Реализација рекурзије

Рекурзија се реализује у складу са општим механизмом извршавања функција: за сваки рекурзивни позив ствара се нови стек оквир и у њему се чувају информације потребне за извршавање функције али и за наставак извршавања програма. Оно што одликује рекурзивне позиве је то да за једну исту функцију на програмском стеку може постојати више стек оквира, обично за различите вредности аргумената функције. Међутим, у меморији рачунара постоји увек само једна копија кôда функције (која се налази у сегменту кода). Наиме, за различите инстанце исте функције (тј. за све активне позиве функције) потребно је памтити докле је стало њихово извшавање али није потребно имати независне копије кôда функције.

Пример 4.5.1. Размотримо поново функцију која рачуна факторијел броја:

int faktorijel(int n) {
  if (n == 0) return 1;
  else return n * faktorijel(n-1);
}
Слика 8: Стек оквири приликом позива faktorijel(3)

Претпоставимо да је из функције main позвана функција faktorijel са аргументом \(3\). Тада се на програмском стеку налазе два стек оквира, један за функцију main, а један за функцију faktorijel са аргументом \(3\) (слика 8, прва слика с levа). Стек оквир за faktorijel чува и место у кôду (адресу инструкције у коду функције main) на које се треба вратити када се заврши извршавање функције faktorijel. Током извршавања функције faktorijel, утврди се да \(n\) није једнако \(0\), те се прелази на другу грану гранања, позива се функција faktorijel за \(n=2\) и ствара стек оквир за ту инстанцу функције faktorijel, где ће бити запамћено, између осталог, и где треба наставити извршавање функције за аргумент \(3\) (слика 8, друга слика с levа). Аналогно се позива функција faktorijel за аргумент \(1\) и за аргумент \(0\).

Када се изврши функција faktorijel за аргумент \(0\), њен резултат (вредност \(1\)) ће бити познат и враћен позиваоцу (најчешће тако што се упише у за то намењен регистар), биће обрисан стек оквир за позив функције faktorijel за вредност \(0\) и биће настављено извршавање faktorijel за аргумент \(1\) (од места које је било сачувано у стек оквиру за \(0\)). Она ће затим помножити ту повратну вредност \(1\) са вредношћу своје променљиве \(n\) (такође \(1\)) и резултат \(1\) ће вратити свом позиваоцу (што је позив faktorijel за \(n=2\)). Аналогно ће бити завршено и извршавање преостале инстанце функције faktorijel и резултат \(6\) инстанце за \(n=3\) биће враћен функцији main (најчешће преко регистра). Пре него што буде ослобођен стек оквир за faktorijel за \(n=3\) из њега ће бити прочитано од које инструкције треба да се настави извршавање функције main.

4.6 Примери рекурзивних функција

Прикажимо у наставку још неколико примера рекурзивних функција.

4.6.1 Фибоначијев низ

Један од примера који се често користи ради илустрације добрих и лоших страна рекурзије је Фибоначијев низ (0,1,1,2,3,5,8,13,…) у којем важи да је сваки наредни члан једнак збиру претходна два.3 Он се може дефинисати у виду (опште) рекурзивне функције \(\mathit{fib}\) (приметимо да базни случај покрива две вредности (\(0\) и \(1\)), а да рекурзивни корак користе две претходне вредности низа):

базни случај
\(\mathit{fib}(0) = 0\) и \(\mathit{fib}(1) = 1\) (тј. за \(n = 0\) важи \(\mathit{fib}(n) = 0\) и за \(n = 1\) важи \(\mathit{fib}(n) = 1\))
рекурзивни корак
за \(n > 1\) важи: \(\mathit{fib}(n) = \mathit{fib}(n - 1) + \mathit{fib}(n - 2)\)

Функција за израчунавање \(n\)-тог елемента Фибоначијевог низа може се дефинисати на следећи начин:

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

Овај приступ генерисању Фибоначијевих бројева, иако веома једноставан за имплементацију, веома је неефикасан и биће дискутовани могући правци побољшања. Приметимо да се за разлику од свих до сада приказаних рекурзивних функција, у склопу једног позива функције врше два рекурзивна позива. Ово само по себи не мора бити проблематично, међутим, у овом конкретном случају се дешава да се рекурзивни позиви понављају за исте вредности параметара, што је један од основних проблема наивних рекурзивних имплементација и што доводи до огромне неефикасности.

Заиста, нека \(T(n)\) означава број инструкција које захтева позив функције fib за улазну вредност \(n\). За \(n \leq 1\) важи \(T(n)=c_1\), где је \(c_1\) нека константа. За \(n>1\), важи \(T(n)=T(n-1)+T(n-2)+c_2\), где је \(c_2\) нека константа. Из \(T(n)=T(n-1)+T(n-2)+c_2\) и \(T(n+1)=T(n)+T(n-1)+c_2\), следи \(T(n+1)=2T(n)-T(n-2)\). Карактеристична једначина ове једначине је \(t^3=2t^2-1\) и њени корени су \(1\), \(\frac{1+\sqrt{5}}{2}\) и \(\frac{1-\sqrt{5}}{2}\), па је опште решење облика \(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,\) одакле следи \(T(n)=O(\left(\frac{1+\sqrt{5}}{2}\right)^n)\).

Пример 4.6.1. Функције сличног типа често се добијају када се техника рекурзије примени на решавање неких проблема пребројавања. Као илустрацију рекурзивног приступа решавању проблема, размотримо број начина да се правоугаона табла димензије \(2 \times k\) поплоча плочицама димензије \(1 \times 2\) и \(2 \times 1\). Сва поплочавања табле димензије \(2 \times 4\) приказана су на наредној слици (има их 5).

Покривање табле димензије \(4\times 2\) плочицама димензије \(2\times 1\) и \(1 \times 2\)

Прво поље на табли (поље у горњем левом углу) мора бити прекривено домином. Она мора бити постављена или вертикално или хоризонтално.

Излаз из рекурзије представља табла димензије \(2 \times 0\), која се може поплочати само на један начин (без домина) и табла димензије \(2 \times 1\), која се такође може поплочати само на један начин (једном вертикалном домином). Ако \(F(k)\) означава број поплочавања табле \(2\times k\), важи да је \(F(0) = F(1) = 1\) и да је \(F(k) = F(k-1) + F(k-2)\), што је управо једначина која дефинише Фибоначијев низ.

4.6.2 Грејови кодови

Бинарни бројеви са \(n\) цифара обично се ређају по величини (на пример, 000, 001, 010, 011, 100, 101, 110, 111). Алтернативно, Грејов кôд4 подразумева да се бинарни бројеви ређају тако да се свака два суседна броја разликују тачно на једном биту (при чему то својство важи и за последњи и први број у низу). Троцифрени Грејов кôд може бити 000, 001, 011, 010, 110, 111, 101, 100. Ово није једини троцифрени Грејов кôд, али се он ипак најчешће разматра, јер је добијен врло правилним, систематичним поступком. Наиме, прва четири броја почињу са 0, док наредна четири броја почињу са 1. Када се са почетка прва четири броја избрише 0, добија се двоцифрен Грејов кôд 00, 01, 11, 10, док се брисањем 1 са почетка наредна четири броја добија исти тај Грејов кôд, али у обратном поретку. И овај двоцифрени Грејов кôд је добијен на исти начин. Прва два броја почињу са 0, након које се јавља једноцифрени кôд 0, 1, а друга два броја почињу са 1 иза чега се јавља обратан једноцифрени кôд. Чак и за једноцифрени кôд можемо константовати исто. Први број почиње са 0 након које иде Грејов кôд са нула цифара (који је празан), док други број почиње са 1 након које иде исти тај кôд са нула цифара (који је празан) у обратном редоследу.

Дефинишимо рекурзивну функцију која одређује \(k\)-ти по реду број \(n\)-тоцифреног Грејовог кода (он садржи \(2^n\) бројева и подразумеваћемо да је \(0 \leq k < 2^n\)). За \(n=0\) резултат је празна ниска. У супротном, треба израчунати одговарајући елемент Грејовог кода са \(n-1\) цифара и затим га допунити слева нулом или јединицом. Треба разликовати случај елемената у првој и у другој половини Грејовог кода.

Израчунавање степена двојке најједноставније се врши битовским операцијама. Шифтовање броја 1 за \(m\) позиција улево еквивалентно је са \(n\) узастопних множења са 2 и израчунава тачно вредност \(2^m\) (под претпоставком да не дође до прекорачења).

Елементи Грејовог кода могу се једноставно представити у облику ниски карактера. Иако дописивање карактера на почетак ниске може бити неефикасна операција, с обзиром на то да су ниске са којима радимо прилично кратке (најдужа има 32 карактера), о том не морамо да бринемо.

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

Позив функције grej(5, 17) враћа ниску 11001. Заиста, ако обележимо функцију скраћемо са \(G\), важи:

\[\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 Ханојске куле

Проблем кула Ханоја5 гласи овако: дате су три куле и на првој од њих \(n=64\) диска опадајућих величина; задатак је пребацити све дискове са прве на трећу кулу (користећи и другу) али тако да никада ниједан диск не стоји изнад неког мањег.

Куле Ханоја са 8 дискова

За разлику од итеративног, рекурзивно решење овог проблема је прилично једноставно: уколико је \(n=0\), нема дискова који треба да се пребацују; иначе, пребаци (рекурзивно) \(n-1\) дискова са полазног на помоћну кулу (коришћењем долазне куле као помоћне), пребаци највећи диск са полазне на долазну кулу и, коначно, пребаци (рекурзивно) \(n-1\) дискова са помоћне на долазну кулу (коришћењем полазне куле као помоћне). У наставку је имплементација овог решења:

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

Позив наведене функције kule(3,'A','C','B') даје следећи излаз:

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

Израчунајмо број пребацивања дискова \(T(n)\) које описује наведена функција. Важи \(T(0)=0\) и \(T(n)=2T(n-1)+1\). Дакле, једначина која описује овај низ је нехомогена рекурентна једначина првог реда. Из \(T(n)-2T(n-1)=1=T(n-1)-2T(n-2)\) (за \(n>1\)) следи \(T(n)=3T(n-1)-2T(n-2)\). Ова једначина је хомогена једначина другог реда, њена карактеристична једначина је \(t^2=3t-2\) и њени корени су \(2\) и \(1\), па је опште решење \(\alpha \cdot 2^n + \beta \cdot 1^n\). Решавањем система добијеног за \(n=0\) и \(n=1\) следи \(\alpha=1\) и \(\beta=-1\), па је \(T(n)= 2^n - 1.\), што одређује експоненцијалну временску сложеност ове функције.

Размотримо сада и просторну сложеност \(S(n)\) функције kule. Једна инстанца функције kule заузима (на програмском стеку) константан простор \(c\). У оквиру функције kule у једном тренутку може извршавати највише један од два рекурзивна позива. Зато за просторну сложеност важи: \(S(n) = S(n-1) + c\) и \(S(0) = c\) (а не \(S(n) = 2S(n-1) + c\)), одакле се добија да \(S(n)\) припада класи \(O(n)\). На програмском стеку, за улазни аргумент \(n\), може се у једном тренутку наћи највише \(n+1\) стек оквира инстанци функције kule.

4.6.4 Попуњавање контуре на слици

Често постоји потреба да се систематично обиђу и обраде елементи неког скупа који су међусобно повезани. То, на пример, могу бити елементи неке матрице, истобојна поља на некој слици или градови (који су повезани ако између њих постоји директан пут) и слично. Обилазак свих елемената до којих се може стићи од неког почетног елемента често се спроводи рекурзивним алгоритмима.

Програми за обраду слика нуде алат за попуњавање (“fill” алатка). Потребно је изабрати пиксел одређене боје и читава област сличне боје која је ограничена контуром друге боје или рубом слике биће обојена задатом бојом (сматрамо да су пиксели суседни ако имају једну страницу заједничку). Слика @fig:floodfill приказује једну контуру (лево) и резултат попуњавања ако је била изабрана тачка унутар полазне контуре (десно).

Попуњавање контуре на слици

Размотримо поједностављену варијанту проблема: сматрајмо обојени пиксели имају вредност \(1\), а остали имају вредност \(0\). У рекурзивном решењу (то је, такозвано, flood fill решење), креће се од задатог пиксела, он се боји и онда се иста функција позива за четири суседна пиксела. За текући пиксел се проверава да ли је већ обојен или је ван граница слике и та провера омогућава излазак из рекурзије. Слика је представљена дводимензионим низом slika који садржи нуле и јединице. Једноставности ради претпоставићемо да је тај низ статички алоциран, а да су познате димензије \(m\) и \(n\) дела који треба обрадити, као и координате почетног поља \(v\) и \(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); 
}

Ако се функција покрене за наредну матрицу приказану лево и то са позиције x=2, y=2, добија се матрица приказана десно.

00100100  00111100 
01000100  01111100 
01000100  01111100 
00100100  00111100 
00011111  00011111

Функција floodFill има четири рекурзивна позива, те делује да ће лако доћи до експлозије броја поља која се испитују. Међутим, не улази се у рекурзију за пикселе који су већ обрађени и обојени, те је број пиксела који се обрађују реда \(O(mn)\) и толика је и временска сложеност функције floodFill. Стек оквир за функцију floodFill је константе величине, али је питање колико рекурзивних позива може бити активно у једном тренутку, тј. колико највише може бити стек оквира на програмском стеку. Тај број је, наравно, ограничен одозго вредношћу \(мн\), а слика @fig:floodfill2 илуструје један тип ситуација у којма је број стек оквира реда \(\Theta(mn)\):

Слика на којој је рекурзије веома дубока

У поглављу 4.9.2 биће приказано решење овог проблема без коришћења рекурзије.

4.7 Узајамна рекурзија

У досадашњим примерима, рекурзивне функције су позивале саме себе директно. Постоји и могућност да се функције међусобно позивају и тако стварају узајамну рекурзију. Пожељно је да компилатор зна дефиницију функције пре сваког њеног позива. Међутим, ако се две функције узајамно позивају, тада то није могуће (јер у било ком редоследу дефинисања пре позива друге функције у склопу прве функције дефиниција те друге функције још није виђена). Пошто је исправно превођење могуће ако се пре позива зна само декларација (прототип функције), решење може бити тако што се пре дефиниција функција наведу њихове декларације (довољно би било навести и једну декларацију, али симетрије ради не смета да се наведу обе).

Узајамна рекурзија је понекад важна техника конструкције алгоритама. Прикажимо то на једном примеру. Многи појмови се дефинишу коришћењем индуктивних дефиниција које посредно зависе једна од друге. Размотримо, на пример, аритметичке изразе који садрже природне бројеве и операторе + и *. Сваки израз је низ сабирака раздвојених оператором + (то укључује и могућност да постоји само један сабирак), сваки сабирак је низ чинилаца раздвојених оператором * (то укључује и могућност да постоји само један чинилац), док је сваки чинилац или цео број или израз у заградама. Дакле, израз смо дефинисали преко сабирака, сабирке преко чинилаца, а чиниоце преко израза.

За обраду израза у рачунарству често се користи техника позната под називом рекурзивни спуст, која се заснива на узајамној рекурзији. Функције које читају аритметички израз и израчунавају његову вредности могу бити дефинисане на следећи начин (коришћењем узајамне рекурзије). Претпоставићемо да функција procitaj_sledeci_simbol чита следећи симбол са улаза (то може бити цифра, оператор, нека заграда или крај улаза) и у променљивој sledeci_simbol бележи о којој врсти симбола се ради, а да приликом читања броја у променљиву vrednost_broja смести и његову бројну вредност. Када се на улазу појави било који симбол који не може бити део израза, враћа се ознака да је препознат крај израза, учитавање се прекида и исписује се вредност до тада учитаног израза. Функција main позива функцију izraz() и исписује вредност унетог израза.

// 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;
}

Програм за улаз (1+2)*(3+45) даје излаз 144, а за улаз (1+2. пријављује грешку.

4.8 Добре и лоше стране рекурзије

Добре стране рекурзије су (обично) читљив и кратак код, једноставан за разумевање, анализу, доказивање коректности и одржавање. Ипак, рекурзивна решења имају и мана.

4.8.1 Цена позива

Приликом сваког рекурзивног позива креира се нови стек оквир и копирају се аргументи функције. Када рекурзивних позива има много, то може бити веома захтевно у смислу меморије (а донекле и у смислу времена). Како је величина стек сегмента и на савременим системима релативно мала,6 рекурзивне функције могу довести до прекорачења програмског стека и прекида рада програма. Зато је у неким ситуацијама пожељно рекурзивно решење заменити итеративним (види поглавље 4.9). Једна општа препорука је да би дубина рекурзије требало да расте знатно спорије од димензије улаза (јер димензија улаза која се може обрадити је релативно мала чак и у случају када дубина рекурзије линеарно зависи од димензије улаза).

4.8.2 Сувишна израчунавања

У неким случајевима приликом разлагања проблема на мање потпроблеме долази до преклапања потпроблема и до вишеструких рекурзивних позива за исте потпроблеме.

Илустрација поновљених израчунавања приликом извршавања рекурзивне funkcije

Размотримо, на пример, извршавање наведене функције која израчунава елементе Фибоначијевог низа за \(n=5\), приказано на слици @fig:fibonaci. Функција fib је три пута позвана за \(n=0\), пет пута за \(n=1\), три пута за \(n=2\) и тако даље. Због овога, извршава се много сувишних израчунавања. Решење овог проблема описано је у поглављу @sec:dinamicko.

Треба водити рачуна о томе да се поновљена израчунавања грешком не уведу тамо где их је веома једноставно избећи. Размотримо наредну рекурзивну имплементацију функције за израчунавање минимума непразног низа.

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

У овој имплементацији се може десити да се у истом позиву два пута рекурзивно позове minimum(a, n-1), што доводи до експоненцијалне сложености. Ово се лако може решити тако што се резултат позива запамти у помоћној променљивој.

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;
}

Алтернативно, можемо употребити и библиотечку функцију min, која проналази минимум два броја.

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

4.9 Ослобађање од рекурзије

Сваку рекурзивну функцију је могуће имплементирати на други начин тако да не користи рекурзију. Општи поступак за такво ослобађање од рекурзије укључује имплементацију структуре података у коју се експлицитно смештају подаци који се иначе смештају на програмски стек. Пошто је програмски стек прилично ограничен, овим се могу спречити неке грешке прекорачења стека, али такви програми и даље користе велику количину меморије. У многим случајевима, пре свега када се током сваког извршавања рекурзивне функције изврши највише један рекурзивни позив, могуће је ослободити се рекурзије и без коришћења стека.

4.9.1 Репна рекурзија

Нарочито је занимљив случај репне рекурзије, јер се у том случају рекурзија може једноставно елиминисати на веома систематичан начин7. Рекурзивни позив је репно рекурзивни уколико је вредност рекурзивног позива управо и коначан резултат функције, тј. након рекурзивног позива не извршава се никаква додатна наредба (укључујући ни било каква исписивања). На пример, у функцији stepen_brzo, позив return stepen_brzo(x * x, n / 2); јесте, док позив return x * stepen_brzo(x, n - 1); није репно рекурзиван (зато што је по изласку из рекурзије неопходно још помножити резултат са \(x\)). За рекурзивну функцију кажемо да је репно-рекурзивна ако јој је сваки рекурзивни позив репни.

Пошто након повратка из репног рекурзивног позива неће бити више потребни подаци који се налазе у текућем стек оквиру, нема потребе за рекурзивни позив алоцирати нови стек оквир, већ рекурзивни позив може за све податке користити текући стек оквир. На тај начин се целокупно извршавање репно-рекурзивне функције реализује коришћењем само једног стек оквира. Многи компилатори аутоматски врше ову оптимизацију, а може је извршити и програмер самостално, тако што ће рекурзију заменити је петљом у којој ће се на месту рекурзивног позива, на крају текуће итерације, ажурирати вредности променљивих које одговарају улазним параметрима функције. Размотримо следећи пример, где су p, a, b и f произвољне функције.

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

Кључни корак је да се пре рекурзивног корака вредности параметара функције (у овом случају параметра x) поставе на вредности параметара рекурзивног позива, а затим да се контрола тока извршавања некако пребаци на почетак функције. Ово је најједноставније (али не превише елегантно) урадити коришћењем безусловног скока.

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

Даљом анализом могуће је уклонити безусловни скок и добити следећи итеративни кôд.

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

Пример 4.9.1. Демонстрирајмо технику уклањања репне рекурзије и на примеру Еуклидовог алгоритма.

unsigned nzd(unsigned a, unsigned b) {
  if (b == 0)
    return a;
  else
    return nzd(b, a % 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;
  }
}

Даљом анализом, једноставно се уклања наредба goto и добија идентичан кôд оном који смо раније приказали.

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

С обзиром на својства репне рекурзије, понекад делује пожељно рекурзивне функције формулисати тако да користе искључиво репну рекурзију.

Пример 4.9.2. Наредна репно-рекурзивна функција израчунава \(n!\) и лако се преводи у итеративну имплементацију. Променљива acc мало по мало акумулира вредност производа.

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

Пример 4.9.3. Имплементирајмо репно-рекурзивну функцију за израчунавање \(n\)-тог Фибоначијевог броја. У наредној имплементацији, у сваком позиву рекурзивне функције fib_ њој се, уз број \(n\), прослеђују и две узастопне вредности Фибоначијевог низа \(F_k\) (у променљивој fpp) и \(F_{k+1}\) (у променљивој fp). Функција онда на основу њих израчунава следећу вредност \(F_{k+2}\) и затим наредном рекурзивном позиву прослеђује вредности \(n-1\), \(F_{k+1}\) и \(F_{k+2}\). Пошто се у почетном рекурзивном позиву прослеђују почетна вредност \(n\) (назовимо је \(n_0\)) и вредности \(F_0 = 0\) и \(F_1 = 1\), све време важи инваријанта да је \(k+n = n_0\). Излаз из рекурзије је за \(n=0\), па се тада тражена вредност налази у променљивој \(F_k = F_{n_0}\).

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

Извршавање броја \(F_5\) применом ове функције се може описати следећим низом једнакости:

\[\begin{eqnarray*} \mathtt{fib}(5) &=& \mathtt{fib}(5, 1, 0) = \mathtt{fib}(4, 1, 1) = \mathtt{fib}(3, 2, 1) \\ &=& \mathtt{fib}(2, 3, 2) = \mathtt{fib}(1, 5, 3) = \mathtt{fib}(0, 8, 5) = 5 \end{eqnarray*}\]

Елиминацијом ове репне рекурзије добијамо веома елегантну итеративну имплементацију.

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

Током извршавања репно-рекурзивних функција параметри се постепено мењају од неких почетних вредности (у примеру Фибоначијевих бројева то су вредности \(F_0 = 0\) и \(F_1 = 1\)) па све до крајњих, тражених вредности (у примеру Фибоначијевих бројева то су вредности \(F_{n}\) и \(F_{n+1}\)). Таква измена променљивих суштински је итеративна (променљиве се на потпуно исти начин мењају и у итеративној верзији, са петљама) и одговарајуће репно-рекурзивне функције често се називају итеративне функције. Пошто је императивним језицима, какви су C и C++, таква промена променљивих карактеристична је за петље, у њима ретко када пишу репно-рекурзивне функције (када програмер осмисли решење у којем се променљиве мењају на описани начин, он по обичају такво решење одмах формулише у виду петљи).

И рекурзија која није репно-рекурзивна често се може уклонити и заменити једноставном итерацијом, али то није једноставно урадити на систематичан начин, као у случају репне рекузије.

Пример 4.9.4. Анализом тока извршавања функције grej којом се израчунавају елементи Грејовог кода примећује се да се у сваком кораку на десни крај резултујуће ниске допише једна нула или јединица (у зависности од тога да ли \(k\) припада првој или другој половини одговарајућег \(n\)-тоцифреног Грејовог кода). То нас доводи до следеће итеративне имплементације.

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.5. У поглављу 1.4.4 приказана је итеративна имплементација функције за брзо степеновање дефинисане у поглављу 1.4.3. Пошто функција за брзо степеновање није репно рекурзивна, ослобађање од рекурзије није текло директно, већ се до итеративне функције дошло пажљивом анализом израчунавања рекурзивне функције и уочавањем да се у случају непарних вредности \(n\) вредности \(x\) којима се множи резултат рекурзивног позива којим се израчунава степен \(x^{n-1}\) могу акумулирати у новој променљивој s.

4.9.2 Ослобађање од рекурзије коришћење погодних структура података

За многе проблеме рекурзивно решење може бити веома елегантно али може бити и захтевно у смислу потребног времена или простора за извршавање. Чак и ако рекурзивна функција захтева мали стек оквир, уколико има много рекурзивних позива може доћи до препуњавања стека и прекида извршавања програма. Број рекурзивних позива који може довести до прекида извршавања програма зависи од много фактора, али обично је реда неколико десетина хиљада пре него неколико милиона. У ситуацијама када је могуће да број рекурзивних позива буде велики пожељно је рекурзивно решење заменити нерекурзивним. Као што је показано, у неким ситуацијама (за неке форме рекурзије као што је репна рекурзија) довољна је релативно једноставна трансформација програма. У неким ситуација, међутим, потребне промене могу изискивати потпуну промену логику програма и ослањање на додатне погодне структуре података.

Пример 4.9.6. Размотримо поново проблем попуњавања контуре (који је описан у поглављу 4.6.4). Овај проблем може бити решен и без коришћења рекурзије. Међутим, уместо рекурзије биће потребна нека погодна динамичка структура, и у овом случају то ће бити стек. Елементи стека ће бити поља мапе, тј. парови целих бројева.

У приказаном решењу, креће се од полазног поља (поља \((x,y)\)), оно се ставља на врх стека и онда, док год их има, обрађује једно по једно поље са врха стека. На врх стека стављају се сва суседна поља текућег поља која нису препреке. Координате суседних поља одређују се једноставно, користећи помоћни низ smer који садржи помераје за четири могућа смера.

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 Ојачавање индуктивне хипотезе

Приликом примене индуктивно-рекурзивне конструкције понекада се испоставља да само решење потпроблема мање димензије није довољно да би се реконструисало решење полазног проблема, али да се приликом рекурзивног решавања потпроблема може урадити и нешто додатно (на пример, израчунати неке помоћне информације) које нам онда помажу да решимо и полазни проблем. Дакле, до решења је могуће доћи захваљујући “кредиту” који смо добили из рекурзивног позива, али не смемо заборавити да вратимо тај “дуг” тј. да нашем позиваоцу поред траженог решења проблема урадимо и тај додатни посао (на пример, вратимо те помоћне информације) — иако то није потребно у полазном рекурзивном позиву, на свим другим нивоима рекурзије јесте. Такоће, и база мора бити проширена тако да обухвати овај додатни посао. Ова техника се назива ојачање индуктивне хипотезе. У случају ојачања индуктивне хипотезе, класичну схему

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

мењамо схемом

\[(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 Упарене заграде

Опишимо рекурзивни алгоритам који проверава да ли су заграде унутар ниске која садржи само отворене и затворене заграде коректно упарене. Ако приступимо овом проблему рекурзивно, ниску природно разлажемо на префикс и последњи карактер. Задатак не можемо решити тако што ће рекурзивни позив вратити само логичку вредност која описује да ли је префикс ниска која садржи коректно упарене заграде. Наиме, ако је последњи карактер ')', цела ниска ће бити коректна само ако је префикс такав да су све заграде коректно упарене осим једне заграде која је само отворена, али није још затворена. Зато је потребно ојачати индуктивну хипотезу и из рекурзивног позива треба да сазнамо и да ли су заграде упарене и колико је отворених заграда још незатворено.

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;
}

Наравно, овај програм се лако може превести у итеративну верзију (која је једноставнија и природнија). Њена инваријанта директно одговара рекурзивној конструкцији коју смо управо приказали и користи исту ојачану индуктивну хипотезу (у сваком кораку петље знамо да је до тада обрађен префикс исправан и да промељива otvoreno садржи број отворених заграда у префиксу).

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;
}

Илуструјмо ову технику кроз решење неколико задатака у којима ћемо углавном употребити индуктивну конструкцију са ојачаном индуктивном хипотезом.

Задатак: Максимални збир сегмента

Овај задатак је поновљен у циљу илустровања различитих техника решавања.

Текст задатка.

Решење

Каданов алгоритам

Покушавамо да алгоритам заснујемо на индуктивној конструкцији.

Дакле, ојачаћемо индуктивну хипотезу и претпоставити да умемо да израчунамо и максимални збир \(M_i\) неког сегмента првих \(i\) елемената низа и максимални збир \(S_i\) неког суфикса првих \(i\) елемената низа. Важи да је \(M_0 = S_0 = 0\), да је \(S_{i+1} = \max{(S_i+a_i, 0)}\) и \(M_{i+1} = \max{(M_i, S_{i+1})}\).

Имплементацију можемо направити итеративним алгоритмом коме је инваријанта да у сваком кораку петље знамо ове две вредности (максимум сегмента и максимум суфикса). Овај алгоритам је познат под називом Каданов алгоритам.

Пример 4.10.1. Прикажимо рад алгоритма на примеру низа -2 3 2 -3 -3 -2 4 5 -8 3. У таблици попуњавамо вредности \(S_i\) и \(M_i\).

\(i\) \(a_{i+1}\) \(S_i\) \(M_i\)
\(0\) \(0\)
\(1\) \(-2\) \(0 = \max(0 + (-2), 0)\) \(0 = \max(0, 0)\)
\(2\) \(3\) \(3 = \max(0 + 3, 0)\) \(3 = \max(0, 3)\)
\(3\) \(2\) \(5 = \max(3 + 2, 0)\) \(5 = \max(3, 5)\)
\(4\) \(-3\) \(2 = \max(5 + (-3), 0)\) \(5 = \max(5, 2)\)
\(5\) \(-3\) \(0 = \max(2 + (-3), 0)\) \(5 = \max(5, 0)\)
\(6\) \(-2\) \(0 = \max(0 + (-2), 0)\) \(5 = \max(5, 0)\)
\(7\) \(4\) \(4 = \max(0 + 4, 0)\) \(5 = \max(5, 4)\)
\(8\) \(5\) \(9 = \max(4 + 5, 0)\) \(9 = \max(5, 9)\)
\(9\) \(-8\) \(1 = \max(9 + (-8), 0)\) \(9 = \max(9, 1)\)
\(10\) \(3\) \(4 = \max(1 + 3, 0)\) \(9 = \max(9, 4)\)

Пошто елементе учитавамо један по један и не памтимо их истовремено, меморијска сложеност је \(O(1)\). Максимални збир сегмента и суфикса инкрементално израчунавамо једним проласком кроз задате елементе и временска сложеност је линеарна тј. \(O(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;
#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;
}

Задатак: Максимални збир несуседних елемената низа

Напиши програм који одређује највећи збир подниза датог низа целих бројева који не садржи два узастопна члана низа.

Опис улаза

Са стандардног улаза се уноси број чланова низа \(n\) (\(1 \leq n \leq 10^5\)), а затим из наредног реда чланови низа раздвојени размацима.

Опис излаза

На стандардни излаз исписати тражени максимални збир.

Пример 1

Улаз

6
7 3 2 4 1 5

Излаз

16

Објашњење

Максимални збир је збир сегмента \(7+4+5=16\).

Пример 2

Улаз

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

Излаз

17

Решење

Задатак можемо једноставно решити индуктивно-рекурзивном конструкцијом. Низ можемо разложити на последњи елемент и префикс пре њега. Да бисмо одредили максимални збир несуседних елемената низа, анализираћемо случај када је последњи елемент низа део тог максималног збира и када није (то су једине две могућности и једна од њих је сигурно тачна). Зато је максимални збир несуседних елемената низа максимум следећа два збира:

Дакле, осим што претпостављамо да умемо да решимо проблем мање димензије тј. да за префикс умемо да одредимо максимални збир несуседних елемената, потребно је да ојачамо индуктивну хипотезу и да за префикс умемо да одредимо и максимални збир несуседних елемената тог префикса ако последњи елемент префикса није укључен у тај збир. Наравно, као и увек када се ојачава индуктивна хипотеза, “дуг” се мора вратити па за префикс проширен додатним елементом поред максималног збира несуседних елемената, морамо да умемо да одредимо и максимални збир несуседних елемената када последњи елемент није укључен. Међутим, то није тешко, јер је то управо максимални збир несуседних елемената префикса. Максимални збир проширеног низа (без обзира на то да ли укључује или не укључује последњи елемент) одређујемо као максимум два описана збира (која на основу индуктивне хипотезе лако израчунавамо).

База је случај празног низа. Максимални збир његових несуседних елемената у свакој варијанти једнак је нули.

Обележимо са \(m_k\) максимални збир несуседних елемената првих \(k\) елемената датог низа. Циљ је да одредимо \(m_n\). Нека је \(m'_k\) максимали збир несуседних елемената првих \(k\) елемената низа у који није укључен елемент \(a_{k-1}\). Важе следеће рекурентне релације: \(m_0 = m'_0 = 0\), док за \(k > 0\), важи \(m'_k = m_{k-1}\) и \(m_k = \max(a_{k-1} + m'_{k-1}, m_{k-1})\).

Сложеност овог алгоритма је \(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;
}

Још једна индуктивно-рекурзивна конструкција којом се проблем може решити подразумева да се за сваки префикс низа одреди максимални збир несуседних елемената када је последњи елемент префикса укључен и максимални збир несуседних елемената када последњи елемент префикса није укључен.

Обележимо са \(m^{sa}_k\) максимални збир несуседних елемената првих \(k\) елемената низа, који садржи и елемент \(a_{k-1}\) и са \(m^{bez}_k\) максимални збир несуседних елемената првих \(k\) елемената низа, који не садржи елемент \(a_{k-1}\). База индукције може бити једночлан низ и важи \(m^{sa}_1 = a_0\), \(m^{bez}_1 = 0\). За сваку вредност \(k > 1\), важи \(m^{sa}_k = a_{k-1} + m^{bez}_{k-1}\) и \(m^{bez}_k = \max(m^{sa}_{k-1}, m^{bez}_{k-1})\). Тражена вредност једнака је \(\max(m^{sa}_n, m^{bez}_n)\).

Сложеност овог алгоритма је \(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;
}

Индуктивно-рекурзивна конструкција може тећи и на следећи начин. Претпостављамо да умемо да израчунамо максимални збир несуседних елемената сваког префикса низа. Ако је префикс празан, максимални збир несуседних елемената је нула, а ако је једночлан, тада је једнак већем од броја нула и првог елемента низа. Ако је префикс бар двочлан онда је максимални збир несуседних елемената тог префикса максимум максималног збира префикса без последњег елемента и збира последњег елемента и максималног збира без последња два елемента.

Дакле, добијамо да је \(m_0 = 0\), \(m_1 = \max(a_0, 0)\) и \(m_i = \max(m_{i-1}, a_{i-1} + m_{i-2})\).

Ова рекурзивна конструкција се може испрограмирати рекурзивном функцијом. Нажалост, то решење је прилично неефикасно.

Сложеност овог решења задовољава једначину \(T(n) = T(n-1) + T(n-2) + O(1)\), \(T(1) = T(0) = 1\), чије је решење експоненцијална функција (иста једначина се јавља и приликом директне рекурзивне имплементације израчунавања елемената Фибоначијевог низа).

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;
}

Рекурзију можемо уклонити и добити наредну итеративну имплементацију.

Сложеност овог алгоритма је \(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;
}

Систематичан начин ослобађања неефикасности проузроковане рекурзијом овог типа долази у облику техника динамичког програмирања, које је описано у засебном поглављу.

  1. У наставку под скупом природних бројева подразумевамо скуп \(\mathbb{N}_0\) тј. подразумевамо да је нула најмањи природни број.↩︎

  2. Често се цитира шала како се у речнику рекурзија може најилустративније објаснити тако што се под ставком рекурзија напише: види рекурзија.↩︎

  3. Фибоначијев низ јавља се у многим појавама у природи. На пример, пчеле се рађају из оплођених, а трутови из неоплођених јаја, па трут има само једну мајку, она има два родитеља (оца и мајку), они имају три родитеља (две баке и деку), они имају пет родитеља (три баке и два деке) и тако даље. Дакле, број предака трутова чини Фибоначијев низ. Фибоначи је низ увео кроз проблем бројања парова зечева који се паре тако да прво потомство дају два месеца после рођења и након тога сваки наредни месец.↩︎

  4. Грејове кодове увео је Френк Греј и они се користе за минимализацију логичких функција у склопу методе Карноових мапа, за корекцију грешака у дигиталној комуникацији (на пример, у дигиталној и кабловској телевизији) и слично.↩︎

  5. Овај проблем је у форми аутентичног мита описао француски математичар Де Парвил у једном часопису 1884.↩︎

  6. Иако данашњи рачунари имају неколико гигабајта радне меморије, програми на располагању обично имају свега неколико мегабајта за програмски стек. Предефинисана величина програмског стека може се променити задавањем одговарајуће опције компилатору, у некој мери, у зависности од конкретног система.↩︎

  7. Неки компилатори (пре свега за функционалне програмске језике) аутоматски детектују репно рекурзивне позиве и елиминишу их.↩︎