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

Рекурзија у компјутерској науци је метод где решење проблема зависи од решења мањих случајева истог проблема (за разлику од итерација).^[1] Овај приступ се може применити на многе врсте проблема, а рекурзија је једна од централних идеја компјутерских наука.^[2]

Дрво створено коришћењем језика Лого и ослањајући се на рекурзију

"Снага рекурзије очигледно лежи у могућности дефинисања бесконачног низа објеката до коначног саопштења. На исти начин, бесконачан број израчунавања може се описати коначном рекурзијом програма, чак и ако тај програм не садржи изричита понављања."^[3]

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

Рекурзивне функције и алгоритми

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

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

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

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

Рекурзивни типови података

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

Индуктивно дефинисани подаци

Индуктивно дефинисан рекурзивни податак је онај који одређује како изградити пример података. На пример, повезана листа се може дефинисати индутивно (коришћењем Хаскелове синтаксе):

data ListOfStrings = EmptyList | Cons String ListOfStrings

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

Други пример индуктивне дефиниције је природан број (или позитивни цео број):

Природан број је 1 или n+1, где је n природан број.

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

 <expr> ::= <number>
          | (<expr> * <expr>)
          | (<expr> + <expr>)

Ово каже да је израз или број, производ два израза, или збир два израза. Рекурзија која се односи на изразе у другој и трећој линија, граматика дозвољава произвољно сложене аритметичке изразе као што су (5 * ((3 * 6) + 8)), са више од једног производа или збира операција у једном изражавању.

Коиндуктивно дефинисани подаци и корекурзија

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

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

Ток стрингова је објекат s тако да:
 глава(s) је стринг, а    
 реп(s) је ток стрингова.

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

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

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

Једнострука и вишеструка рекурзија

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

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

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

Индиректна рекурзија

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

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

Анонимна рекурзија

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

Структурна у односу на генеративне рекурзије

Неки аутори класификују рекурзију као "структурну" или "генеративну". Разлика се односи на који рекурзивни поступак добије податке на који ради, и како се обрађују те податке:

[Функције које конзумирају структурирани податак] обично разлаже своје аргументе у своје непосредне структурне компоненте, а затим обрађује те компоненте. Ако један од непосредних компоненти припада истој класи података као улаз, функција је рекурзивна. Из тог разлога, говоримо о овим функцијама као (структурно) рекурзивним функцијама.^[4]

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

Генеративна рекурзија је алтернатива. Многи познати рекурзивни алгоритми генеришу потпуно нови податак из датих података и враћамо на њу. HtDP (Како осмислити програм) се односи на ову врсту као генеративне рекурзије. Примери генеративних рекурзија укључују Еуклидов алгоритам, квиксорт, бинарна претрага, сортирање са спајањем, Њутнова метода, фрактал, и прилагодљива интеграција.^[5]

Ова разлика је важна за доказивање престанка функције.

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

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

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

Факторијел

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

\operatorname {fact} (n)={\begin{cases}1&{\mbox{if }}n=0\\n\cdot \operatorname {fact} (n-1)&{\mbox{if }}n>0\\\end{cases}}

Псеукод (рекурзивно:

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

Функција се може записати и као рекурзивни однос:

b_{n}=nb_{n-1}

b_{0}=1

Ова процена понављања односа показује рачунање које ће се обавити у процени Псеудокода изнад:

Израчунавање понављања односа за n = 4:
b₄ = 4 * b₃ = 4 * (3 * b₂) = 4 * (3 * (2 * b₁)) = 4 * (3 * (2 * (1 * b₀))) = 4 * (3 * (2 * (1 * 1))) = 4 * (3 * (2 * 1)) = 4 * (3 * 2) = 4 * 6 = 24

Ова функција факторијела може бити описана без употребе рекурзије тако што користе типичне петље конструкције које се налазе у императивним програмским језицима:

Псеукод (итеративно)

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

Императив код изнад је еквивалент за ову математичку дефиницију користећи акумулациону роменљиву $t$ :

{\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}}

Дефиниција изнад директно преводи функционалним програмским језиком као што су Шеме; ово је пример итерације која се спроводи рекурзивно.

Највећи заједнички делилац

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

Дефиниција функције:

\gcd(x,y)={\begin{cases}x&{\mbox{if }}y=0\\\gcd(y,\operatorname {remainder} (x,y))&{\mbox{if }}y>0\\\end{cases}}

