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

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

Репне рекурзије могу бити реализоване без додавања новог стек оквира да би се позвао стек. Већина оквира тренутне процедуре није потребна, и може бити замењен оквиром репа рекурзије, модификован по потреби (слично преклапању за процесе, али за позиве функција). Програм може скочити на позвану подрутину. Производња оваквог код уместо стандардног позива секвенце се назива елиминација репне рекурзије. Елиминација репне рекурзије омогућује позивима процедуре у позицији репа да буду ефикасни као gоТо наредбе, што омогућује ефикасно структурно програмирање. У речима Гај Л. Стила, "у генералној процедуру позиви могу се сматрати корисним као GOTO наредбе који такође пролазе и параметре, и може бити равномерно кодиран као [код машине] JUMP инструкција".[1]

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

Опис

Када се функција позове, рачунар мора „запамтити“  место са ког је позван, повратна адреса, тако да се може вратити на локацију са резултатом онда када је позив завршен. Типично, ова иформација је сачувана на гомили позива, једноставна листа враћених локација поређаних по достигнутим локацијама које су описане. За репне рекурзије, није потребно да запамтимо место са којег их зовемо- уместо тога, може урадити елиминацију репне рекурзије остављајући гомилу саму (могуће је осим аргумената функција и локалних варијабли [2]) и ново позвана функција ће вратити њен резултат директно право позивачу. Имати на уму да репна рекурзија не мора да се појави лексички после свих наредби у изворном коду; само је важно да се позвана функција врати одмах након позива репне рекурзије, враћа репну рекурзију ако постоји, пошто позив функције неће добити шансу да уради било шта након што се оптимизација изведе.

За нерекурзивне фунционе позиве, ово је обично оптимизацију која чува мало времена и места, пошто не постоје много различитих функција за позивање. Када имате посла са рекурзивним или обостраним рекурзивним функцијама где се рекурзија дешава кроз реп рекурзије, међутим, гоимла простора и број сачуваних повратка може нарасти да буде веома значајан, пошто функција може да позове саму себе, директно или индиректно, стварајући нову гомилу позива приликом сваког понављања. У ствари, често асимптотски смањује захтеве гомиле простора са линеарног, или О(n), на константно, О(1), Елиминација репне рекурзије је често захтевана од стране стандардних дефиниција неких програмски језика, као што је Scheme ,[3][4] и језици из ML породице. У случају Scheme, дефиниција језика формализује интуитивни појам репне рекурзије тачно, наводећи које синтаксне форме дозвољавају поседовање резултата у контексту репа. Имплементације дозвољавају бесконачан број репних рекурзија да буду активне у исто време, захваљујући елиминацији репне рекурзије, може се такође звати "правилна репна рекурзија".[3]

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

Форма синтаксе

Репна рекурзија може бити лоцирана пре синтаксног краја подрутине:A

function 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 у пређашњем примеру) функцији. У неким случајевима (као што је филтеровање листе) и у неким језицима, цела репна рекурзија може захтевати функцију која је претходно потпуно функционална да буде записана тако да мутира референце сачуване у осталим варијаблама.

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

Репна рекурзија против модула је генерализација репне рекурзије оптимизације представљена од стране Давида Х. Ворена[5] у контексту компилација Пролога, виђен као експлицитни језик постови једном. Описано је (али не и именовано) од стране Данијела П. Фридмана и Давида С. Вајса 1974[6] као 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))))))

Историја

У папиру донетом АЦМ конференцији у Сиетлу 1977. године, Гај Л. Стили укртко је сумирао дебату око goTo и структурног програмирања и посматрао је позиве процедуре у репној рекурзији које могу бити најбоље третиране као директан трансфер контроле до позване процедуре, типично елеминишући непотребне гомиле манипулативних операција .[1] Пошто су такви "репни позиви" чести у Lisp-у, језик у коме су позиви процедура свеприсутни, ова форма оптимизације значајно смањује цену позива процеду поређеним са осталим имплементацијама. Стили је расправљао да су лоше имплементовани позиви процедуре довели до вештачке перцепције да је GOTO  јефтин у поређењу са позивом процедуре. Стили се даље расправљао да "у главном позиви процедура могу бити корисно мишљење GOTO наредби које такође пролазе параметре, и може бити равномерно кодиран као[код машине] JUMP инструкција", са стаком кода машине манипулација инструкција "се сматра оптимизацијом (више него обрнуто)".[1] Стили је цитирао доказ да добро оптимизовани нумерички алгоритми у Lisp-у могу извршити брже него код произведен преко доступне рекламе Фортран компајлера, зато што је цена позива процедуре у Lisp-у много јефтинија. У Scheme, Lisp-ов диалект развијен од стране Стилија са Гералдом Џеј Сусманом,|Гералдом Џеј Сусманом, елиминација репа рекурзије је гарантована да је имплементована у било који интерпретер[7]

