Repna rekurzija
Repna rekurzija u informatici je podrutinski poziv kao finalna akcija procedure. Ako bi repna rekurzija mogla dovesti do iste podrutine koja je pozvana ponovo kasnije u lancu poziva, za podrutinu se kaže da je repno-rekurzivna, što je poseban slučaj rekurzije. Repna rekurzija (ili rep-kraj rekurzija) je delimično korisna i često lako podnošljiva u implementacijama.
Repne rekurzije mogu biti realizovane bez dodavanja novog stek okvira da bi se pozvao stek. Većina okvira trenutne procedure nije potrebna, i može biti zamenjen okvirom repa rekurzije, modifikovan po potrebi (slično preklapanju za procese, ali za pozive funkcija). Program može skočiti na pozvanu podrutinu. Proizvodnja ovakvog kod umesto standardnog poziva sekvence se naziva eliminacija repne rekurzije. Eliminacija repne rekurzije omogućuje pozivima procedure u poziciji repa da budu efikasni kao goTo naredbe, što omogućuje efikasno strukturno programiranje. U rečima Gaj L. Stila, "u generalnoj proceduru pozivi mogu se smatrati korisnim kao GOTO naredbe koji takođe prolaze i parametre, i može biti ravnomerno kodiran kao [kod mašine] JUMP instrukcija".[1]
Tradicionalno, eliminacija repne rekurzije je opcionalna. Međutim, funkcionalnim programskim jezicima, eliminacija repne rekurzije je često zagarantovana preko standarda jezika i ova garancija omogućuje korišćenje rekurzije, posebno repa rekurzije, umesto petlji. U takvim slučajevima, nije tačno (ali može biti po želji) da se odnosi na njega kao na optimizaciju. Specijalan slučaj repnih poziva rekurzije, kada funkcija pozove samu sebe, može biti podložnija da pozove eliminaciju nego poziv glavnog repa.
Opis uredi
Kada se funkcija pozove, računar mora „zapamtiti“ mesto sa kog je pozvan, povratna adresa, tako da se može vratiti na lokaciju sa rezultatom onda kada je poziv završen. Tipično, ova iformacija je sačuvana na gomili poziva, jednostavna lista vraćenih lokacija poređanih po dostignutim lokacijama koje su opisane. Za repne rekurzije, nije potrebno da zapamtimo mesto sa kojeg ih zovemo- umesto toga, može uraditi eliminaciju repne rekurzije ostavljajući gomilu samu (moguće je osim argumenata funkcija i lokalnih varijabli [2]) i novo pozvana funkcija će vratiti njen rezultat direktno pravo pozivaču. Imati na umu da repna rekurzija ne mora da se pojavi leksički posle svih naredbi u izvornom kodu; samo je važno da se pozvana funkcija vrati odmah nakon poziva repne rekurzije, vraća repnu rekurziju ako postoji, pošto poziv funkcije neće dobiti šansu da uradi bilo šta nakon što se optimizacija izvede.
Za nerekurzivne funcione pozive, ovo je obično optimizaciju koja čuva malo vremena i mesta, pošto ne postoje mnogo različitih funkcija za pozivanje. Kada imate posla sa rekurzivnim ili obostranim rekurzivnim funkcijama gde se rekurzija dešava kroz rep rekurzije, međutim, goimla prostora i broj sačuvanih povratka može narasti da bude veoma značajan, pošto funkcija može da pozove samu sebe, direktno ili indirektno, stvarajući novu gomilu poziva prilikom svakog ponavljanja. U stvari, često asimptotski smanjuje zahteve gomile prostora sa linearnog, ili O(n), na konstantno, O(1), Eliminacija repne rekurzije je često zahtevana od strane standardnih definicija nekih programski jezika, kao što je Scheme ,[3][4] i jezici iz ML porodice. U slučaju Scheme, definicija jezika formalizuje intuitivni pojam repne rekurzije tačno, navodeći koje sintaksne forme dozvoljavaju posedovanje rezultata u kontekstu repa. Implementacije dozvoljavaju beskonačan broj repnih rekurzija da budu aktivne u isto vreme, zahvaljujući eliminaciji repne rekurzije, može se takođe zvati "pravilna repna rekurzija".[3]
Pored efikasnosti prostora i izvršavanja, eliminacija repne rekurzije je važna u funkcionalnom programiranju idiom poznat kao nastavak prolaznog stila (CPS), koji bi u suprotnom brzo ostao bez gomile prostora.
Forma sintakse uredi
Repna rekurzija može biti locirana pre sintaksnog kraja podrutine:A
function foo(data) {
a(data);
return b(data);
}
Ovde, a(data) ib(data) su pozivi, ali b je poslednja stvar koju procedura izvršava pre vraćanja i nalazi se u repnoj poziciji. Međutim, nisu sve repne rekurzije obavezno locijara ne sintaksnom kraju podrutine. Razmotriti:
function bar(data) {
if ( a(data) ) {
return b(data);
}
return c(data);
}
Ovde, oba poziva na b i c su u repnoj poziciji. Ovo je zato što svaki od njih leži na kraju if-grane redom, iako prvi nije sintasno na kraju bartela.
Sada razmotriti ovaj kod:
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;
}
Ovde, poziv na a(data) je u repnoj poziciju u foo2, ali nije u repnoj poziciji takođe u foo1 ili u foo3, zato što kontrola mora da vrati pozivaču da dozovli da ispita ili modifikuje vraćenu vrednost pre nego što ga vrati.
Example programs uredi
Videti ovaj Scheme program kao primer:
;; факторијел : број -> број
;; да калкулише продукт свих позитива
;; цели бројеви мањи или једнаки n.
(define (factorial n)
(if (= n 0)
1
(* n (factorial (- n 1)))))
Program iznad nije napisan u stilu repne rekurzije, zato što oznaka ("*") je u poziciji repa. Sada pogledati ovaj Scheme program kao primer:
;; факторијел : број -> број
;; да калкулише продукт свих позитива
;; цели бројеви мањи или једнаки n.
(define (factorial n)
(let fact ([i n] [acc 1])
(if (zero? i)
acc
(fact (- i 1) (* acc i)))))
Unutrašnji postupak fact poziva samu sebe poslednju u kontroli toka. Ovo dozvoljava interpretatoru ili kompilatoru da reorganizuje izvršavanje koje bi obično izgledalo ovako:
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
u efikasniju varijantu, u koristi vremenu i prostoru
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
Reorganizacija čuva prostor zato što nijedna izjava osim poziva adresa funkcije ne treba da se sačuva, ili na staku ili na gomili i okvir poziva steka zafact se ponovo koristi za srednji rezultat skladištenja. Ovo takođe znači da programer ne treba da brine da će da mu nestane prostora za ekstremno duboke rekurzije. Takođe ništa ne znači da, pri tipičnim implementacijama, varijante repa rekurzije će biti znatno brža nego druga varijanta, ali samo preko konstantnog faktora.
Neki programeri koji rade sa funkcionalnim jezicima bi ponovo napisali rekurzivan kod da bude repno-rekurzivan tako da bi mogli da uzmu korist od ove osobine. Ovo često zahteva dodatak "akumulator" argumenta (acc u pređašnjem primeru) funkciji. U nekim slučajevima (kao što je filterovanje liste) i u nekim jezicima, cela repna rekurzija može zahtevati funkciju koja je prethodno potpuno funkcionalna da bude zapisana tako da mutira reference sačuvane u ostalim varijablama.
Repna rekurzija protiv modula uredi
Repna rekurzija protiv modula je generalizacija repne rekurzije optimizacije predstavljena od strane Davida H. Vorena[5] u kontekstu kompilacija Prologa, viđen kao eksplicitni jezik postovi jednom. Opisano je (ali ne i imenovano) od strane Danijela P. Fridmana i Davida S. Vajsa 1974[6] kao LISP česta tehnika. Kao što ime nagoveštava, odnosi kada jedina operacija koje je ostala ponaša se kao repna rekurzija da predvidi poznatu vrednost ispred liste vraćene od njega (ili da uradi konstantan broj jednostavne operacije konstrukcije-podataka, u glavnom). Ovaj poziv bi bio rep rekurzije koji spašava za cons operaciju. Ali vrednost prefiksa na početku liste na kraju od rekurzivnog poziva je isto kao i dodavanje ove vrednost na kraju rastuće list na ulazu u rekurzivni poziv, gradeći listu kao sporedni efekat, kao implicitni parametar akumulatora. Sledeći fragmet Prologa pokazuje taj koncept:
% репно рекурзивни модул константе:
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)
).
|
Tako u prevodu repne rekurzije je transformisan prvo u pretvaranje novog čvora liste i postavljanje first polja i onda pravljenje repne rekurzija sa pokazivačem čvora rest polja kao argument, da bude ispunjen rekurzivno.
Kao još jedan primer, razmotriti rekurzivnu funkciju u S koja duplira linkovanu listu:
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([],[]).
|
U ovoj formi funckija nije repno rekurzivna, zato što se kontrola vraća pozivaču posle rekurzivnog poziva, duplira ostatak unosa liste. Čak iako bi se dodelila glava čvora pre dupliranja ostatka, idalje bi bilo potrebno priključiti rezultati rekurzivnog poziva u next polje posle poziva..[lower-alpha 1] Tako da je funkcija skoro repno-rekurzivna. Varenov metod odstranjuje odgovornost popunjavanjanext polja u rekurzivni poziv sam od sebe, čime postaje rep rekurzije:
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([],[]).
|
Imati na umu kako sada pozivaoc raste do kraja rastuće liste, radije nego da pozivač padne na početak vraćene liste. Posao je sada gotov na putu napred od početka liste, pre rekurzivnog poziva koji kasnije nastavlja dalje, nazad od kraja liste, posle rekurzivnog poziva vraća svoj rezultat. Stoga je sličan tehnici akumulacije parametra, koja pretvara rekurzivno računanje u iteraciono .
Karakteristično za ovu tehniku, roditeljski okvir je kreirao na izvršenju poziva steka, što poziva pozivaoca repne rekurzcije koji može ponovo koristiti svoj pozivni ovir ako je repna rakurzija optimizovana u sadašnjnosti.
Pravilna implementacija repa rekurzije može sada biti pretvorena u ekplicitnu iterativnu formu, npr. akumulaciona petlja:
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))))))
|
Istorija uredi
U papiru donetom ACM konferenciji u Sietlu 1977. godine, Gaj L. Stili ukrtko je sumirao debatu oko goTo i strukturnog programiranja i posmatrao je pozive procedure u repnoj rekurziji koje mogu biti najbolje tretirane kao direktan transfer kontrole do pozvane procedure, tipično eleminišući nepotrebne gomile manipulativnih operacija .[1] Pošto su takvi "repni pozivi" česti u Lisp-u, jezik u kome su pozivi procedura sveprisutni, ova forma optimizacije značajno smanjuje cenu poziva procedu poređenim sa ostalim implementacijama. Stili je raspravljao da su loše implementovani pozivi procedure doveli do veštačke percepcije da je GOTO jeftin u poređenju sa pozivom procedure. Stili se dalje raspravljao da "u glavnom pozivi procedura mogu biti korisno mišljenje GOTO naredbi koje takođe prolaze parametre, i može biti ravnomerno kodiran kao[kod mašine] JUMP instrukcija", sa stakom koda mašine manipulacija instrukcija "se smatra optimizacijom (više nego obrnuto)".[1] Stili je citirao dokaz da dobro optimizovani numerički algoritmi u Lisp-u mogu izvršiti brže nego kod proizveden preko dostupne reklame Fortran kompajlera, zato što je cena poziva procedure u Lisp-u mnogo jeftinija. U Scheme, Lisp-ov dialekt razvijen od strane Stilija sa Geraldom Džej Susmanom,|Geraldom Džej Susmanom, eliminacija repa rekurzije je garantovana da je implementovana u bilo koji interpreter[7]
Metode implementacije uredi
Repna rekurzija je važna prilikom nekih programskih jezika visokog nivoa, specijalno funkcionalnih i logičkih jezika i članova Lisp porodice. U ovim jezicima, repna rekurzija je najšće korišćena preko (i ponekad jedini mogući način) implementacije ponavljanja. Specifikacija jezika Scheme zahteva da repne rekurzije budu optimizovane kako ne bi povećavale stek. Repne rekurzije mogu biti eksplicitne u Perlu, preko varijante "goto" naredbe koja uzima ime funkcije: goto &NAME;[8]
Implementacija eliminacije repne rekurzije samo za rep rekurzije, pre nego za sve pozive repa, je nešto značajno lakše. Na primer, u Javinoj Virtualnoj Mašini(JVM), repno-rekurzivni pozivi mogu biti eliminisani (jer to preuzima postojeći poziv steka), ali uglavnom repne rekurzije ne mogu biti (jer ovo menja poziv steka).[9][10] Kao rezultat, funkcionalni jezici kao što je Skala koji ciljaju JVM mogu efikasno implementovati direktno reprnu rekurziju, ali ne uzajamnu repnu rekurziju.
Različite metode implementacije su dostupne.
U asembleru uredi
Repne rekurzije su često optimizovane od strane interpretatora i kompilatora od funkcionalnih i logičkih programiranja jezika kako bi bile efikasnije forme iteracije. Na primer, Scheme programeri često izražavaju while petlje kao poziv na provedu u repnoj poziciji i oslanjaju se na komplitaor ili interpretator Scheme kako bi zamenio repne rekurzije sa efikasnijim skok instrukcijama.[11]
Za kompilatore koji generališu asembler direktno, eliminacija repne rekurzije je laka: dovoljno je da zameni operacioni poziv sa skokom, posle poravljanja parametra na steku. Iz perspektive kompilatora, prvi primer iza je inicijalno preveden u pseudo-asembler jeziku(u stvari ovo je x86 asembler validno) :
foo:
call B
call A
ret
Eliminacija repne rekurzije menja dva reda sa jednom skok instrukcijom:
foo:
call B
jmp A
Pošto se podrutina A završi, ona će se vratiti direktno vraćenoj adresi foo, izbegavanjem nepotrebne ret naredbe.
Tipično, pozvana podrutina mora biti snabdevana paramterima. Ostvareni kod se mora uveriti da je pozivni okvir za A pravilno postavljen pre skoka na repno-pozvanu podrutinu. Na primer, na platformama gde poziv steka ne sadrži povratnu adresu, ali takođe parametre za podrutinu, komplitaor će možda morati da emituje instrukcije da bi prilagodio poziv steka. Na takvoj platformi, razmotriti kod:
function foo(data1, data2) B(data1) return A(data2)
gde data1 i data2 su parametri. Kompilator može prevesti to u sledeći pseudo asembler kod:[a]
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
Optimizer repne rekurzije može promeniti kod u:
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 и враћа одмах позивачу
Ovaj promenjeni kod je mnogo efikasniji u oba uslova izvršavanja brzine i korišćenja prostora.
Kroz trampolining uredi
Međutim, pošto mnogo Scheme kompilatori koriste S kao središnji ciljani kod, problem dolazi pri kodiranju repne rekurziju u S bez rasta steka, iako zadnji kompilator ne optimizuje repne rekurzije. Mnogo implementacije postižu ovo korišćenjem uređaja poznatiji kao trampolin, deo koda koji neprestano poziva funkcije. Sve funkcije su unete preko trampoline. Kada funkcija treba da pozove drugu, umesto da je pozove direktno ona joj daje adresu funkcije za poziv, argumenti za korišćenje, i tako dalje, do trampoline. Ovo osigurava da S stek ne raste i da ponavljanje može da ide do beskonačnosti
Moguće je ubaciti tramolinovanje koristeći funkcije višeg reda u jezicima koji ih podržavaju , kao što su Gruvi, Vižual Bejsik .Net i S#.[12]
Koristeći trampolin za sve pozive funkcije je dosta skuplje nego normalni S pozivi, tako da najmanje jedan Scheme kompilator, Kokoška, koristi tehniku koju je prvi opisao Henri Bejker u neobjavljenoj sugestiji Endru Apela,[13] u kojoj normalni S pozivi se koriste ali veličina steka je proverena pre svakog poziva. Kada stek dostigne maksimum dozvoljene veličine, objekti steka su pokupljeno đubre korišćenjem Čenej algoritmom pomerajući sve žive podatke u odvojenu gomilu. Prateći ovo, stek je odmotan ("pao") u i program nastavlja sa sačuvanog stanja pre kolekcije smeća. Bejker kaže "Apelov metod izbegava pravljenje velikog broja malih odbitaka trampoline privremenim skokovima sa Empajer Stejt Zgrade"[13] Kolekcija smeća proverava da li uzajamna reprna rekurzija nastavlja u da radi u beskonačnost. Međutim, ovaj pristup zahtva da se nijedan S poziv funkcije vraća, pošto ne postoji garancija da okvir pozivača idalje postoji; zbog toga, to uključuje dramatičnije unutrašnje prepisivanje programskog koda:stil nastavka-prolaza.
Odnos prema while konstrukciji uredi
Repna rekurzija može biti povezana sa while operatorom kontrole toka putem transformacije kao što sledi:
function foo(x) is:
if predicate(x) then
return foo(bar(x))
else
return baz(x)
Konstrukcija iznad se pretvara u:
function foo(x) is:
while predicate(x) do:
x ← bar(x)
return baz(x)
U prethodnom, x može biti n-torka koja uključuje više od jedne varijable: ako tako, mora se voditi računa prilikom projektovanja dodele izjave x ← bar(x) tako da se poštuju zavisnosti. Jedan će možda morati da uvede pomoće varijable ili da koristi konstrukcije menjanja.
Opštije korišćenje repne rekurzije može biti povezano sa operatorima kontrole toka kao što je stani i nastavi, što sledi:
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))
gde bar i baz su direktni povratni pozivi, gde quux i quuux uključuju rep rekurzija poziva do foo. Translacija sledi:
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
Po jezicima uredi
- Javaskrip- ECMASkript 6.0 kompatibilni motori bi trebalo da imaju repne rekurzije [14] što je ubačeno u Veb-kit .[15]
- Lua - Repna rekurzija je izvedena preko implementacije reference.[16]
- Pajton - Pajton implementacije Stoka ne izvode optimizaciju repne rekurzije, iako je partija od troje modula dostupna ovome.[17] Kreator jezika Gvido van Rosum tvrdi da su tragovi steka obavešteni preko eliminacije repne rekurzije praveći debagovanje teškim, i preferira da programeri koriste ekplicitno ponavljanje umesto toga.[18]
- Scheme - Zahtevan preko definicije jezika.[19][20]
- Tcl - Još od Tcl 8.6, Tcl ima komandu repne rekurzije.[21]
Vidi još uredi
Napomene uredi
- ^ The
callinstruction first pushes the current code location onto the stack and then performs an unconditional jump to the code location indicated by the label. Theretinstruction first pops a code location off the stack, then performs an unconditional jump to the retrieved code location.
- Ovaj članak je baziran na materijalu uzetom iz Free On-line Dictionary of Computing pre 1 November 2008 i osnovan po "ponovnom izdanju licenci" uslova GNU, verzije 1.3 ili kasnije.
Reference uredi
- ^ a b v Steele, Guy Lewis (1977).
- ^ "recursion - Stack memory usage for tail calls - Theoretical Computer Science".
- ^ a b "Revised^6 Report on the Algorithmic Language Scheme".
- ^ "Revised^6 Report on the Algorithmic Language Scheme - Rationale".
- ^ D. H. D. Warren, DAI Research Report 141, University of Edinburgh, 1980.
- ^ Daniel P. Friedman and David S. Wise, Technical Report TR19: Unwinding Structured Recursions into Iterations, Indiana University, Dec. 1974.
- ^ R5RS Sec. 3.5, Richard Kelsey, William Clinger, Jonathan Rees; et al.
- ^ Contact details. "goto". perldoc.perl.org.
- ^ "What is difference between tail calls and tail recursion?"
- ^ "What limitations does the JVM impose on tail-call optimization", Programmers Stack Exchange
- ^ Probst, Mark (20 July 2000). "proper tail recursion for gcc".
- ^ Samuel Jack, Bouncing on your tail.
- ^ a b Henry Baker, "CONS Should Not CONS Its Arguments, Part II: Cheney on the M.T.A." Arhivirano na sajtu Wayback Machine (3. mart 2006)
- ^ Adam Beres-Deak. „Worth watching: Douglas Crockford speaking about the new good parts of JavaScript in 2014”. Bdadam.com. Pristupljeno 1. 2. 2016.
- ^ Barati, Saam (13. 10. 2015). „ECMAScript 6 in”. WebKit. Pristupljeno 1. 2. 2016.
- ^ „Lua 5.2 Reference Manual”. Lua.org. Pristupljeno 1. 2. 2016.
- ^ „baruchel/tco: Tail Call Optimization for Python”. GitHub. 7. 11. 2015. Pristupljeno 1. 2. 2016.
- ^ Guido van Rossum (22. 4. 2009). „Neopythonic: Tail Recursion Elimination”. Neopythonic.blogspot.com. Pristupljeno 1. 2. 2016.
- ^ „Revised^5 Report on the Algorithmic Language Scheme”. Schemers.org. Pristupljeno 1. 2. 2016.
- ^ „Revised^6 Report on the Algorithmic Language Scheme”. R6rs.org. Pristupljeno 1. 2. 2016.
- ^ „tailcall manual page - Tcl Built-In Commands”. Tcl.tk. Pristupljeno 1. 2. 2016.