Изворни код странице Рекурзија (компјутерске науке)

{{лектура}}
[[Датотека:RecursiveTree.JPG|thumb|396x396px|Дрво створено коришћењем језика [[Лого (програмски језик)|Лого]] и ослањајући се на рекурзију]]
'''Рекурзија '''у [[Информатика|компјутерској науци]] је метод где решење проблема зависи од решења мањих случајева истог проблема (за разлику од  [[итерација]]).{{sfn|Graham|Knuth|Patashnik|1990|pp=}} Овај приступ се може применити на многе врсте проблема, а [[рекурзија]] је једна од централних идеја компјутерских наука.<ref name="automatski generisano2">{{harvnb|Epp|1995|pp=}}</ref><blockquote class="">"Снага рекурзије очигледно лежи у могућности дефинисања бесконачног низа објеката до коначног саопштења. На исти начин, бесконачан број израчунавања може се описати коначном рекурзијом програма, чак и ако тај програм не садржи изричита понављања."<ref name="automatski generisano1">{{harvnb|Wirth|1976|pp=}}</ref>
</blockquote>Већина рачунарских програмских језика подржавају рекурзију дозвољавајући [[Функција (програмирање)|функцији]] да се позове у тексту програма. Неки  [[Функционално програмирање|функционални програмски језици]]  не дефинишу никакве петље конструкције, али ослањају се искључиво на рекурзије да стално зову код. [[Computability theory (computer science)|Рекурзивна теорија]] доказује да ови строго рекурзивни језици су [[Тјурингова потпуност|Тјуринг - комплетни]] ; они су рачунски јаки као и Тјуринг-комплетни императивни језици, што значи да они могу да реше исту врсту проблема као и императивни језици чак и без уобичајених структурних команди као што су "док" и "за".

== Рекурзивне функције и алгоритми ==
Заједничка тактика [[Програмирање|компјутерског програмирања]] је да поделите проблем у под-проблеме, истог типа као и оригинал, решити ове под-проблеме, и комбиновати резултате. Ово се често назива [[Подели па владај (информатика)|подели па владај метод]]; када се комбинује са [[Лукап табела|лукап табелом]] која садржи резултате решавања под-проблема (да би се избегло њихово решавање у више наврата и стварања додатног времена израчунавања), може се назвати [[Динамичко програмирање|динамично програмирање]] или [[мемоизација]].

Рекурзивног функција дефинисана је са један или више базних предмета, што значи улаз за које функција даје резултат [[тривијално]] (без понављања), и један или више рекурзивних случајева, што значи улаз за који се програм враћа (позиви се) . На пример, функција [[факторијел]] fсе може рекурзивно дефинисати једначинама  <span class="texhtml ">0! = 1</span>, а за све <span class="texhtml ">''n'' > 0</span>, <span class="texhtml ">''n''! = ''n''(''n'' − 1)!</span>. Ниједна једначина по себи представља потпуну дефиницију; први је основни случај, а други је рекурзивни случај. Будући да основни случај прекида ланац рекурзије, понекад се такође назива и "завршен случај".

Посао рекурзивних случајева може се посматрати као разбијање сложених улаза у једноставније. У правилно дизајнираној рекурзивној функцији, са сваким рекурзивним позивом, проблем улаза мора бити поједностављен на такав начин да на крају основног случаја мора бити постигнут. (Функције које нису намењене да доврше под нормалним околностима, на пример, неки систем и сервер процеси-су изузетак). Занемарити да се напише основни случај, или тестирати за то погрешно, може изазвати [[бесконачна петља|бесконачну петљу]].

За неке функције (као што је она која израчунава [[Ред (математика)|ред]] за <span class="texhtml ">''[[Број е|e]]'' = 1/0! + 1/1! + 1/2! + 1/3! + ...</span>) не постоји очигледан основни случај подразумеван од стране улазних података; за ово се може додати [[параметар]] (као што је број услова који се додаје, у нашем примеру серије) да обезбеди 'заустављање критеријума' који успоставља основни случај. Такав пример је природно више третирати ко-рекурзије, где узастопни термини у излазу су парцијалне суме; ово се може конвертовати у рекурзије користећи индексирања параметара "израчунати n-ти термин (n-ти парцијални збир)".

== Рекурзивни типови података ==
Многи [[Рачунарски програм|компјутерски програми]]  морају обрадити или генерисати произвољно велике количине [[податак]]а. Рекурзија је једина техника за представљање података чију тачну величину [[програмер]] не зна: програмер може навести ове податке са самореферентне дефиниције. Постоје две врсте самореферентних дефиниција: индуктивне и коиндуктивне дефиниције.

=== Индуктивно дефинисани подаци ===
Индуктивно дефинисан рекурзивни податак је онај који одређује како изградити пример података. На пример,  [[Povezana lista|повезана листа]] се може дефинисати индутивно (коришћењем Хаскелове синтаксе):
: <source lang="haskell">data ListOfStrings = EmptyList | Cons String ListOfStrings</source>
Код изнад одређује листу стригова да буде празна, или структура која садржи стринг и листу стрингова. Само-референца у дефиницији дозвољава изградњу листа неког (коначниог) броја стрингова.

Други пример индуктивне [[Дефиниција|дефиниције]] је [[природан број]] (или позитивни [[цео број]]):
: <code>Природан број је 1 или n+1, где је n природан број.</code>
Слично, рекурзивне [[Дефиниција|дефиниције]] се често користе за моделирање структуре [[израза]] и [[Изјавама|изјава]] у програмирамском језику. Језички дизајнери често изражавају граматику у синтакси као што је  [[Бакус–Наурова форма|Бакус-Наурова форма]]; овде је таква граматика, за једноставним језиком аритметичких израза са множењем и сабирањем:<source lang="bnf">
 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)