Методе имплементације

Репна рекурзија је важна приликом неких програмских језика високог нивоа, специјално функционалних и логичких језика и чланова Lisp породице. У овим језицима, репна рекурзија је најшће коришћена преко (и понекад једини могући начин) имплементације понављања. Спецификација језика Scheme захтева да репне рекурзије буду оптимизоване како не би повећавале стек. Репне рекурзије могу бити експлицитне у Перлу, преко варијанте "goto" наредбе која узима име функције: goto &NAME;[8]

Имплементација елиминације репне рекурзије само за реп рекурзије, пре него за све позиве репа, је нешто значајно лакше. На пример, у Јавиној Виртуалној Машини(ЈВМ), репно-рекурзивни позиви могу бити елиминисани (јер то преузима постојећи позив стека), али углавном репне рекурзије не могу бити (јер ово мења позив стека).[9][10] Као резултат, функционални језици као што је Скала који циљају ЈВМ могу ефикасно имплементовати директно репрну рекурзију, али не узајамну репну рекурзију.

Различите методе имплементације су доступне.

У асемблеру

Репне рекурзије су често оптимизоване од стране интерпретатора и компилатора од функционалних и логичких програмирања језика како би биле ефикасније форме итерације. На пример, Scheme програмери често изражавају while петље као позив на проведу у репној позицији и ослањају се на комплитаор или интерпретатор Scheme како би заменио репне рекурзије са ефикаснијим скок инструкцијама.[11]

За компилаторе који генералишу асемблер директно, елиминација репне рекурзије је лака: довољно је да замени операциони позив са скоком, после порављања параметра на стеку. Из перспективе компилатора, први пример иза је иницијално преведен у псеудо-асемблер језику(у ствари ово је x86 асемблер валидно) :

 foo:
  call B
  call A
  ret

Елиминација репне рекурзије мења два реда са једном скок инструкцијом:

 foo:
  call B
  jmp  A

Пошто се подрутина A заврши, она ће се вратити директно враћеној адреси foo, избегавањем непотребне ret наредбе.

Типично, позвана подрутина мора бити снабдевана парамтерима.  Остварени код се мора уверити да је позивни оквир за  А  правилно постављен пре скока на репно-позвану подрутину. На пример, на платформама где позив стека не садржи повратну адресу, али такође параметре за подрутину, комплитаор ће можда морати да емитује инструкције да би прилагодио позив стека. На таквој платформи, размотрити код: 

function foo(data1, data2)
   B(data1)
   return A(data2)

где data1 и data2 су параметри. Компилатор може превести то у следећи псеудо асемблер код:[а]

 foo:
   mov  reg,[sp+data1] ; доноси data1 из стека (сп) параметра у изгребан регистар.
   push reg            ; ставља data1 на стек где B очекује то
   call B              ; B користи data1
   pop                 ; брише data1 из стека
   mov  reg,[sp+data2] ; доноси data2 из стека (sp) параметра у изгребан регистар.
   push reg            ; ставља data2 на стек где A очекује то
   call A              ; A користи data2
   pop                 ; брише data2 из стека.
   ret

Оптимизер репне рекурзије може променити код у:

 foo:
   mov  reg,[sp+data1] ; доноси data1 из стека (сп) параметра у изгребан регистар.
   push reg            ; ставља data1 на стек где B очекује то
   call B              ; B користи data1
   pop                 ; брише data1 из стека
   mov  reg,[sp+data2] ; доноси data2 из стека (sp) параметра у изгребан регистар.
   mov  [sp+data1],reg ; ставља data2 на стек где A очекује то
   jmp  A              ;A користи data2 и враћа одмах позивачу

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

Кроз трамполининг

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

Могуће је убацити трамолиновање користећи функције вишег реда у језицима који их подржавају , као што су Груви, Вижуал Бејсик .Net и С#.[12]

Користећи трамполин за све позиве функције је доста скупље него нормални С позиви, тако да најмање један Scheme компилатор, Кокошка, користи технику коју је први описао Хенри Бејкер у необјављеној сугестији Ендру Апела,[13] у којој нормални С позиви се користе али величина стека је проверена пре сваког позива. Када стек достигне максимум дозвољене величине, објекти стека су покупљено ђубре коришћењем Ченеј алгоритмом померајући све живе податке у одвојену гомилу. Пратећи ово, стек је одмотан ("пао") у и програм наставља са сачуваног стања пре колекције смећа. Бејкер каже "Апелов  метод избегава прављење великог броја малих одбитака трамполине привременим скоковима са Емпајер Стејт Зграде"[13] Колекција смећа проверава да ли узајамна репрна рекурзија наставља у да ради у бесконачност. Међутим, овај приступ захтва да се ниједан С позив функције враћа, пошто не постоји гаранција да оквир позивача идаље постоји; због тога, то укључује драматичније унутрашње преписивање програмског кода:стил наставка-пролаза.

