Репна рекурзија у информатици је подрутински позив као финална акција процедуре. Ако би репна рекурзија могла довести до исте подрутине која је позвана поново касније у ланцу позива, за подрутину се каже да је репно-рекурзивна, што је посебан случај рекурзије. Репна рекурзија (или реп-крај рекурзија) је делимично корисна и често лако подношљива у имплементацијама.
Репне рекурзије могу бити реализоване без додавања новог стек оквира да би се позвао стек. Већина оквира тренутне процедуре није потребна, и може бити замењен оквиром репа рекурзије, модификован по потреби (слично преклапању за процесе, али за позиве функција). Програм може скочити на позвану подрутину. Производња оваквог код уместо стандардног позива секвенце се назива елиминација репне рекурзије. Елиминација репне рекурзије омогућује позивима процедуре у позицији репа да буду ефикасни као gоТо наредбе, што омогућује ефикасно структурно програмирање. У речима Гај Л. Стила, "у генералној процедуру позиви могу се сматрати корисним као GOTO наредбе који такође пролазе и параметре, и може бити равномерно кодиран као [код машине] JUMP инструкција".
Традиционално, елиминација репне рекурзије је опционална. Међутим, функционалним програмским језицима, елиминација репне рекурзије је често загарантована преко стандарда језика и ова гаранција омогућује коришћење рекурзије, посебно репа рекурзије, уместо петљи. У таквим случајевима, није тачно (али може бити по жељи) да се односи на њега као на оптимизацију. Специјалан случај репних позива рекурзије, када функција позове саму себе, може бити подложнија да позове елиминацију него позив главног репа.
Опис Када се функција позове, рачунар мора „запамтити“ место са ког је позван, повратна адреса, тако да се може вратити на локацију са резултатом онда када је позив завршен. Типично, ова иформација је сачувана на гомили позива, једноставна листа враћених локација поређаних по достигнутим локацијама које су описане. За репне рекурзије, није потребно да запамтимо место са којег их зовемо- уместо тога, може урадити елиминацију репне рекурзије остављајући гомилу саму (могуће је осим аргумената функција и локалних варијабли ) и ново позвана функција ће вратити њен резултат директно право позивачу. Имати на уму да репна рекурзија не мора да се појави лексички после свих наредби у изворном коду; само је важно да се позвана функција врати одмах након позива репне рекурзије, враћа репну рекурзију ако постоји, пошто позив функције неће добити шансу да уради било шта након што се оптимизација изведе.
За нерекурзивне фунционе позиве, ово је обично оптимизацију која чува мало времена и места, пошто не постоје много различитих функција за позивање. Када имате посла са рекурзивним или обостраним рекурзивним функцијама где се рекурзија дешава кроз реп рекурзије, међутим, гоимла простора и број сачуваних повратка може нарасти да буде веома значајан, пошто функција може да позове саму себе, директно или индиректно, стварајући нову гомилу позива приликом сваког понављања. У ствари, често асимптотски смањује захтеве гомиле простора са линеарног, или О(n), на константно, О(1), Елиминација репне рекурзије је често захтевана од стране стандардних дефиниција неких програмски језика, као што је Scheme , и језици из ML породице. У случају Scheme, дефиниција језика формализује интуитивни појам репне рекурзије тачно, наводећи које синтаксне форме дозвољавају поседовање резултата у контексту репа. Имплементације дозвољавају бесконачан број репних рекурзија да буду активне у исто време, захваљујући елиминацији репне рекурзије, може се такође звати "правилна репна рекурзија".
Поред ефикасности простора и извршавања, елиминација репне рекурзије је важна у функционалном програмирању идиом познат као наставак пролазног стила (CPS), који би у супротном брзо остао без гомиле простора.
Форма синтаксе Репна рекурзија може бити лоцирана пре синтаксног краја подрутине:Afunction foo(data) { a(data); return b(data); }Овде, a(data) иb(data) су позиви, али b је последња ствар коју процедура извршава пре враћања и налази се у репној позицији. Међутим, нису све репне рекурзије обавезно лоцијара не синтаксном крају подрутине. Размотрити: function bar(data) { if ( a(data) ) { return b(data);
return c(data); }Овде, оба позива на b и c су у репној позицији. Ово је зато што сваки од њих лежи на крају if-гране редом, иако први није синтасно на крају barтела.
Сада размотрити овај код:function foo1(data) { return a(data) + 1; }function foo2(data) { var ret = a(data); return ret; }function foo3(data) { var ret = a(data); return (ret == 0) ? 1 : ret; }Овде, позив на a(data) је у репној позицију у foo2, али није у репној позицији такође у foo1 или у foo3, зато што контрола мора да врати позивачу да дозовли да испита или модификује враћену вредност пре него што га врати.
Example programs Видети овај Scheme програм као пример:;; факторијел : број -> број ;; да калкулише продукт свих позитива ;; цели бројеви мањи или једнаки n. (define (factorial n) (if (= n 0) 1 (* n (factorial (- n 1)))))Програм изнад није написан у стилу репне рекурзије, зато што ознака ("*") је у позицији репа. Сада погледати овај Scheme програм као пример:;; факторијел : број -> број ;; да калкулише продукт свих позитива ;; цели бројеви мањи или једнаки n. (define (factorial n) (let fact ([i n] [acc 1]) (if (zero? i) acc (fact (- i 1) (* acc i)))))Унутрашњи поступак fact позива саму себе последњу у контроли тока. Ово дозвољава интерпретатору или компилатору да реорганизује извршавање које би обично изгледало овако: call factorial (3) call fact (3 1) call fact (2 3) call fact (1 6) call fact (0 6) return 6 return 6 return 6 return 6 return 6 у ефикаснију варијанту, у користи времену и простору call factorial (3) call fact (3 1) replace arguments with (2 3) replace arguments with (1 6) replace arguments with (0 6) return 6 return 6 Реорганизација чува простор зато што ниједна изјава осим позива адреса функције не треба да се сачува, или на стаку или на гомили и оквир позива стека заfact се поново користи за средњи резултат складиштења. Ово такође значи да програмер не треба да брине да ће да му нестане простора за екстремно дубоке рекурзије. Такође ништа не значи да, при типичним имплементацијама, варијанте репа рекурзије ће бити знатно бржа него друга варијанта, али само преко константног фактора.
Неки програмери који раде са функционалним језицима би поново написали рекурзиван код да буде репно-рекурзиван тако да би могли да узму корист од ове особине. Ово често захтева додатак "акумулатор" аргумента (acc у пређашњем примеру) функцији. У неким случајевима (као што је филтеровање листе) и у неким језицима, цела репна рекурзија може захтевати функцију која је претходно потпуно функционална да буде записана тако да мутира референце сачуване у осталим варијаблама.
Репна рекурзија против модула Репна рекурзија против модула је генерализација репне рекурзије оптимизације представљена од стране Давида Х. ВоренаD. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980. у контексту компилација Пролога, виђен као експлицитни језик постови једном. Описано је (али не и именовано) од стране Данијела П. Фридмана и Давида С. Вајса 1974Daniel P. Friedman and David S. Wise, Technical Report TR19: Unwinding Structured Recursions into Iterations , Indiana University, Dec. 1974. као LISP честа техника. Као што име наговештава, односи када једина операција које је остала понаша се као репна рекурзија да предвиди познату вредност испред листе враћене од њега (или да уради константан број једноставне операције конструкције-података, у главном). Овај позив би био реп рекурзије који спашава за cons операцију. Али вредност префикса на почетку листе на крају од рекурзивног позива је исто као и додавање ове вредност на крају растуће лист на улазу у рекурзивни позив, градећи листу као споредни ефекат, као имплицитни параметар акумулатора. Следећи фрагмет Пролога показује тај концепт: % репно рекурзивни модул константе: partition([], _, [], []). partition([X|Xs], Pivot, [X|Rest], Bigs) :- X @< Pivot, !, partition(Xs, Pivot, Rest, Bigs). partition([X|Xs], Pivot, Smalls, [X|Rest]) :- partition(Xs, Pivot, Smalls, Rest). -- У Хаскелу, чувана рекурзија: partition [] _ = ([],[]) partition (x:xs) p | x < p = (x:a,b) | otherwise = (a,x:b) where (a,b) = partition xs p% Са експлицитним унификацијама: % не-петљани рекурзивни превод: partition([], _, [], []). partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs], ( X @< Pivot -> partition(Xs,Pivot,Rest,Bigs), Smalls=[X|Rest] ; partition(Xs,Pivot,Smalls,Rest), Bigs=[X|Rest] ). % рекурзивна петља превода: partition([], _, [], []). partition(L, Pivot, Smalls, Bigs) :- L=[X|Xs], ( X @< Pivot -> Smalls=[X|Rest], partition(Xs,Pivot,Rest,Bigs) ; Bigs=[X|Rest], partition(Xs,Pivot,Smalls,Rest) ). Тако у преводу репне рекурзије је трансформисан прво у претварање новог чвора листе и постављање first поља и онда прављење репне рекурзија са показивачем чвора rest поља као аргумент, да буде испуњен рекурзивно.
Као још један пример, размотрити рекурзивну функцију у С која дуплира линковану листу: list *duplicate(const list *ls)
list *head = NULL;
if (ls != NULL) { list *p = duplicate(ls->next); head = malloc(sizeof *head); head->value = ls->value; head->next = p;
return head; } ;; у Scheme, (define (duplicate ls) (if (not (null? ls)) (cons (car ls) (duplicate (cdr ls))) '()))%% у Прологу, dup([X|Xs],[X|Ys]):- dup(Xs,Ys).
dup([],[]). У овој форми фунцкија није репно рекурзивна, зато што се контрола враћа позивачу после рекурзивног позива, дуплира остатак уноса листе. Чак иако би се доделила глава чвора пре дуплирања остатка, идаље би било потребно прикључити резултати рекурзивног позива у next поље после позива..[lower-alpha 1] Тако да је функција скоро репно-рекурзивна. Варенов метод одстрањује одговорност попуњавањаnext поља у рекурзивни позив сам од себе, чиме постаје реп рекурзије: list *duplicate(const list *ls)
list head; duplicate_aux(ls, &head); return head.next;
void duplicate_aux(const list *ls, list *end)
if (ls != NULL) { end->next = malloc(sizeof *end); end->next->value = ls->value; duplicate_aux( ls->next, end->next); } else { end->next = NULL;
};; у Scheme, (define (duplicate ls) (let ((head (list 1))) (let dup ((ls ls) (end head)) (if (not (null? ls)) (begin (set-cdr! end (list (car ls))) (dup (cdr ls) (cdr end))))) (cdr head)))%% у Прологу, dup([X|Xs],R):- R=[X|Ys], dup(Xs,Ys).
dup([],[]). Имати на уму како сада позиваоц расте до краја растуће листе, радије него да позивач падне на почетак враћене листе. Посао је сада готов на путу напред од почетка листе, пре рекурзивног позива који касније наставља даље, назад од краја листе, после рекурзивног позива враћа свој резултат. Стога је сличан техници акумулације параметра, која претвара рекурзивно рачунање у итерационо .
Карактеристично за ову технику, родитељски оквир је креирао на извршењу позива стека, што позива позиваоца репне рекурзције који може поново користити свој позивни овир ако је репна ракурзија оптимизована у садашњности.
Правилна имплементација репа рекурзије може сада бити претворена у екплицитну итеративну форму, нпр. акумулациона петља: list *duplicate(const list *ls)
list head, *end; end = &head; while (ls != NULL)
end->next = malloc(sizeof *end); end->next->value = ls->value; ls = ls->next; end = end->next;
end->next = NULL; return head.next; } ;; у Scheme, (define (duplicate ls) (let ((head (list 1))) (do ((end head (cdr end)) (ls ls (cdr ls ))) ((null? ls) (cdr head)) (set-cdr! end (list (car ls))))))
Историја