</source>Ово каже да је израз или број, производ два израза, или збир два израза. Рекурзија која се односи на изразе у другој и трећој линија, граматика дозвољава произвољно сложене аритметичке изразе као што су   <code>(5 * ((3 * 6) + 8))</code>, са више од једног производа или збира операција у једном изражавању.

=== Коиндуктивно дефинисани подаци и корекурзија ===
Коиндуктивна дефиниција података је она која одређује операције које се могу обављати на делу података; типично, самореференцијална коиндуктивна дефиниција се користи за структуре података бесконачне величине.

Коиндуктивна дефиниција безброј [[токова]] стрингова, неформално, може да изгледа овако:
 Ток стрингова је објекат s тако да:
  глава(s) је стринг, а    
  реп(s) је ток стрингова.

Ово је веома слично индуктивној дефиницији листе стрингова; разлика је у томе што ова дефииција одређује како да приступите садржају података структуре наиме, преко аксесор функција <code>глава</code> и <code>реп</code>— и који то садржаји могу бити, док индуктивна дефиниција одређује како да креирате структуру и шта може бити креирано од.

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

== Врсте рекурзије ==

=== Једнострука и вишеструка рекурзија ===
Рекурзија која садржи само једну референцу позната је као '''једнострука рекурзија''', док рекурзија која садржи више само-референца је позната као вишеструка рекурзија. Стандардни примери једноструке рекурзије укључују листу ношења, као што су линеарно тражење, или рачунање факторијела, док стандардни примери вишеструке рекурзије укључују  [[обилазак стабла]], као што у дубини првог тражења, или рачунања [[Фибоначијев низ|Фибоначијевог низа]].

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

Вишеструка рекурзија понекад може бити конвертована у једноструку рекурзију (и, ако се жели, одатле у итерацију). На пример, док рачунање Фибоначијевог низа је вишеструка итерација, свака вредност захтева две претходне вредности, то може да се израчуна једноструком рекурзијом коришћењем две узастопне вредности као параметре. Ово је више природно урамљено као корекурзија, изградња од почетних вредности, праћење на сваком кораку две узастопне вредносте - види [[корекурзија: примери]]. Софистицирани пример користи [[бинарно стабло нити]], које омогућава итеративни обилазак стабла, пре него вишеструка рекурзија.

=== Индиректна рекурзија ===
Већина основних примера рекурзије, и већина од примера који су овде, показују '''''директну'' рекурзију''', у којој се функција зове. ''Индиректна'' рекурзија настаје када се функција не зове само по себи већ другу функцију да се зове (директно или индиректно). На пример, ако  ''f'' позива ''f'' , то је директна рекурзија, али ако ''f'' позива ''g'' којом се позива ''f'', онда је то индиректна рекурзија ''f'' . Ланци од три или више функција су могуће; на пример, функција 1 позива функцију 2, функција 2 позива функцију 3, и функција 3 позива функцију 1 поново.

Индиректна рекурзија се такође назива и  [[Mutual recursion|узајамна рекурзија]], што је више симетрична термину, мада то је једноставно разлика нагласка, а не разликује појам. То је, ако ''f'' позива ''g,'' а затим ''g'' позива ''f'', што заузврат опет позива ''g'', са тачке гледишта ''f'' , ''f'' је посредно рекурзија, док са тачке гледишта  ''g'', то је индиректна рекурзија, док са тачке гледишта оба ''f'' и ''g'' је вишеструка рекурзија једна на друге. Слично сет од три или више функција које позивају једни друге може се назвати скуп међусобно рекурзивних функција.

=== Анонимна рекурзија ===
Рекурзија се обично врши позивањем функција по имену. Међутим, рекурзија може да се уради преко имплицитног позивања функција заснована на тренутном контексту, што је посебно корисно [[Anonymous function|анонимне функције]], и познат је као  [[Anonymous recursion|анонимна рекурзија]].

=== Структурна у односу на генеративне рекурзије ===
Неки аутори класификују рекурзију као  "структурну" или "генеративну". Разлика се односи на који рекурзивни поступак добије податке на који ради, и како се обрађују те податке:
<blockquote class="">
[Функције које конзумирају структурирани податак] обично разлаже своје аргументе у своје непосредне структурне компоненте, а затим обрађује те компоненте. Ако један од непосредних компоненти припада истој класи података као улаз, функција је рекурзивна. Из тог разлога, говоримо о овим функцијама као (структурно) рекурзивним функцијама.<ref name="Felleisen HtDP 2001"><cite class="citation book">Felleisen, Matthias; Robert Bruce Findler; Matthew Flatt; Shriram Krishnamurthi (2001). </cite></ref></blockquote>Дакле, дефинисање карактеристика структурално рекурзивних функција је да аргумент за сваки рекурзивни позив је садржај поља оригиналног улаза. Структурна рекурзија обухвата скоро све обиласке стабла, укључујући XML прераде, бинарног стабла креирања и претраге, итд. Узимајући у обзир алгебарску структуру природних бројева (који је, природан број је или нула или наследник природног броја), функција као факторијел се такође може сматрати структурном рекурзијом.

'''<span id="Generative recursion">Генеративна рекурзија </span>''' је алтернатива. Многи познати рекурзивни алгоритми генеришу потпуно нови податак из датих података и враћамо на њу. [[How to design programs|HtDP (Како осмислити програм)]] се односи на ову врсту као генеративне рекурзије. Примери генеративних рекурзија укључују [[Еуклидов алгоритам]], [[квиксорт]], [[бинарна претрага]], [[Sortiranje spajanjem|сортирање са спајањем]], [[Њутнова метода]], [[фрактал]], и [[прилагодљива интеграција]].{{sfn|Felleisen|2002|p=108}}

