Рекурзија

Рекурзија (лат. recursio, recursion од recurrere: враћање) у математици и информатици означава поступак или функцију који у својој дефиницији користе сами себе. Другим речима, уколико неки поступак захтева да делови проблема које је раздвојио од других бивају независно подвргнути истом том поступку, тај поступак је рекурзиван.

Формалне дефиниције рекурзије

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

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

Родитељи особе су му преци (базни случај);
Родитељи предака су такође преци особе (корак рекурзије ).

Згодно је сматрати да рекурзивна дефиниција дефинише објекте у односу на претходно дефинисане објекте класе која се дефинише.

Дефиниције попут ове се често јављају у математици. На пример, формална дефиниција природног броја у теорији скупова је: 1 је природан број, и сваки природан број има свог наследника, који је такође природан број.

Следи још један, можда једноставнији начин да се разумеју рекурзивни процеси:

Да ли имаш решење? Ако имаш, јави резултат. (Без оваквог услова за прекидање, рекурзија би се вртела бесконачно).
Ако не, поједностави проблем, реши једноставнији проблем (проблеме), и спој резултате у решење почетног проблема. Затим јави резултат.

Шаљива илустрација гласи Како би разумео рекурзију, човек прво мора да разуме рекурзију. Или можда тачније, од Ендруа Плоткина: Ако већ знаш шта је рекурзија, запамти одговор. Ако не знаш, нађи некога ко стоји ближе Дагласу Хофштатеру^[1], и питај њега шта је рекурзија.

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

Рекурзивне дефиниције у математици

Рекурзивне дефиниције су присутне у математици. Пример је следећа дефиниција природних бројева:

1 је природни број
Ако је n природни број, онда је то и n+1.

Рекурзијом се дефинише и Фибоначијев низ:

1. члан низа је 0
2. члан низа је 1
сваки n-ти члан низа (n>2) је сума претходна два члана ( $a_{n}=a_{n-1}+a_{n-2}$ )

Рекурзивни алгоритми у програмирању

Битно је напоменути да у савременим програмским језицима попут C/C++ и Јаве свако рекурзивно решење неког проблема има и свој итеративни еквивалент, тј. алгоритам који исти проблем решава без рекурзије. У практичном програмирању углавном треба избегавати рекурзију јер таква решења у општем случају троше више времена од итеративних.^{[тражи се извор]}

Следи пар примера проблема који су решени рекурзијом.

Вредност факторијела

Факторијел је математичка функција која се у едукативне сврхе често спомиње у контексту рекурзије. Факторијел природног броја n је производ њега самог и свих природних бројева који су мањи од њега:

n!=\prod _{k=1}^{n}k=1\cdot 2\cdot \dots \cdot (n-2)(n-1)n

При овоме важе закони комутативности множења над скупом природних бројева, те се исто може обављати у било ком редоследу. Може се почети од броја n па ићи уназад све до броја 1. Ево како би то изгледало у програмском језику C:

int fakt(int n)
{
	if(n < 2) // Уколико је добијени број мањи од два,
	{ return 1; } // вратити 1.

	else // У супротном,
	{ return n*fakt(n-1); } // вратити тренутни број помножен са
                                 // факторијелом броја за један мањег
                                 // од њега.
}

У конкретном случају уколико би функција као аргумент добила број 5, рачун би се развијао на начин показан испод. Притом ће рекурзивни позиви функција бити обележени заградама, да би се дочарао редослед почетака и завршетака ових функција.

fakt(5) = 5 · fakt(4)
        = 5 · (4 · fakt(3))             // (јер је fakt(4) = 4 · fakt(3))
        = 5 · (4 · (3 · fakt(2)))       // (јер је fakt(3) = 3 · fakt(2))
        = 5 · (4 · (3 · (2 · fakt(1)))) // (јер је fakt(2) = 2 · fakt(1))
        = 5 · (4 · (3 · (2 · 1)))       // (јер је fakt(1) = 1)

        = 5 · (4 · (3 · (2 · 1)))       // сада се множење ових вредности врши редом
        = 5 · (4 · (3 · 2))             // којим се ф-је завршавају тј. уназад
        = 5 · (4 · 6)
        = 5 · 24
        = 120

Сума низа који се завршава нулом

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

public static int sum(int[] niz, int indeks) {
  if(indeks >= niz.length) {                  // Уколико се дошло до краја низа,
    return 0;                                 // рекурзија се прекида и враћа се
  }                                           // нула која представља неутрал за
                                              // операцију сабирања.

  return niz[indeks] + sum(niz, indeks+1);    // У супротном, враћа се сума елемента
                                              // који се налази на датом индексу и
                                              // рекурзивног позива ове функције који
                                              // треба да израчуна суму свих елемената
                                              // након њега
}

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