Псеукод (рекурзивно):
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

Понављање односа за највећи заједнички делилац $x\%y$ изражава остатак од $x/y$ :

\gcd(x,y)=\gcd(y,x\%y)

if

y\neq 0

\gcd(x,0)=x

Израчунавање понављања односа за 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 и коришћење конструктивне петље, програм избегава доношење рекурзивних позива и расте позив стека.

Псеукод (итеративно):

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

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

Ханојска кула

Ханои кула

Ханојска кула је математичка загонетка чије решење илуструје рекурзију.^[1]^[2] Постоје три штапа који могу да чувају гомилу дискова различитих пречника. Већи диска никад не може бити сложен на врху мањег. Почевши са н дисковима на једном штапу, они морају бити премештени на други штап један по један. Који је најмањи број корака да бисте померили све?

Дефиниција функције:

\operatorname {hanoi} (n)={\begin{cases}1&{\mbox{if }}n=1\\2\cdot \operatorname {hanoi} (n-1)+1&{\mbox{if }}n>1\\\end{cases}}

Понављање односа за ханои:

h_{n}=2h_{n-1}+1

h_{1}=1

Израчунавање понављања односа за n = 4:
hanoi(4) = 2hanoi(3) + 1 = 2(2hanoi(2) + 1) + 1 = 2(2(2hanoi(1) + 1) + 1) + 1 = 2(2(21 + 1) + 1) + 1 = 2(2(3) + 1) + 1 = 2(7) + 1 = 15

Пример имплементације:

Псеукод (рекурзивно):
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

Иако нису сви рекурзивне функције имају експлицитан решење, Ханојска кула секвенца може да се сведе на експлицитне формуле .^[2]

Експлицитна формула за Ханои кулу:
h₁ = 1 = 2¹ - 1 h₂ = 3 = 2² - 1 h₃ = 7 = 2³ - 1 h₄ = 15 = 2⁴ - 1 h₅ = 31 = 2⁵ - 1 h₆ = 63 = 2⁶ - 1 h₇ = 127 = 2⁷ - 1 In general: h_n = 2ⁿ - 1, for all n >= 1

Бинарна претрага

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

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

Пример имплементације бинарне претраге у 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);
 }

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

Важна примена рекурзије у компјутерсој науци је у дефинисању динамичке структуре података као што су листе и стабла. Рекурзивне структуре података могу динамички расти до теоретски бесконачне величине као одговор на почетне захтеве; насупрот томе, величина статичког низа мора бити постављена на компајлирање. Рекурзивни алгоритми су посебно одговарајући када се основни проблем или податак који се третира, дефинисани у рекурзивним условима.^[3]

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

Докле год програмер произилази образац из дефиниције података, функција запошљава структурну рекурзију. То јест рекурзија у функцијском телу троши непосредни део дате вредности.^[6]

Повезана листа

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

struct node
{
  int data;           // some integer data
  struct node *next;  // pointer to another struct node
};

Зато што је struct node структура података рекурзивно се дефинишу процедуре које послују на њему, могу да се реализују као природно рекурзивне процедуре. Поступак list_print дефинисан у даљем тексту шетња кроз листу док је листа празна (тј показивач листе има вредност НУЛЛ)..

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

Бинара стабла

Испод је једноставна дефиниција за бинарно стабло чвора. Као чвориште за повезане листе, што је дефинисано у смислу себе, рекурзивно. Постоје два самореференцијална показивача: лево (показујући на лево под-стабло) и право (показујући надесно под-стабло).

struct node
{
  int data;            // some integer data
  struct node *left;   // pointer to the left subtree
  struct node *right;  // point to the right subtree
};

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

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

Највише два рекурзивна позива ће бити направљена за сваки дати позив на tree_contains како је горе дефинисано.

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

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

Filesystem traversal

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

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

}

Овај код спаја линије, барем донекле, између рекурзије и понављања. То је, у суштини, рекурзивна имплементација, што је најбољи начин за прелазак фајлс истема. Такође је пример директне и индиректне рекурзије. Метод "rtraverse" је чисто директан пример; метод "traverse" је индиректан, којом се позива "rtraverse." Овај пример треба "основни случај" сценарио с обзиром на чињеницу да ће увек бити неки фиксни број датотека или директоријума у датом фајл систему.

Питања имплементације

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