Ова разлика је важна за [[доказивање престанка]] функције.  
* Све структурно рекурзивне функције на коначне ([[индуктивно дефинисано]]) структуре података се лако може показати да доврши, преко структурне индукције: интуитивно, сваки рекурзивни позив добија мањи део улазних података, док се не постигне основни случај.
* Генеративне рекурзивне функције, насупрот томе, не морају хранити мањи улаз својим рекурзивним позивима, тако да говорити о њиховом раскиду није нужно тако једноставно, и избегавање [[бесконачна петља|бесконачне петље]] захтева већу бригу. Ове генеративне рекурзивне функције често се могу тумачити као корекурзивне функције - сваки корак генерише нове податке, као што су сукцесивна апроксимација у Њутновој методи - и довршетак ове корекурзије захтева  да подаци на крају задовоље неке услове, није гарантовано.
* Што се тиче [[варијанти петље]], структурна рекурзија је када постоји очигледна варијанта петље, односно величина или комплексност, која почиње коначано и смањује се на сваком рекурзивном кораку. 
* Насупрот томе, генеративна рекурзија је кад не постоји таква очигледна варијанта петље, и престанак зависи од функције, као што је  "грешка приближавања", то не мора да се смањи на нулу, и на тај начин раскид није загарантован без даљих анализа.

== Рекурзивни програми ==

=== Рекурзивне процедуре ===

==== Факторијел ====
Класичан пример рекурзивне процедуре је функција коришћена за рачунање  [[факторијел]]а [[Природан број|природног броја:]]
: <math> \operatorname{fact}(n) =
 \begin{cases}
 1 & \mbox{if } n = 0 \\
 n \cdot \operatorname{fact}(n-1) & \mbox{if } n > 0 \\
 \end{cases}