Однос према while конструкцији

Репна рекурзија може бити повезана са while оператором контроле тока путем трансформације као што следи: 

function foo(x) is:
  if predicate(x) then
    return foo(bar(x))
  else
    return baz(x)

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

function foo(x) is:
  while predicate(x) do:
    x ← bar(x)
  return baz(x)

У претходном, x може бити н-торка која укључује више од једне варијабле: ако тако, мора се водити рачуна приликом пројектовања доделе изјаве x ← bar(x) тако да се поштују зависности. Један ће можда морати да уведе помоће варијабле или да користи конструкције мењања.

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

function foo(x) is:
  if p(x) then
    return bar(x)
  else if q(x) then
    return baz(x)
  ...
  else if t(x) then
    return foo(quux(x))
  ...
  else
    return foo(quuux(x))

где bar и baz су директни повратни позиви, где quux и quuux укључују реп рекурзија позива до foo. Транслација следи:  

function foo(x) is:
  do:
    if p(x) then
      x ← bar(x)
      break
    else if q(x) then
      x ← baz(x)
      break
    ...
    else if t(x) then
      x ← quux(x)
      continue
    ...
    else
      x ← quuux(x)
      continue
    loop
  return x

По језицима

  • Јаваскрип-  ECMAСкрипт 6.0 компатибилни мотори би требало да имају репне рекурзије [14] што је убачено у Веб-кит .[15]
  • Луа - Репна рекурзија је изведена преко имплементације референце.[16]
  • Пајтон - Пајтон имплементације Стока не изводе оптимизацију репне рекурзије, иако је партија од троје модула доступна овоме.[17] Креатор језика Гвидо ван Росум тврди да су трагови стека обавештени преко елиминације репне рекурзије правећи дебаговање тешким, и преферира да програмери користе екплицитно понављање уместо тога.[18]
  • Scheme - Захтеван преко дефиниције језика.[19][20]
  • Tcl - Још од Tcl 8.6, Tcl има команду репне рекурзије.[21]

Види још

Напомене

  1. ^ The call instruction first pushes the current code location onto the stack and then performs an unconditional jump to the code location indicated by the label. The ret instruction first pops a code location off the stack, then performs an unconditional jump to the retrieved code location.
  • Овај чланак је базиран на материјалу узетом из Free On-line Dictionary of Computing пре 1 November 2008 и основан по "поновном издању лиценци" услова ГНУ, верзије 1.3 или касније.

Референце

  1. ^ а б в Steele, Guy Lewis (1977).
  2. ^ "recursion - Stack memory usage for tail calls - Theoretical Computer Science".
  3. ^ а б "Revised^6 Report on the Algorithmic Language Scheme".
  4. ^ "Revised^6 Report on the Algorithmic Language Scheme - Rationale".
  5. ^ D. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980.
  6. ^ Daniel P. Friedman and David S. Wise, Technical Report TR19: Unwinding Structured Recursions into Iterations, Indiana University, Dec. 1974.
  7. ^ R5RS Sec. 3.5, Richard Kelsey, William Clinger, Jonathan Rees; et al.
  8. ^ Contact details. "goto". perldoc.perl.org.
  9. ^ "What is difference between tail calls and tail recursion?"
  10. ^ "What limitations does the JVM impose on tail-call optimization", Programmers Stack Exchange
  11. ^ Probst, Mark (20 July 2000). "proper tail recursion for gcc".
  12. ^ Samuel Jack, Bouncing on your tail.
  13. ^ а б Henry Baker, "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." Архивирано на сајту Wayback Machine (3. март 2006)
  14. ^ Adam Beres-Deak. „Worth watching: Douglas Crockford speaking about the new good parts of JavaScript in 2014”. Bdadam.com. Приступљено 1. 2. 2016. 
  15. ^ Barati, Saam (13. 10. 2015). „ECMAScript 6 in”. WebKit. Приступљено 1. 2. 2016. 
  16. ^ „Lua 5.2 Reference Manual”. Lua.org. Приступљено 1. 2. 2016. 
  17. ^ „baruchel/tco: Tail Call Optimization for Python”. GitHub. 7. 11. 2015. Приступљено 1. 2. 2016. 
  18. ^ Guido van Rossum (22. 4. 2009). „Neopythonic: Tail Recursion Elimination”. Neopythonic.blogspot.com. Приступљено 1. 2. 2016. 
  19. ^ „Revised^5 Report on the Algorithmic Language Scheme”. Schemers.org. Приступљено 1. 2. 2016. 
  20. ^ „Revised^6 Report on the Algorithmic Language Scheme”. R6rs.org. Приступљено 1. 2. 2016. 
  21. ^ „tailcall manual page - Tcl Built-In Commands”. Tcl.tk. Приступљено 1. 2. 2016.