Омот функција (на врху)
Кратким спајањем основног случаја, звани "рука- дужина рекурзије" (при дну)
Хибрид алгоритма (на дну) - пребацивање на други алгоритам довољно малих података

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

Омот функција

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

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

Кратко спајање основног случаја

Кратко спајање основног случаја, познатије као рука- дужина рекурзије, састоји се од провере основног случаја пре него што рекурзивно позове – односно провера да ли следећи позив ће бити основа случаја, уместо позива, а затим проверава за основни случај. Кратки спој је посебно учинио за ефикасност разлога, да се избегне изнад главе једног позива функције која се одмах враћа.. Имајте на уму да, пошто основни случај већ проверава (непосредно пре рекурзивног корака), не треба да буде проверен одвојено, али не треба да се користи омот функција у случају када је укупна рекурзија почиње са основним случајем. На пример, у факторијел функцији, правилни основни случај је 0! = 1, док одмах враћа 1 за 1! за кратки спој, и може пропустити 0; ово се може ублажити и у омот функцији.

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

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

Дубина прве претраге

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

Стандардни рекурзивни алгоритам DFS је:

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

У кратком споја, ово је уместо тога:

проверити вредност текућег чвора и врати тачо ако је погодак
иначе ако не нулл онда рекурзија.

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

У случају савршеног бинарог дрвета висине h, где је 2^h+1−1 чвор и 2^h+1 нулл показивачи као деца (2 за сваку од 2^h лишћа), тако кратког споја смањује број позива функција на пола у најгорем случају.

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

Алгоритам кратког споја може бити имплементиран као:

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

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

Хибридни алгоритам

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

Рекурзија у односу итерација

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

Упоредите шаблоне за израчунавање x_n дефинисано са x_n = f(n, x_n-1) од x_base:

function recursive(n)
    if n==base
        return x_base
    else
        return f(n, recursive(n-1))

function iterative(n)
    x = x_base
    for i = n downto base
        x = f(i, x)
    return x

За императивни језик плафон је дефинисати функцију, за функционални језик плафон је да се дефинише акумулатор променљиве x.

На пример, факторијална функција може да се итеративно имплементира у C доделом на индекс петље променљиве и акумулатор променљиве, уместо да пролази аргументе и враћа вредности од рекурзије:

unsigned int factorial(unsigned int n) {
  unsigned int product = 1; // empty product is 1
  while (n) {
    product *= n;
    --n;
  }
  return product;
}

Изражајна моћ

Већина програмских језика у употреби данас омогућавају директну спецификацију рекурзивних функција и процедура. Када се зове таква функција, програми runtime environment прати разних инстанци функције (често користећи позив стека, иако могу да се користе друге методе). Свака рекурзивна функција може да се трансформише у итеративну функцију заменом рекурзивног позива са итеративним контролним конструкцијама и симулира позив стека са стека експлицитно управља програмом.^[7]^[8]

С друге стране, све итеративне функције и процедуре које могу бити оцењене од стране рачунара (погледајте Тјурингова потпуност) могу се изразити у смислу рекурзивних функција; итеративне контроле конструкције, као што су while петља и do петља су рутински преписани у рекурзивном облику функционалог језика.^[9]^[10] Међутим, у пракси то преписивање зависи од реп позива елиминација

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

Проблеми са перформансама

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

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

Стек простор

У неким програмским језицима, стек простор доступан на теми је много мање од расположивог простора у гомили, а рекурзивни алгоритми имају тенденцију да захтевају више простора него стек итеративни алгоритам. Сходно томе, ови језици понекад ставе лимит на дубину рекурзије да се избегне стек преливања; Пајтон је један такав језик.^[11] Обратите пажњу на упозорење испод о посебном случају реп рекурзије.

Вишеструки рекурзивни проблеми

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

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

Функције репне рекурзије

Функције репне рекурзије су функције у којој сви рекурзивни позиви су реп позиви и стога не нагомилавају никакве одложене операције. На пример, gcd функција (показано опет испод ) је репно рекурзивна. Насупрот томе, факторијел функција (такође испод) није реп-рекурзивна; јер је његов рекурзиван позив није у позицији репа, темељи се одложена множења операције које се мора извршити након финални рекурзиви позив заврши. Са компајлером или тумачем који третира реп-рекурзивни позив као скокове, пре него позив функције, реп-рекурзивна функција као што је gcd ће се извршити помоћу сталног простора. Тако се програм суштински понавља, једнако користећи императивне контролне структуре језика као што су "for" и "while" петље.