</math>
{| class="wikitable"
|-
![[Псеудокод|Псеукод]] (рекурзивно:
|-
|
 '''function''' factorial is:
 
 '''input''': integer ''n'' such that ''n'' >= 0
 
 '''output''': [''n'' × (''n''-1) × (''n''-2) × … × 1]

     1. if ''n'' is 0, '''return''' 1
     2. otherwise, '''return''' [ ''n'' × factorial(''n''-1) ]
 
 '''end''' factorial
|}
Функција се може записати и као рекурзивни однос:
: <math>b_n = nb_{n-1}</math>
: <math>b_0 = 1</math>
Ова процена понављања односа показује рачунање које ће се обавити у процени Псеудокода изнад:

{| class="wikitable"
|-
!Израчунавање понављања односа за n = 4:
|-
| b<sub>4</sub>           = 4 * b<sub>3</sub>
 
              = 4 * (3 * b<sub>2</sub>)
              = 4 * (3 * (2 * b<sub>1</sub>))
              = 4 * (3 * (2 * (1 * b<sub>0</sub>)))
              = 4 * (3 * (2 * (1 * 1)))
              = 4 * (3 * (2 * 1))
              = 4 * (3 * 2)
              = 4 * 6
              = 24
|}
Ова функција факторијела може бити описана без употребе рекурзије тако што користе типичне петље конструкције које се налазе у императивним програмским језицима:
{| class="wikitable"
|-
! Псеукод (итеративно)
|-
|
 '''function''' factorial is:
 
 '''input''': integer ''n'' such that ''n'' >= 0
 
 '''output''': [''n'' × (''n''-1) × (''n''-2) × … × 1]
 
     1. '''create''' new variable called ''running_total'' with a value of 1
 
     2. '''begin''' loop
           1. if ''n'' is 0, '''exit''' loop
           2. '''set''' ''running_total'' to (''running_total'' × ''n'')
           3. '''decrement''' ''n''
           4. '''repeat''' loop

     3. '''return''' ''running_total''
 
 '''end''' factorial
|}
Императив код изнад је еквивалент за ову математичку дефиницију користећи акумулациону роменљиву <span class="texhtml "><var>t</var></span><span class="texhtml "></span>'':''
: <math>
\begin{array}{rcl}
\operatorname{fact}(n) & = & \operatorname{fact_{acc}}(n, 1) \\
\operatorname{fact_{acc}}(n, t) & = &
 \begin{cases}
 t & \mbox{if } n = 0 \\
 \operatorname{fact_{acc}}(n-1, nt) & \mbox{if } n > 0 \\
 \end{cases}
\end{array}
</math>
Дефиниција изнад директно преводи  [[Функционално програмирање|функционалним програмским језиком]] као што су [[Scheme (programming language)|Шеме]];  ово је пример итерације која се спроводи рекурзивно.

==== Највећи заједнички делилац ====
[[Еуклидов алгоритам]], који рачуна [[највећи заједнички делилац]] два цела броја, може се записати рекурзивно.

Дефиниција функције:
: <math> \gcd(x,y) =
 \begin{cases}
 x & \mbox{if } y = 0 \\
 \gcd(y, \operatorname{remainder}(x,y)) & \mbox{if } y > 0 \\
 \end{cases}
</math>
{| class="wikitable"
|-
! [[Псеудокод|Псеукод]] (рекурзивно):
|-
|
 '''function''' gcd is:
 '''input''': integer ''x'', integer ''y'' such that ''x'' > 0 and ''y'' >= 0

     1. if ''y'' is 0, '''return''' ''x''
     2. otherwise, '''return''' [ gcd( ''y'', (remainder of ''x''/''y'') ) ]
 
 '''end''' gcd
|}
[[Recurrence relation|Понављање односа]] за највећи заједнички делилац <math>x \% y</math> изражава [[остатак]] од <math>x / y</math>:
: <math>\gcd(x,y) = \gcd(y, x \% y)</math> if <math>y \neq 0</math>
: <math>\gcd(x,0) = x</math>
{| class="wikitable" style="margin-bottom: 10px;"
|-
! Израчунавање понављања односа за x = 27 и y = 9:
|-
| gcd(27, 9)   = gcd(9, 27% 9)
              = gcd(9, 0)
              = 9
|-
! Израчунавање понављања односа за x = 111 и           y = 259:
|-
| gcd(111, 259)   = gcd(259, 111% 259)
                 = gcd(259, 111)
                 = gcd(111, 259% 111)
                 = gcd(111, 37)
                 = gcd(37, 111% 37)
                 = gcd(37, 0)
                 = 37
|}
Рекурзивни програм горе је реп-рекурзије; то је еквивалентно итеративни алгоритам и рачунање приказано горе показује кораке процене да ће да се обављају на језику који елиминише задње позиве. Испод је верзија истог алгоритма користећи експлицитну итерацију, погодан за језик који не отклони задње позиве. По одржавању својих стања у потпуности. променљиве ''x'' и ''y'' и коришћење конструктивне петље, програм избегава доношење рекурзивних позива и расте позив стека.
{| class="wikitable" style="margin-bottom: 10px;"
|-
! Псеукод  (итеративно):
|-
|
 '''function''' gcd is:

 '''input''': integer ''x'', integer ''y'' such that ''x'' >= ''y'' and ''y'' >= 0
 
     1. '''create''' new variable called ''remainder''
 
     2. '''begin''' loop
           1. if ''y'' is zero, '''exit''' loop
           2. '''set''' ''remainder'' to the remainder of x/y
           3. '''set''' x to y
           4. '''set''' y to ''remainder''
           5. '''repeat''' loop
 
     3. '''return''' ''x''

 '''end''' gcd
|}
Итеративни алгоритам захтева привремену променљиву, па чак и дато знање Еуклидовог алгоритма је теже да разумеју процес простом контролом, иако су два алгоритма веома слична у својим корацима.

==== Ханојска кула ====
[[Датотека:Tower_of_Hanoi.jpeg|thumb|110x110px|Ханои кула]]
[[Ханојска кула]] је математичка загонетка чије решење илуструје рекурзију.{{sfn|Graham|Knuth|Patashnik|1990|pp=}}<ref name="automatski generisano2" /> Постоје три штапа који могу да чувају гомилу дискова различитих пречника. Већи диска никад не може бити сложен на врху мањег. Почевши са н дисковима на једном штапу, они морају бити премештени на други штап један по један. Који је најмањи број корака да бисте померили све?

''Дефиниција функције'':
: <math> \operatorname{hanoi}(n) =
 \begin{cases}
 1 & \mbox{if } n = 1 \\
 2\cdot\operatorname{hanoi}(n-1) + 1 & \mbox{if } n > 1\\
 \end{cases}
</math>
''Понављање односа за ханои:''
: <math>h_n = 2h_{n-1}+1</math>
: <math>h_1 = 1</math>
{| class="wikitable"
|-
! Израчунавање понављања односа за n = 4:
|-
| hanoi(4)     = 2*hanoi(3) + 1
              = 2*(2*hanoi(2) + 1) + 1
              = 2*(2*(2*hanoi(1) + 1) + 1) + 1
              = 2*(2*(2*1 + 1) + 1) + 1
              = 2*(2*(3) + 1) + 1
              = 2*(7) + 1
              = 15
|}
Пример имплементације:
{| class="wikitable"
|-
![[Псеудокод|Псеукод]] (рекурзивно):
|-
|
 '''function''' hanoi is:
 
 '''input''': integer ''n'', such that ''n'' >= ''1''
 
     1. '''if''' n is 1 '''then return''' 1
 
     2. '''return''' [2 * ['''call''' hanoi(n-1)] + 1]
 
 '''end''' hanoi
|}
Иако нису сви рекурзивне функције имају експлицитан решење, Ханојска кула секвенца може да се сведе на експлицитне формуле
.<ref name="automatski generisano2" />
{| class="wikitable" style="margin-bottom: 10px;"
|-
!Експлицитна формула за Ханои кулу:
|-
| h<sub>1</sub> = 1   = 2<sup>1</sup> - 1
 h<sub>2</sub> = 3   = 2² - 1
 h<sub>3</sub> = 7   = 2³ - 1
 h<sub>4</sub> = 15  = 2<sup>4</sup> - 1
 h<sub>5</sub> = 31  = 2<sup>5</sup> - 1
 h<sub>6</sub> = 63  = 2<sup>6</sup> - 1
 h<sub>7</sub> = 127 = 2<sup>7</sup> - 1

 In general:
 h<sub>n</sub> = 2<sup>n</sup> - 1, for all n >= 1
|}

==== Бинарна претрага ====
[[Бинарна претрага]] је метод у потрази  [[Sortirani niz|сортираног низа]] за један елемента смањењем низ на пола са сваким рекурзивним пролазом. Трик је да изаберете средиште у близини центра низа, упоредимо податке у том тренутку са подацима који се претресају и онда одговор на један од три могућа стања: подаци се налазе на средини, подаци на средини већи него што су се подаци тражили, или су подаци на средини мањи од података који се траже.

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

Пример имплементације бинарне претраге у C:<source lang="C">
 /*
  Call binary_search with proper initial conditions.

  INPUT:
    data is an array of integers SORTED in ASCENDING order,
    toFind is the integer to search for,
    count is the total number of elements in the array

  OUTPUT:
    result of binary_search

 */
 int search(int *data, int toFind, int count)
 {
    //  Start = 0 (beginning index)
    //  End = count - 1 (top index)
    return binary_search(data, toFind, 0, count-1);
 }

 /*
   Binary Search Algorithm.

   INPUT:
        data is a array of integers SORTED in ASCENDING order,
        toFind is the integer to search for,
        start is the minimum array index,
        end is the maximum array index
   OUTPUT:
        position of the integer toFind within array data,
        -1 if not found
 */
 int binary_search(int *data, int toFind, int start, int end)
 {
    //Get the midpoint.
    int mid = start + (end - start)/2;   //Integer division

    //Stop condition.
    if (start > end)
       return -1;
    else if (data[mid] == toFind)        //Found?
       return mid;
    else if (data[mid] > toFind)         //Data is greater than toFind, search lower half
       return binary_search(data, toFind, start, mid-1);
    else                                 //Data is less than toFind, search upper half
       return binary_search(data, toFind, mid+1, end);
 }
</source>

=== Рекурзија структуре података (структурна рекурзија) ===
Важна примена рекурзије у компјутерсој науци је у дефинисању динамичке структуре података као што су  [[Листа (структура података)|листе]] и [[Стабло (структура података)|стабла]]. Рекурзивне структуре података могу динамички расти до теоретски бесконачне величине као одговор на почетне захтеве; насупрот томе, величина статичког низа мора бити постављена на компајлирање. Рекурзивни алгоритми су посебно одговарајући када се основни проблем или податак који се третира,  дефинисани у рекурзивним условима.<ref name="automatski generisano1" />

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

Докле год програмер произилази образац из дефиниције података, функција запошљава структурну рекурзију. То јест рекурзија у функцијском телу троши непосредни део дате вредности.<ref name="Felleisen 2002 108">{{Cite book|last=Felleisen| first = Matthias  | contribution = Developing Interactive Web Programs  |year=2002| title = Advanced Functional Programming: 4th International School  |url=https://archive.org/details/springer_10.1007-b11942| editor-last=Jeuring| editor-first = Johan  | volume =  | place = Oxford, UK  | publisher = Springer  | id =  | postscript = <!--None--> |pages=[https://archive.org/details/springer_10.1007-b11942/page/n117 108] }}</ref>

==== Повезана листа ====
Испод је C дефиниција повезане структуре листе чворова. Обавештење посебно како је чвор дефинисан у смислу себи. "Следећи" елемент структурног чвора је показивач на други структурни чвор, ефективно стварајући тип листе.<source lang="C">
struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};
</source>Зато што је ''struct node'' структура података  рекурзивно се дефинишу процедуре које послују на њему, могу да се реализују као природно рекурзивне процедуре. Поступак  ''list_print''  дефинисан у даљем тексту шетња кроз листу док је листа празна (тј показивач листе  има вредност НУЛЛ)..<source lang="C">
void list_print(struct node *list)
{
    if (list != NULL)               // base case
    {
       printf ("%d ", list->data);  // print integer data followed by a space
       list_print (list->next);     // recursive call on the next node
    }
}
</source>

==== Бинара стабла ====
Испод је једноставна дефиниција за бинарно стабло чвора. Као чвориште за повезане листе, што је дефинисано у смислу себе, рекурзивно. Постоје два самореференцијална показивача: лево (показујући на лево под-стабло) и право (показујући надесно под-стабло).
<source lang="C">
struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};
</source>Операције на стаблу могу да се имплементирају коришћењем рекурзија. Имајте на уму да, јер постоје две самореференцијална показивача (лево и десно), операције стабла могу захтевати два рекурзивна позива:<source lang="C">
// Test if tree_node contains i; return 1 if so, 0 if not.

int tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return 0;  // base case
    else if (tree_node->data == i)
        return 1;
    else
        return tree_contains(tree_node->left, i) || tree_contains(tree_node->right, i);
}
</source>Највише два рекурзивна позива ће бити направљена за сваки дати позив на ''tree_contains'' како је горе дефинисано.
<source lang="C">
// Inorder traversal:
void tree_print(struct node *tree_node) {
        if (tree_node != NULL) {                  // base case
                tree_print(tree_node->left);      // go left
                printf("%d ", tree_node->data);   // print the integer followed by a space
                tree_print(tree_node->right);     // go right
        }
}
</source>Горњи пример илуструје [[Обилазак стабла|обилазак ставла]] бинарног дрвета. [[Binarno stablo pretrage|Бинарно стабло претраге]] је специјални случај бинарног дрвета где су елементи података у сваком чвору у реду.