Узевши да је дати низ на пример a = {11,12,13,14,15}, ова функција би рачун обавила на следећи начин:

sum(a,0) = a[0] + sum(a,0+1)
         = 11   + (a[1] + sum(a,1+1))
         = 11   + (12   + (a[2] + sum(a,2+1)))
         = 11   + (12   + (13   + (a[3] + sum(a,3+1))))
         = 11   + (12   + (13   + (14   + (a[4] + sum(a,4+1)))))
         = 11   + (12   + (13   + (14   + (15   + 0))))          // нема a[5], враћа се нула

         = 11   + (12   + (13   + (14   + 15)))
         = 11   + (12   + (13   + 29))
         = 11   + (12   + 42)
         = 11   + 54
         = 65

Овај проблем има и друго решење. Аритметика показивача у језику C омогућава мало другачији приступ. Наиме, функција овде не мора да прима и низ, и индекс елемента да би приступила елементу. Довољно јој је само дати показивач на тражени елемент. Како се овде увек тражи следећи елемент, показивач на њега је лако добити из показивача на тренутни. Да би се имплементација поједноставила, узећемо додатни услов да се низ завршава са нулом.

int asum(const int* p)
{
	if(*p == 0) // Уколико је тренутно обрађивани број нула,
	{ return 0; } // рекурзија се прекида. Претходном резултату
                                    // ће бити додата враћена нула.

	else // У супротном, 
	{ return *p + asum(p+1); } // се исти број сабира са следећим и као такав
                                    // враћа претходним сабирцима.
}

Понашање ове функције је идентично понашању горенаведене, с том разликом што задати низ треба да буде a = {11,12,13,14,15,0}. Аргуменат при првом позиву функције је увек име низа, нпр. позив за низ a би био asum(a).

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

Верижни разломци

Један од верижних разломака, који се везује за вредност броја пи.

{\frac {4}{\pi }}=1+{\frac {1}{3+{\frac {4}{5+{\frac {9}{7+{\frac {16}{9+{\frac {25}{11+{\frac {36}{13+...}}}}}}}}}}}}

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

Сабирци: 1, 3, 5, 7, 9, 11, 13, ... = 2n - 1, n = 1, ...

Дељеници: 1, 4, 9, 16, 25, 36, ... = n², n = 1, ...

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

{\frac {4}{\pi }}\approx 1+{\frac {1}{3+{\frac {4}{5+{\frac {9}{7+{\frac {16}{9+{\frac {25}{11+0}}}}}}}}}}

Имплементација овог решења у програмском језику C би изгледала овако:

double f1(int n) // Функција добија редни број разломка
{
	if(n > 200) // Ако је редни број већи од 200,
	{ return 2*n-1; } // рекурзија се прекида враћањем само 
                                     // одговарајућег непарног броја.

	else // У супротном
	{
		return // се враћа збир
		 (2*n-1) // одговарајућег непарног броја,
		 + n*n / f1(n+1); // и квадрата редног броја разломка,
	} // подељеног са следећим разломком.
}

Ову функцију треба увек позивати са аргументом n=1.

Често има више решења. Посматрањем низова се може увидети и следећа законитост, при истој расподели на разломке.

Ако су код једног разломка сабирак a и дељеник b, код следећег ће то бити a+2 и a+b+2.

Притом редни број разломка, који је у овом случају n=a+1/2, не мора бити једини критеријум за заустављање рекурзије. Целобројни тип, који ће и у овом случају бити кориштен за обраду вредности a и b има своја ограничења у опсегу који покрива, тако да би неконтролисани раст ових вредности дао погрешне резултате или изазвао пад програма. С обзиром да вредност b расте много брже од вредности a, довољно је прекинути рекурзију када дође до неке вредности за коју је сигурно да је достижна пре постизања недозвољених вредности. Како и није потребно превише разломака да би се ваљани резултат сместио у дабл, тип реалних бројева, ова граница сме бити прилично ниско.

Једна од могућих имплементација би била:

double f(int a, int b)
{
	if(b > 1000) // Уколико променљива ''b'' премаши унапред
                                        // задату вредност,
	{ return a; } // рекурзија се прекида и враћа се само ''a''.

	else // У супротном, рекурзија се наставља
	{ return a + b/f(a+2,a+b+2); } // и враћа се следећи сабирак бесконачног низа,
                                        // који у себи садржи рекурзивни позив
}

Ова функција се увек мора позивати са аргументима a=1 и b=1

Референце

^ Даглас Хофштатер је амерички академик који је написао чувену књигу Гедел, Ешер, Бах: Вечна златна плетеница.

Види још

[1] Даглас Хофштатер је амерички академик који је написао чувену књигу Гедел, Ешер, Бах: Вечна златна плетеница.

[1]