Tail recursion:

Augmenting recursion:

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

//INPUT: n is an Integer such that n >= 0
int fact(int n)
{
   if (n == 0)
      return 1;
   else
      return n * fact(n - 1);
}

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

Редослед извршавања

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

Функција 1

void recursiveFunction(int num) {
   printf("%d\n", num);
   if (num < 4)
      recursiveFunction(num + 1);
}

Функција 2 са замењеним линијама

void recursiveFunction(int num) {
   if (num < 4)
      recursiveFunction(num + 1);
   printf("%d\n", num);
}

Временска ефикасност рекурзивног алгоритма

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

Правило пречице (мајстор теорема)

Ако је време-комплексност функције је у виду

$T(n)=a\cdot T(n/b)+O(n^{k})$

Затим Велико-О временске комплексности је овако:

If $a>b^{k}$ , онда временска комплексност је

 $O(n^{\log _{b}a})$

If $a=b^{k}$ , онда временска комплексност је $O(n^{k}\cdot \log n)$
If $a<b^{k}$ , онда временска комплексност је $O(n^{k})$

где $a$ представља број рекурзивних позива на сваком нивоу рекурзије, $b$ представља по ономе фактор мањи улаз за следећи ниво рекурзије (тј број комада поделимо проблем у), и $n^{k}$ представља рад функција не независна од било које рекурзије (нпр подела, комбинујући) на сваком нивоу рекурзије.

Види још

Рекурзивне функције

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

Књиге

Structure and Interpretation of Computer Programs
Walls and Mirrors

Референце

^ ^а ^б Graham, Knuth & Patashnik 1990.
^ ^а ^б ^в Epp 1995
^ ^а ^б Wirth 1976
^ Felleisen, Matthias; Robert Bruce Findler; Matthew Flatt; Shriram Krishnamurthi (2001).
^ Felleisen 2002, стр. 108. sfn грешка: више циљева (2×): CITEREFFelleisen2002 (help)
^ Felleisen, Matthias (2002). „Developing Interactive Web Programs”. Ур.: Jeuring, Johan. Advanced Functional Programming: 4th International School. Oxford, UK: Springer. стр. 108.
^ Hetland 2010, стр. 79.
^ Drozdek 2012, стр. 197.
^ Shivers, Olin.
^ Lambda the Ultimate.
^ "27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation".

Литература

Felleisen, Matthias (2002). „Developing Interactive Web Programs”. Ур.: Jeuring, Johan. Advanced Functional Programming: 4th International School. Oxford, UK: Springer. стр. 108.
Drozdek, Adam (2012). Data Structures and Algorithms in C++. Cengage Learning. стр. 197. ISBN 978-1-285-41501-7.
Hetland, Magnus Lie (2010). Python Algorithms: Mastering Basic Algorithms in the Python Language. Apress. стр. 79. ISBN 978-1-4302-3238-4.

Чланци

Dijkstra, Edsger W. (1960). „Recursive Programming”. Numerische Mathematik 2 (1): 312—318. doi:10.1007/BF01386232.

Спољашње везе

[FOOTNOTEGrahamKnuthPatashnik1990-1] а ^б Graham, Knuth & Patashnik 1990.

[automatski_generisano2-2] а ^б ^в Epp 1995

[automatski_generisano1-3] а ^б Wirth 1976

[Felleisen_HtDP_2001-4] Felleisen, Matthias; Robert Bruce Findler; Matthew Flatt; Shriram Krishnamurthi (2001).

[FOOTNOTEFelleisen2002108-5] Felleisen 2002, стр. 108. sfn грешка: више циљева (2×): CITEREFFelleisen2002 (help)

[Felleisen_2002_108-6] Felleisen, Matthias (2002). „Developing Interactive Web Programs”. Ур.: Jeuring, Johan. Advanced Functional Programming: 4th International School. Oxford, UK: Springer. стр. 108.

[FOOTNOTEHetland201079-7] Hetland 2010, стр. 79.

[FOOTNOTEDrozdek2012197-8] Drozdek 2012, стр. 197.

[9] Shivers, Olin.

[10] Lambda the Ultimate.

[11] "27.1. sys — System-specific parameters and functions — Python v2.7.3 documentation".

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]