==== Filesystem traversal ====
Од броја датотека  [[Датотечни систем|фајлссистема]] може да варира, [[рекурзија]] је једини практичан начин да пролазе и тако набраја његов садржај. . Преласком фајлсистем је веома сличан оном из [[Обилазак стабла|обиласка стабла]], па су концепти иза обиласка стабла важе за прелажење фајлсистема. Прецизније, код испод ће бити пример [[обилазак стабла]] на фајлсистему..<source lang="Java">
import java.io.*;

public class FileSystem {

	public static void main (String [] args) {
		traverse ();
	}

	/**
	 * Obtains the filesystem roots
	 * Proceeds with the recursive filesystem traversal
	 */
	private static void traverse () {
		File [] fs = File.listRoots ();
		for (int i = 0; i < fs.length; i++) {
			if (fs[i].isDirectory () && fs[i].canRead ()) {
				rtraverse (fs[i]);
			}
		}
	}

	/**
	 * Recursively traverse a given directory
	 *
	 * @param fd indicates the starting point of traversal
	 */
	private static void rtraverse (File fd) {
		File [] fss = fd.listFiles ();

		for (int i = 0; i < fss.length; i++) {
			System.out.println (fss[i]);
			if (fss[i].isDirectory () && fss[i].canRead ()) {
				rtraverse (fss[i]);
			}
		}
	}

}
</source>Овај код спаја линије, барем донекле, између рекурзије и [[Iteration|понављања]]. То је, у суштини, рекурзивна имплементација, што је најбољи начин за прелазак  [[Датотечни систем|фајлс истема]]. Такође је пример директне и индиректне рекурзије. Метод "''rtraverse''" је чисто директан пример; метод  "''traverse''" је индиректан, којом се позива "''rtraverse''." Овај пример треба "основни случај" сценарио с обзиром на чињеницу да ће увек бити неки фиксни број датотека или директоријума у датом фајл систему.

== Питања имплементације ==
Заправо имплементације, више него чиста рекурзивноа функција (јединствена провера за основни случај, иначе рекурзивни корак), велики број модификација може бити, у сврху јасноће и ефикасности. Ово укључује:
* Омот функција (на врху) 
* Кратким спајањем основног случаја, звани "рука- дужина рекурзије" (при дну) 
* Хибрид алгоритма (на дну) - пребацивање на други алгоритам довољно малих података
На основу елеганцијом, конфекција функције се углавном одобравају, док је кратак спој основног случаја није пожељан, посебно у академским круговима. Хибридни алгоритми се често користе за ефикасност, смањење режијске трошкове рекурзије у малим случајевима рука- дужине рекурзије је посебан случај за ово.

=== Омот функција ===
[[Омот функција]] је функција која се зове директно, али не рекурзивно, позива се посебна помоћна функција која заправо ради о рекурзији.  

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

=== Кратко спајање основног случаја<span id="Arm's-length recursion"></span> ===
Кратко спајање основног случаја, познатије као '''рука- дужина рекурзије''', састоји се од провере основног случаја пре него што рекурзивно позове – односно провера да ли следећи позив ће бити основа случаја, уместо позива, а затим проверава за основни случај. Кратки спој је посебно учинио за ефикасност разлога, да се избегне изнад главе једног позива функције која се одмах враћа.. Имајте на уму да, пошто основни случај већ проверава (непосредно пре рекурзивног корака), не треба да буде проверен одвојено, али не треба да се користи омот функција у случају када је укупна рекурзија почиње са основним случајем. На пример, у факторијел функцији, правилни основни случај је  0! = 1, док одмах враћа 1 за 1! за кратки спој, и може пропустити 0; ово се може ублажити и у омот функцији.

Кратки спој је пре свега забринутост када су наишли на велики број база случајева, као што су Нулл показивач на стабло, које може бити линеарно у броју позива функција, па значајне уштеде за ''O''(''n'') алгоритма; ово је приказано испод за дубинско првог претреса. Кратког споја на дрвету одговара разматра лист (не празна чвор без деце) као основног случаја, него с обзиром празан чвор као основног случаја. Ако постоји само један основни случај, као што су у израчунавању факторијела, кратког споја обезбеђује само О (1) уштеде.  

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

==== Дубина прве претраге ====
Основни пример кратког споја дат је у дубини прве претраге (DFS) бинарног стабла; види бинарни део стабла за стандардне рекурзивне дискусије.

Стандардни рекурзивни алгоритам  DFS је:
* основни случај: ако је тренутни чвор нулл врати нетачно
* рекурзивни корак: иначе, проверите вредност текућег чвора, вратите тачно ако је погодак, у супротном рекурзија о деци.

У кратком споја, ово је уместо тога:
* проверити вредност текућег чвора и врати тачо ако је погодак
* иначе ако не нулл онда рекурзија. 
Што се тиче стандардних корака, ово покреће проверу базног случаја пред рекурзивним кораком. Алтернативно, они се могу сматрати другачијим обликом основног случаја и рекурзивним кораком. Имајте на уму да ово захтева омот функцију за руковање случај када је само стабло је празно (корен чвора је нулл).

У случају савршеног бинарог дрвета висине ''h,'' где је 2<sup>''h''+1</sup>&#x2212;1 чвор и 2<sup>''h''+1</sup> нулл показивачи као деца (2 за сваку од 2<sup>''h''</sup> лишћа), тако кратког споја смањује број позива функција на пола у најгорем случају.

У C, стандардни рекурзивни алгоритам може бити имплементиран као:<source lang="C">
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // base case
    else if (tree_node->data == i)
        return true;
    else
        return tree_contains(tree_node->left, i) ||
               tree_contains(tree_node->right, i);
}
</source>Алгоритам кратког споја може бити имплементиран као:<source lang="C">
// Wrapper function to handle empty tree
bool tree_contains(struct node *tree_node, int i) {
    if (tree_node == NULL)
        return false;  // empty tree
    else
        return tree_contains_do(tree_node, i);  // call auxiliary function
}

// Assumes tree_node != NULL
bool tree_contains_do(struct node *tree_node, int i) {
    if (tree_node->data == i)
        return true;  // found
    else  // recurse
        return (tree_node->left  && tree_contains_do(tree_node->left,  i)) ||
               (tree_node->right && tree_contains_do(tree_node->right, i));
}
</source>Обратите пажњу на употребу [[кратког споја евалуације]] боолеан && (И) оператори, тако да рекурзивни позив је направљен само ако је чвор важећи (не нулл). Имајте на уму да док је први термин  И представља показивач на чвор, други термин је инт, тако да је укупан израз процењује на боол. Ово је уобичајена идиом у рекурзивном кратком споју. Ово је поред евалуације кратког споја на Боолеан || (ИЛИ) оператер, да само проверите право дете ако је лево дете не успе. У ствари, цела контрола тока од ових функција може да се замени са једним буловом експресијом у саопштењу повратка, али читљивост пати без корисне ефикасности.

=== Хибридни алгоритам ===
Рекурзивне алгоритми су често неефикасни за мале податке, због графоскоп поновљених позива функција и повратак. Из тог разлога ефикасне имплементације алгоритама рекурзивних често почињу са рекурзивном алгоритма, али онда пребаците на други алгоритам када је улаз постане мали.. Важан пример је [[Спајање врсту|спајање врста]], која се често реализује преласком на не-рекурзивно [[Sortiranje umetanjem|убацивање врста]]  када се подаци довољно мали, као у [[Sortiranje spajanjem|поплочаној врсти спајања]]. Хибридна рекурзија алгоритма често може бити даље рафинирана, kao u [[Тимсорт]]у, изведене из хибридног стапања методу / уметања врсте

== Рекурзија у односу итерација ==
Рекурзија и итерација су подједнако изражајна: рекурзија може бити замењена итерацијом са експлицитним стеком, а итерација може бити замењена реп рекурзијом. Који приступ је пожељан зависи од проблема који се разматра и језика који се користи. У императивном програмирању, итерација је пожељна, посебно за једноставне рекурзије, јер избегава изнад функције позива и управљање  стеком, али рекурзије се углавном користе за вишеструке рекурзије. Насупрот томе, у функционалном језику рекурзија је пожељна, са репа рекурзије оптимизација доводи до мало изнад главе, а понекад експлицитна итерација није доступна.

Упоредите шаблоне за израчунавање x<sub>n</sub> дефинисано са x<sub>n</sub> = f(n, x<sub>n-1</sub>) од x<sub>base</sub>:
{| class=""
|-
| 
 function recursive(n)
     if n==base
         return x<sub>base</sub>
     else
         return f(n, recursive(n-1)) 
|
 function iterative(n)
     x = x<sub>base</sub>
     for i = n downto base
         x = f(i, x)
     return x
|}
За императивни језик плафон је дефинисати функцију, за функционални језик плафон је да се дефинише акумулатор променљиве x.

На пример, факторијална функција може да се итеративно имплементира у C доделом на индекс петље променљиве и акумулатор променљиве, уместо да пролази аргументе и враћа вредности од рекурзије:<source lang="C">
unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}
</source>

=== Изражајна моћ ===
Већина [[Програмски језик|програмских језика]] у употреби данас омогућавају директну спецификацију рекурзивних функција и процедура. Када се зове таква функција, програми [[runtime environment]] прати разних инстанци функције (често користећи [[позив стека]], иако могу да се користе друге методе). Свака рекурзивна функција може да се трансформише у итеративну функцију заменом рекурзивног позива са итеративним контролним конструкцијама  и симулира позив стека са [[Стек (апстрактни тип података)|стека]] експлицитно управља програмом.{{sfn|Hetland|2010|p=79}}{{sfn|Drozdek|2012|p=197}}

С друге стране, све итеративне функције и процедуре које могу бити оцењене од стране рачунара (погледајте [[Тјурингова потпуност]]) могу се изразити у смислу рекурзивних функција; итеративне контроле конструкције, као што су [[while петља]] и [[For петља|do петља]] су рутински преписани у рекурзивном облику
[[Функционално програмирање|функционалог језика]].<ref><cite class="citation web">Shivers, Olin. </cite></ref><ref><cite class="citation web">Lambda the Ultimate. </cite></ref> Међутим, у пракси то преписивање зависи од [[Tail call elimination|реп позива елиминација]]

, што није карактеристика свих језика. [[C (програмски језик)|C]], [[Јава (програмски језик)|Јава]], и [[Пајтон (програмски језик)|Пајтон]] су значајни језици на којим сви позиви функције, укључујући крајње позиве, јер стек расподела не би дошла уз коришћење петље конструкција; на тим језицима, радни понављачки програм преписан у рекурзивној форми може премашити позивни стек.

=== Проблеми са перформансама ===
У језицима (као што су [[C (програмски језик)|C]] и [[Јава (програмски језик)|Јава]]) који воле више итеративне петље конструкције, обично постоји значајан простор и време и трошкови повезани са рекурзивним програмима, због додатне потребне за управљање библиотеком и релативна спорост позива функција; у [[Функционално програмирање|функцијалним језицима]], функција позива (нарочито крајњи позив) је обично веома брз рад, а разлика је обично мање приметна.

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

=== Стек простор ===
У неким програмским језицима, стек простор доступан на теми је много мање од расположивог простора у гомили, а рекурзивни алгоритми имају тенденцију да захтевају више простора него стек итеративни алгоритам. Сходно томе, ови језици понекад ставе лимит на дубину рекурзије да се избегне стек преливања; [[Пајтон (програмски језик)|Пајтон]] је један такав језик.<ref><cite class="citation web">[https://docs.python.org/library/sys.html "27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation"]. </cite></ref> Обратите пажњу на упозорење испод о посебном случају реп рекурзије.

=== Вишеструки рекурзивни проблеми ===
Вишеструки рекурзивни проблеми су инхерентно рекурзивни, због ранијег стања морају да прате. Један пример је [[обилазак стабла]] као у [[Pretraga u dubinu|претрага у дубину]]; контраст са листе и линеарне претраге у листи, што је једнострука рекурзија и тако природно итеративна.

Други примери укључују [[Подели па владај (информатика)|подели па владај алгоритам]] као што су [[Квиксорт]], и функције као што су [[Акерманова функција]]. Све ове алгоритме можемо итеративно имплементирати, уз помоћ експлицитног [[Стек (апстрактни тип података)|стека]], али програмерски труд који је укључен у управљању стека и сложености добијеног програма, ће вероватно надмашити све предности итеративног решења.

== Функције репне рекурзије ==
Функције репне рекурзије су функције у којој сви рекурзивни позиви су [[реп позиви]] и стога не нагомилавају никакве одложене операције. На пример, gcd функција (показано опет испод
) је репно рекурзивна. Насупрот томе, факторијел функција (такође испод) није реп-рекурзивна; јер је његов рекурзиван позив '''није '''у позицији репа, темељи се одложена множења операције које се мора извршити након финални рекурзиви позив заврши.  Са [[компилатор|компајлером]] или [[тумачем]] који третира реп-рекурзивни позив као [[скокове]], пре него позив функције, реп-рекурзивна функција као што је gcd  ће се извршити помоћу сталног простора. Тако се програм суштински понавља, једнако користећи императивне контролне структуре језика као што су "for" и "while" петље.
{| class="wikitable"
|-
! [[Репна рекурзија|Tail recursion]]:
! Augmenting recursion:
|-
|<source lang="c">
//INPUT: Integers x, y such that x >= y and y > 0
int gcd(int x, int y)
{
  if (y == 0)
     return x;
  else
     return gcd(y, x % y);
}
</source>
|<source lang="c">
//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}
</source>
|}
Значај реп рекурзија је да приликом доношења реп-рецурзивног позива (или било ког реп позив), позивалац враћа положај не мора да се чува на позивном стеку; када рекурзивни позив врати, оне ће се гранати директно на претходно сачувану позицију повратка. Дакле, на језицима које признају ову имовину задњих позива, реп рекурзије штеди простор и време.  

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

=== Функција 1 ===
<source lang="c">
void recursiveFunction(int num) {
   printf("%d\n", num);
   if (num < 4)
      recursiveFunction(num + 1);
}
</source>[[Датотека:RecursiveFunction1_execution.png]]

=== Функција 2 са замењеним линијама ===
<source lang="c">
void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   printf("%d\n", num);
}
</source>[[Датотека:RecursiveFunction2_execution.png]]

== Временска ефикасност рекурзивног алгоритма ==
Временска ефикасност рекурзивног алгоритма може се изразити у односу на  враћање односа [[Велико О]]. Они могу (обично) се поједноставити у један
Big-Oh термин.

=== Правило пречице  (мајстор теорема) ===
Ако је време-комплексност функције је у виду

<math>T(n) = a \cdot T(n / b) + O(n ^ k)</math>

Затим Велико-О временске комплексности је овако:
* If <math>a > b^k</math>, онда временска комплексност је

 <math>O(n ^ {\log_b a})</math>
* If <math>a = b^k</math>, онда временска комплексност је <math>O(n ^ k \cdot \log n)</math>
* If <math>a < b^k</math>, онда временска комплексност је <math>O(n ^ k)</math>
где <math>a</math> представља број рекурзивних позива на сваком нивоу рекурзије, <math>b</math> представља по ономе фактор мањи улаз за следећи ниво рекурзије (тј број комада поделимо проблем у), и <math>n^k</math> представља рад функција не независна од било које рекурзије (нпр подела, комбинујући) на сваком нивоу рекурзије.

== Види још ==
* [[Функционално програмирање]]
* [[Хијерархијски и рекурзивни SQL упити Клине-Розер парадокс|Хијерархијски и рекурзивни SQL упити]]
* [[Клине-Розер парадокс]]
* [[Отворена рекурзија]]
* [[Рекурзија]]
* [[Крива Сјерпинског]]

=== Рекурзивне функције ===
* McCarthy 91 функција
* μ-рекурзивна функција
* Примитивна рекурзивна функција
* Tak (функција)

=== Књиге ===
* Structure and Interpretation of Computer Programs
* Walls and Mirrors

== Референце ==
{{reflist|30em}}

== Литература ==
{{Литература|2}}

* {{Cite book |ref= harv|last=Felleisen| first = Matthias  | contribution = Developing Interactive Web Programs  |year=2002| title = Advanced Functional Programming: 4th International School  |url= https://archive.org/details/springer_10.1007-b11942| editor-last=Jeuring| editor-first = Johan  | volume =  | place = Oxford, UK  | publisher = Springer  | id =  | postscript = <!--None--> |pages=[https://archive.org/details/springer_10.1007-b11942/page/n117 108] }}
* {{Cite book |ref= harv|last=Drozdek|first=Adam|title=Data Structures and Algorithms in C++|url=http://books.google.com/books?id=PRgLAAAAQBAJ&pg=PA197|year=2012|publisher=Cengage Learning|isbn=978-1-285-41501-7|pages=197}}
* {{Cite book |ref= harv|last=Hetland|first=Magnus Lie|title=Python Algorithms: Mastering Basic Algorithms in the Python Language|url=http://books.google.com/books?id=4cytGpIPYsAC&pg=PA79|year=2010|publisher=Apress|isbn=978-1-4302-3238-4|pages=79}}

{{Литература крај}}
=== Чланци ===
* {{cite journal|authorlink=Едсгер Дајкстра|last=Dijkstra|first=Edsger W.|year=1960|title=Recursive Programming|journal=Numerische Mathematik '''2''' (1)|doi=10.1007/BF01386232|pages=312–318}}

== Спољашње везе ==
* [http://www.ibm.com/developerworks/linux/library/l-recurs/index.html Jonathan Bartlett: "Mastering Recursive Programming"]
* [http://www.cs.cmu.edu/~dst/LispBook/ David S. Touretzky: "Common Lisp: A Gentle Introduction to Symbolic Computation"]
* [http://www.htdp.org/2003-09-26/Book/ Matthias Felleisen: "How To Design Programs: An Introduction to Computing and Programming"]
* [http://www.cs.duke.edu/~ola/ap/recurrence.html Owen L. Astrachan: "Big-Oh for Recursive Functions: Recurrence Relations"]

{{нормативна контрола}}

[[Категорија:Теорија рекурзије]]
[[Категорија:Рекурзије]]
[[Категорија:Теоријско рачунарство]]
[[Категорија:Програмске парадигме]]