Ce este recursivitatea de coadă? (Programare, Algoritm, Agnostic De Limbă, Programare Funcțională, Recursivitate, Recursivitate De Coadă)

În timp ce începeam să învăț lisp, am dat peste termenul coadă recursivă. Ce înseamnă mai exact?

Comentarii

    15

  • Poate că este târziu, dar acesta este un articol destul de bun despre coada recursivă:programmerinterview.com/index.php/recursion/tail-recursion –  > Por Sam003.
  • Unul dintre marile beneficii ale identificării unei funcții tail-recursive este că aceasta poate fi convertită într-o formă iterativă și astfel să reînvie algoritmul de la method-stack-overhead. Poate doriți să vizitați răspunsul lui @Kyle Cronin și al altor câtorva persoane mai jos –  > Por KGhatak.
  • Acest link de la @yesudeep este cea mai bună și mai detaliată descriere pe care am găsit-o – lua.org/pil/6.3.html –  > Por Jeff Fischer.
  • Ar putea cineva să-mi spună, Merge sort și quick sort folosesc recursivitatea cozii (TRO) ? –  > Por majurageerthan.
  • @majurageerthan – asta depinde de implementarea particulară a acestor algoritmi (și a oricărui alt algoritm). –  > Por Bob Jarvis – Reînscrieți-o pe Monica.
29 răspunsuri
Lorin Hochstein

Luați în considerare o funcție simplă care adaugă primele N numere naturale. (de ex. sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Iată o implementare simplă în JavaScript care folosește recursivitatea:

function recsum(x) {
    if (x === 1) {
        return x;
    } else {
        return x + recsum(x - 1);
    }
}

Dacă ați apelat recsum(5), iată ce ar evalua interpretul JavaScript:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + 1)))
15

Observați cum fiecare apel recursiv trebuie să se finalizeze înainte ca interpretul JavaScript să înceapă să calculeze efectiv suma.

Iată o versiune recursivă a aceleiași funcții:

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

Iată secvența de evenimente care ar avea loc dacă ați apela tailrecsum(5), (care ar fi de fapt tailrecsum(5, 0), din cauza celui de-al doilea argument implicit).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

În cazul funcției recursive de coadă, la fiecare evaluare a apelului recursiv, funcția running_total este actualizată.

Notă: Răspunsul original a folosit exemple din Python. Acestea au fost schimbate în JavaScript, deoarece interpretorii Python nu acceptă optimizarea apelurilor de coadă. Cu toate acestea, în timp ce optimizarea apelurilor de coadă este face parte din specificația ECMAScript 2015, majoritatea interpretoarelor JavaScript nu o acceptă.

Comentarii

    51

  • Pot să spun că în cazul recursivității cozii răspunsul final este calculat doar de ULTIMA invocare a metodei? Dacă NU este recursivitate de coadă, aveți nevoie de toate rezultatele tuturor metodelor pentru a calcula răspunsul. –  > Por chrisapotek.
  • Iată un addendum care prezintă câteva exemple în Lua: lua.org/pil/6.3.html Poate fi util să parcurgeți și asta! 🙂 –  > Por yesudeep.
  • Poate cineva să răspundă la întrebarea lui chrisapotek? Sunt confuz cum tail recursion poate fi realizat într-un limbaj care nu optimizează apelurile de coadă. –  > Por Kevin Meredith.
  • @KevinMeredith „recursivitatea cozii” înseamnă că ultima declarație dintr-o funcție este un apel recursiv la aceeași funcție. Aveți dreptate că nu are rost să faceți acest lucru într-un limbaj care nu optimizează această recursivitate. Cu toate acestea, acest răspuns prezintă conceptul (aproape) corect. Ar fi fost mai clar un apel de coadă, dacă „else:” ar fi fost omis. Aceasta nu ar schimba comportamentul, dar ar plasa apelul de coadă ca o instrucțiune independentă. Voi prezenta acest lucru ca o modificare. –  > Por ToolmakerSteve.
  • Deci, în python nu există niciun avantaj, deoarece la fiecare apel la funcția tailrecsum, se creează un nou cadru de stivă – corect? –  > Por Quazi Irfan.
user316

În recursivitatea tradițională, modelul tipic este că efectuați mai întâi apelurile recursive, apoi luați valoarea de întoarcere a apelului recursiv și calculați rezultatul. În acest mod, nu obțineți rezultatul calculului până când nu v-ați întors din fiecare apel recursiv.

În recursivitate de coadă, efectuați mai întâi calculele și apoi executați apelul recursiv, transmițând rezultatele pasului curent la următorul pas recursiv. Acest lucru are ca rezultat faptul că ultima instrucțiune are forma de (return (recursive-function params)). Practic, valoarea de întoarcere a oricărui pas recursiv dat este aceeași cu valoarea de întoarcere a următorului apel recursiv.

Consecința acestui lucru este că, odată ce sunteți gata să efectuați următorul pas recursiv, nu mai aveți nevoie de cadrul de stivă curent. Acest lucru permite o anumită optimizare. De fapt, cu un compilator scris corespunzător, nu ar trebui să aveți niciodată o depășire a stivei snicker cu un apel recursiv de coadă. Pur și simplu reutilizați cadrul de stivă curent pentru următorul pas recursiv. Sunt destul de sigur că Lisp face acest lucru.

Comentarii

    17

  • „Sunt aproape sigur că Lisp face acest lucru” – Scheme face acest lucru, dar Common Lisp nu o face întotdeauna. –  > Por Aaron.
  • @Daniel „Practic, valoarea de întoarcere a oricărui pas recursiv dat este aceeași cu valoarea de întoarcere a următorului apel recursiv.” – Nu reușesc să văd că acest argument este valabil pentru fragmentul de cod postat de Lorin Hochstein. Puteți, vă rog, să detaliați? –  > Por Geek.
  • @Geek Acesta este un răspuns foarte târziu, dar acest lucru este de fapt adevărat în exemplul lui Lorin Hochstein. Calculul pentru fiecare pas se face înainte de apelul recursiv, mai degrabă decât după acesta. Ca urmare, fiecare oprire doar returnează valoarea direct din pasul anterior. Ultimul apel recursiv finalizează calculul și apoi returnează rezultatul final nemodificat până jos în stiva de apeluri. –  > Por reirab.
  • Scala o face, dar aveți nevoie de specificarea @tailrec pentru a o impune. –  > Por SilentDirge.
  • „În acest mod, nu obțineți rezultatul calculului până când nu vă întoarceți din fiecare apel recursiv.” — poate că am înțeles greșit, dar acest lucru nu este valabil în special pentru limbajele leneșe în care recursivitate tradițională este singura modalitate de a obține efectiv un rezultat fără a apela toate recursivitățile (de exemplu, plierea peste o listă infinită de Bools cu &&). –  > Por hasufell.
Chris Conway

Un aspect important este că recursivitatea de coadă este, în esență, echivalentă cu bucla. Nu este doar o chestiune de optimizare a compilatorului, ci un fapt fundamental despre expresivitate. Acest lucru este valabil în ambele sensuri: puteți lua orice buclă de forma

while(E) { S }; return Q

unde E și Q sunt expresii și S este o secvență de instrucțiuni, și să o transformați într-o funcție recursivă de coadă

f() = if E then { S; return f() } else { return Q }

Bineînțeles, E, S, și Q trebuie să fie definite pentru a calcula o valoare interesantă pentru anumite variabile. De exemplu, funcția de buclă

sum(n) {
  int i = 1, k = 0;
  while( i <= n ) {
    k += i;
    ++i;
  }
  return k;
}

este echivalentă cu funcția (funcțiile) recursivă(e) de coadă

sum_aux(n,i,k) {
  if( i <= n ) {
    return sum_aux(n,i+1,k+i);
  } else {
    return k;
  }
}

sum(n) {
  return sum_aux(n,1,0);
}

(Această „înfășurare” a funcției coada-recursivă cu o funcție cu mai puțini parametri este un idiom funcțional comun).

Comentarii

  • În răspunsul lui @LorinHochstein am înțeles, pe baza explicației sale, că recursivitatea de coadă este atunci când porțiunea recursivă urmează după „Return”, însă în răspunsul dumneavoastră, recursivitatea de coadă nu este. Sunteți sigur că exemplul dvs. este considerat corect recursivitate de coadă? –  > Por CodyBugstein.
  • @Imray Partea recursivă de coadă este declarația „return sum_aux” din interiorul sum_aux. –  > Por Chris Conway.
  • @lmray: Codul lui Chris este în esență echivalent. Ordinea if/then și stilul testului de limitare… if x == 0 versus if(i<=n)… nu este ceva care să ne dea bătăi de cap. Ideea este că fiecare iterație transmite rezultatul său la următoarea. –  > Por Taylor.
  • else { return k; } poate fi schimbat în return k; –  > Por c0der.
  • @cOder, ai dreptate, dar oamenii vin pe stackoverflow pentru a învăța și ei, apoi poate să folosească if și else să fie mai cuprinzător pentru mai mulți începători, cred…  > Por Enrique René.
Hoffmann

Acest extras din carte Programarea în Lua arată cum se realizează o recursivitate de coadă adecvată (în Lua, dar ar trebui să se aplice și la Lisp) și de ce este mai bună.

A apel de coadă [tail recursion] este un fel de goto îmbrăcat ca un apel. Un apel de coadă are loc atunci când o funcție apelează o alta ca ultimă acțiune, astfel încât nu mai are nimic altceva de făcut. De exemplu, în codul următor, apelul către g este un apel secundar:

function f (x)
  return g(x)
end

După f apelează g, nu mai are nimic altceva de făcut. În astfel de situații, programul nu trebuie să se întoarcă la funcția apelantă atunci când funcția apelată se termină. Prin urmare, după apelul de coadă, programul nu trebuie să păstreze în stivă nicio informație despre funcția apelantă. …

Deoarece un apel de coadă adecvat nu utilizează spațiu în stivă, nu există o limită a numărului de apeluri de coadă „imbricate” pe care le poate efectua un program. De exemplu, putem apela următoarea funcție cu orice număr ca argument; aceasta nu va depăși niciodată stiva:

function foo (n)
  if n > 0 then return foo(n - 1) end
end

… După cum am spus mai devreme, un apel de coadă este un fel de goto. Ca atare, o aplicație destul de utilă a apelurilor de coadă adecvate în Lua este programarea mașinilor de stare. Astfel de aplicații pot reprezenta fiecare stare printr-o funcție; pentru a schimba starea este necesar să se meargă la (sau să se apeleze) o funcție specifică. Ca exemplu, să luăm în considerare un joc simplu de labirint. Labirintul are mai multe camere, fiecare cu până la patru uși: nord, sud, est și vest. La fiecare pas, utilizatorul introduce o direcție de deplasare. Dacă există o ușă în direcția respectivă, utilizatorul merge în camera corespunzătoare; în caz contrar, programul tipărește un avertisment. Scopul este de a merge de la o cameră inițială la o cameră finală.

Acest joc este o mașină de stare tipică, în care camera curentă este starea. Putem implementa un astfel de labirint cu o funcție pentru fiecare cameră. Folosim apeluri de coadă pentru a trece de la o cameră la alta. Un labirint mic cu patru camere ar putea arăta astfel:

function room1 ()
  local move = io.read()
  if move == "south" then return room3()
  elseif move == "east" then return room2()
  else print("invalid move")
       return room1()   -- stay in the same room
  end
end

function room2 ()
  local move = io.read()
  if move == "south" then return room4()
  elseif move == "west" then return room1()
  else print("invalid move")
       return room2()
  end
end

function room3 ()
  local move = io.read()
  if move == "north" then return room1()
  elseif move == "east" then return room4()
  else print("invalid move")
       return room3()
  end
end

function room4 ()
  print("congratulations!")
end

Deci, vedeți, atunci când faceți un apel recursiv de genul:

function x(n)
  if n==0 then return 0
  n= n-2
  return x(n) + 1
end

Acesta nu este recursiv de coadă, deoarece mai aveți încă lucruri de făcut (adăugați 1) în acea funcție după ce se face apelul recursiv. Dacă introduceți un număr foarte mare, probabil că se va produce o depășire a stivei.

Comentarii

  • Acesta este un răspuns excelent, deoarece explică implicațiile apelurilor de coadă asupra dimensiunii stivei. –  > Por Andrew Swan.
  • @AndrewSwan Într-adevăr, deși cred că autorul original al întrebării și cititorul ocazional care ar putea să se împiedice de această întrebare ar putea fi mai bine servit cu răspunsul acceptat (deoarece s-ar putea să nu știe ce este de fapt stiva.) Apropo, folosesc Jira, mare fan. –  > Por Hoffmann.
  • Răspunsul meu preferat, de asemenea, datorită includerii implicațiilor pentru dimensiunea stivei. –  > Por njk2015.
FlySwat

Utilizând recursivitatea obișnuită, fiecare apel recursiv împinge o altă intrare pe stiva de apeluri. Când recursivitatea este finalizată, aplicația trebuie apoi să scoată fiecare intrare până jos.

Cu recursivitatea de coadă, în funcție de limbaj, compilatorul poate fi capabil să prăbușească stiva până la o singură intrare, astfel încât să economisiți spațiu în stivă… O interogare recursivă mare poate provoca de fapt o depășire a stivei.

Practic, recursivitățile de coadă pot fi optimizate în iterație.

Comentarii

  • „O interogare recursivă de mari dimensiuni poate provoca de fapt o depășire a stivei.” ar trebui să fie în primul paragraf, nu în cel de-al doilea (recursivitatea cozii) ? Marele avantaj al recursivității de coadă este că poate fi (ex: Scheme) optimizată astfel încât să nu „acumuleze” apeluri în stivă, deci va evita în mare parte depășirile de stivă! –  > Por Olivier Dulac.
Pat

Fișierul de jargon are următorul lucru de spus despre definiția recursivității de coadă:

recursivitate de coadă /n./

Dacă nu v-ați săturat deja de ea, vedeți recursivitate de coadă.

Kyle Cronin

În loc să explicăm prin cuvinte, iată un exemplu. Aceasta este o versiune Scheme a funcției factorial:

(define (factorial x)
  (if (= x 0) 1
      (* x (factorial (- x 1)))))

Iată o versiune a funcției factorial care este recurentă la coadă:

(define factorial
  (letrec ((fact (lambda (x accum)
                   (if (= x 0) accum
                       (fact (- x 1) (* accum x))))))
    (lambda (x)
      (fact x 1))))

Veți observa în prima versiune că apelul recursiv la fact este introdus în expresia de multiplicare și, prin urmare, starea trebuie salvată pe stivă atunci când se face apelul recursiv. În versiunea recursivă de coadă nu există nicio altă expresie S care să aștepte valoarea apelului recursiv și, deoarece nu mai este nimic de făcut, starea nu trebuie salvată pe stivă. De regulă, funcțiile de tip „tail-recursive” din Scheme utilizează un spațiu constant în stivă.

Comentarii

  • +1 pentru a menționa cel mai important aspect al funcțiilor de recursivitate de coadă că acestea pot fi convertite într-o formă iterativă și, astfel, transformate într-o formă cu complexitate de memorie O(1). –  > Por KGhatak.
  • @KGhatak nu chiar; răspunsul vorbește corect despre „spațiu constant de stivă”, nu despre memorie în general. nu pentru a fi pisălog, ci doar pentru a mă asigura că nu există nicio neînțelegere. de exemplu, tail-recursive list-tail-mutating list-reverse se va executa în spațiu constant de stivă, dar va crea și va crește o structură de date pe heap. O parcurgere a unui arbore ar putea utiliza o stivă simulată, într-un argument suplimentar. etc. –  > Por Will Ness.
Peter Meyer

Recursivitatea de coadă se referă la faptul că apelul recursiv este ultimul în ultima instrucțiune logică din algoritmul recursiv.

În mod obișnuit, în recursivitate, aveți un caz de bază care este cel care oprește apelurile recursive și care începe să scoată stiva de apeluri. Pentru a folosi un exemplu clasic, deși mai degrabă în C decât în Lisp, funcția factorială ilustrează recursivitatea de coadă. Apelul recursiv are loc după verificarea condiției de bază.

factorial(x, fac=1) {
  if (x == 1)
     return fac;
   else
     return factorial(x-1, x*fac);
}

Apelul inițial la factorial ar fi factorial(n) unde fac=1 (valoare implicită) și n este numărul pentru care trebuie calculată factoriala.

Comentarii

  • Explicația dvs. mi s-a părut cel mai ușor de înțeles, dar, dacă e să ne luăm după ea, atunci recursivitatea cozii este utilă doar pentru funcțiile cu cazuri de bază cu un singur enunț. Luați în considerare o metodă de genul acesta postimg.cc/5Yg3Cdjn. Observație: funcția exterioară else este pasul pe care l-ați putea numi „caz de bază”, dar se întinde pe mai multe linii. Vă înțeleg greșit sau presupunerea mea este corectă? Recursivitatea de coadă este bună doar pentru un singur rând? –  > Por Vreau răspunsuri.
  • @IWantAnswers – Nu, corpul funcției poate fi arbitrar de mare. Tot ceea ce este necesar pentru un apel de coadă este ca ramura în care se află să apeleze funcția ca ultimul lucru pe care îl face și să returneze rezultatul apelării funcției. factorial exemplu este doar exemplul clasic și simplu, atâta tot. –  > Por T.J. Crowder.
  • Peter Meyer, pentru exemplul tău, este într-adevăr necesar ca timpul de execuție să mențină o stivă de apeluri? @FlySwat –  > Por Supun Wijerathne.
Chris Smith

Înseamnă că, mai degrabă decât să fie nevoie să împingeți pointerul de instrucțiuni pe stivă, puteți pur și simplu să săriți la partea de sus a unei funcții recursive și să continuați execuția. Acest lucru permite ca funcțiile să se recurgă la infinit fără a depăși stiva.

Am scris o funcție blog post pe această temă, care conține exemple grafice despre cum arată cadrele stivei.

Iată un scurt fragment de cod care compară două funcții. Prima este o recursivitate tradițională pentru a găsi factorialul unui număr dat. A doua folosește recursivitatea de coadă.

Foarte simplu și intuitiv de înțeles.

Un mod simplu de a spune dacă o funcție recursivă este o funcție recursivă de coadă este dacă returnează o valoare concretă în cazul de bază. Adică nu returnează 1 sau true sau ceva de genul acesta. Mai mult ca sigur va returna o variantă a unuia dintre parametrii metodei.

Un alt mod de a spune este dacă apelul recursiv nu conține nicio adăugare, aritmetică, modificare etc… Adică nu este decât un apel pur recursiv.

public static int factorial(int mynumber) {
    if (mynumber == 1) {
        return 1;
    } else {            
        return mynumber * factorial(--mynumber);
    }
}

public static int tail_factorial(int mynumber, int sofar) {
    if (mynumber == 1) {
        return sofar;
    } else {
        return tail_factorial(--mynumber, sofar * mynumber);
    }
}

Comentarii

  • 0! este 1. Deci „mynumber == 1” ar trebui să fie „mynumber == 0”. –  > Por polerto.

Cel mai bun mod de a înțelege pentru mine tail call recursion este un caz special de recursivitate în care ultimul apel(sau apelul de coadă) este funcția în sine.

Comparând exemplele furnizate în Python:

def recsum(x):
 if x == 1:
  return x
 else:
  return x + recsum(x - 1)

^RECURSION

def tailrecsum(x, running_total=0):
  if x == 0:
    return running_total
  else:
    return tailrecsum(x - 1, running_total + x)

^RECURSIUNE DE COADĂ

După cum puteți vedea în versiunea recursivă generală, apelul final din blocul de cod este x + recsum(x - 1). Astfel, după ce a fost apelat recsum există o altă operație care este x + ...

Cu toate acestea, în versiunea recursivă de coadă, apelul final (sau apelul de coadă) din blocul de cod este tailrecsum(x - 1, running_total + x) ceea ce înseamnă că ultimul apel se face la metoda în sine și nu mai există nicio operațiune după aceea.

Acest punct este important deoarece recursivitatea de coadă, așa cum se vede aici, nu face ca memoria să crească, deoarece atunci când VM-ul subiacent vede o funcție care se apelează pe sine într-o poziție de coadă (ultima expresie care trebuie evaluată într-o funcție), elimină cadrul stivei curente, ceea ce este cunoscut sub numele de Tail Call Optimization (TCO).

EDITARE

NB. Țineți cont de faptul că exemplul de mai sus este scris în Python, al cărui timp de execuție nu suportă TCO. Acesta este doar un exemplu pentru a explica ideea. TCO este suportat în limbaje precum Scheme, Haskell etc.

jorgetown

În Java, iată o posibilă implementare recursivă de coadă a funcției Fibonacci:

public int tailRecursive(final int n) {
    if (n <= 2)
        return 1;
    return tailRecursiveAux(n, 1, 1);
}

private int tailRecursiveAux(int n, int iter, int acc) {
    if (iter == n)
        return acc;
    return tailRecursiveAux(n, ++iter, acc + iter);
}

Contrastând cu implementarea recursivă standard:

public int recursive(final int n) {
    if (n <= 2)
        return 1;
    return recursive(n - 1) + recursive(n - 2);
}

Comentarii

  • Aceasta îmi returnează rezultate greșite, pentru intrarea 8 primesc 36, trebuie să fie 21. Îmi scapă ceva? Folosesc java și am făcut copy paste. –  > Por Alberto Zaccagni.
  • Aceasta returnează SUM(i) pentru i în [1, n]. Nu are nimic de-a face cu Fibbonacci. Pentru un Fibbo, aveți nevoie de un test care să sustragă iter la acc când iter < (n-1). –  > Por Askolein.
Matt Hamilton

Nu sunt un programator Lisp, dar cred că acest va fi de ajutor.

Practic, este un stil de programare astfel încât apelul recursiv să fie ultimul lucru pe care îl faci.

Iată un exemplu de Common Lisp care face factoriale folosind recursivitatea cozii. Datorită naturii fără stivă, se pot efectua calcule factoriale nebunește de mari …

(defun ! (n &optional (product 1))
    (if (zerop n) product
        (! (1- n) (* product n))))

Și apoi, pentru distracție, puteți încerca (format nil "~R" (! 25))

Pe scurt, o recursivitate de coadă are apelul recursiv ca fiind apelul ultimul declarație din funcție, astfel încât să nu fie nevoie să aștepte apelul recursiv.

Așadar, aceasta este o recursivitate de coadă, adică N(x – 1, p * x) este ultima instrucțiune din funcție în care compilatorul este inteligent și își dă seama că poate fi optimizată pentru o buclă for (factorială). Al doilea parametru p poartă valoarea produsului intermediar.

function N(x, p) {
   return x == 1 ? p : N(x - 1, p * x);
}

Aceasta este modalitatea non-recursivă de scriere a funcției factoriale de mai sus (deși unele compilatoare C++ pot fi capabile să o optimizeze oricum).

function N(x) {
   return x == 1 ? 1 : x * N(x - 1);
}

dar aceasta nu este:

function F(x) {
  if (x == 1) return 0;
  if (x == 2) return 1;
  return F(x - 1) + F(x - 2);
}

Am scris o postare lungă intitulată „Înțelegerea recurenței de coadă – Visual Studio C++ – Vizualizare asamblare

Comentarii

  • Cum este funcția ta N de recursivitate a cozii ? –  > Por Fabian Pijcke.
  • N(x-1) este ultima instrucțiune din funcția în care compilatorul este inteligent să își dea seama că poate fi optimizată la o buclă for (factorială) –  > Por doctorlai.
  • Preocuparea mea este că funcția ta N este exact funcția recsum din răspunsul acceptat al acestui topic (doar că este o sumă și nu un produs) și că se spune că recsum este nerecursivă la coadă ? –  > Por Fabian Pijcke.

Funcția recursivă este o funcție care se apelează singură

Ea permite programatorilor să scrie programe eficiente utilizând o o cantitate minimă de cod.

Dezavantajul este că acestea pot cauza bucle infinite și alte rezultate neașteptate dacă nu sunt scrise corespunzător.

Voi explica ambele funcția Recursivă simplă și funcția Recursivă de coadă

Pentru a scrie o funcție funcție recursivă simplă

  1. Primul punct de luat în considerare este momentul în care ar trebui să decideți să ieșiți din bucla care este bucla if
  2. Al doilea este ce proces să facem dacă suntem propria noastră funcție

Din exemplul dat:

public static int fact(int n){
  if(n <=1)
     return 1;
  else 
     return n * fact(n-1);
}

Din exemplul de mai sus

if(n <=1)
     return 1;

Este factorul care decide când să ieșim din buclă

else 
     return n * fact(n-1);

este procesarea efectivă care trebuie efectuată

Permiteți-mi să despart sarcinile una câte una pentru o mai bună înțelegere.

Să vedem ce se întâmplă pe plan intern dacă execut fact(4)

  1. Înlocuind n=4
public static int fact(4){
  if(4 <=1)
     return 1;
  else 
     return 4 * fact(4-1);
}

If buclă nu reușește, așa că se trece la else buclă și se întoarce 4 * fact(3)

  1. În memoria stivei, avem 4 * fact(3)

    Înlocuind n=3

public static int fact(3){
  if(3 <=1)
     return 1;
  else 
     return 3 * fact(3-1);
}

If buclă eșuează, așa că merge la else bucla

deci se întoarce 3 * fact(2)

Amintiți-vă că am apelat „`4 * fact(3)„

Rezultatul pentru fact(3) = 3 * fact(2)

Până acum, stiva are 4 * fact(3) = 4 * 3 * fact(2)

  1. În memoria stivei, avem 4 * 3 * fact(2)

    Înlocuind n=2

public static int fact(2){
  if(2 <=1)
     return 1;
  else 
     return 2 * fact(2-1);
}

If buclă eșuează, așa că se trece la else bucla

deci se întoarce 2 * fact(1)

Amintiți-vă că am apelat 4 * 3 * fact(2)

Ieșirea pentru fact(2) = 2 * fact(1)

Până acum, stiva are 4 * 3 * fact(2) = 4 * 3 * 2 * fact(1)

  1. În memoria stivei, avem 4 * 3 * 2 * fact(1)

    Înlocuind n=1

public static int fact(1){
  if(1 <=1)
     return 1;
  else 
     return 1 * fact(1-1);
}

If bucla este adevărată

deci returnează 1

Amintiți-vă că am apelat 4 * 3 * 2 * fact(1)

Ieșirea pentru fact(1) = 1

Până acum stiva are 4 * 3 * 2 * fact(1) = 4 * 3 * 2 * 1

În cele din urmă, rezultatul din fact(4) = 4 * 3 * 2 * 1 = 24

Recursivitate de coadă ar fi

public static int fact(x, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(x-1, running_total*x);
    }
}

  1. Înlocuind n=4
public static int fact(4, running_total=1) {
    if (x==1) {
        return running_total;
    } else {
        return fact(4-1, running_total*4);
    }
}

If buclă eșuează, așa că se trece la else buclă și se întoarce fact(3, 4)

  1. În memoria stivă, avem fact(3, 4)

    Înlocuind n=3

public static int fact(3, running_total=4) {
    if (x==1) {
        return running_total;
    } else {
        return fact(3-1, 4*3);
    }
}

If buclă eșuează, așa că merge la else bucla

deci se întoarce fact(2, 12)

  1. În memoria stivei, avem fact(2, 12)

    Înlocuind n=2

public static int fact(2, running_total=12) {
    if (x==1) {
        return running_total;
    } else {
        return fact(2-1, 12*2);
    }
}

If buclă eșuează, așa că merge la else bucla

deci se întoarce fact(1, 24)

  1. În memoria stivei, avem fact(1, 24)

    Înlocuind n=1

public static int fact(1, running_total=24) {
    if (x==1) {
        return running_total;
    } else {
        return fact(1-1, 24*1);
    }
}

If bucla este adevărată

deci returnează running_total

Ieșirea pentru running_total = 24

În cele din urmă, rezultatul din fact(4,1) = 24

Brad Gilbert

aici este o versiune Perl 5 a tailrecsum menționată anterior.

sub tail_rec_sum($;$){
  my( $x,$running_total ) = (@_,0);

  return $running_total unless $x;

  @_ = ($x-1,$running_total+$x);
  goto &tail_rec_sum; # throw away current stack frame
}

Acesta este un extras din Structura și interpretarea programelor de calculator despre recursivitatea cozii.

Atunci când contrastăm iterația și recursivitatea, trebuie să fim atenți să nu confundăm noțiunea de proces recursiv cu noțiunea de procedură recursivă. Atunci când descriem o procedură ca fiind recursivă, ne referim la faptul sintactic că definiția procedurii se referă (fie direct, fie indirect) la procedura însăși. Dar atunci când descriem un proces ca urmând un model care este, să zicem, liniar recursiv, vorbim despre modul în care evoluează procesul, nu despre sintaxa modului în care este scrisă o procedură. Poate părea deranjant faptul că ne referim la o procedură recursivă, cum ar fi fact-iter, ca generând un proces iterativ. Cu toate acestea, procesul este într-adevăr iterativ: Starea sa este captată complet de cele trei variabile de stare, iar un interpret trebuie să țină evidența a doar trei variabile pentru a executa procesul.

Unul dintre motivele pentru care distincția dintre proces și procedură poate fi confuză este faptul că majoritatea implementărilor limbajelor obișnuite (inclusiv Ada, Pascal și C) sunt concepute în așa fel încât interpretarea oricărei proceduri recursive consumă o cantitate de memorie care crește odată cu numărul de apeluri de procedură, chiar și atunci când procesul descris este, în principiu, iterativ. În consecință, aceste limbaje pot descrie procese iterative numai prin recurgerea la „construcții de buclă” cu scop special, cum ar fi do, repeat, until, for și while. Implementarea lui Scheme nu prezintă acest defect. Aceasta va executa un proces iterativ în spațiu constant, chiar dacă procesul iterativ este descris de o procedură recursivă. O implementare cu această proprietate se numește „tail-recursive”. În cazul unei implementări „tail-recursive”, iterația poate fi exprimată folosind mecanismul obișnuit de apelare a procedurilor, astfel încât construcțiile speciale de iterație sunt utile doar ca zahăr sintactic.

Comentarii

  • Am citit toate răspunsurile de aici și totuși aceasta este cea mai clară explicație care atinge miezul cu adevărat profund al acestui concept. Explică într-un mod atât de direct, încât totul pare atât de simplu și de clar. Iertați-mi impolitețea, vă rog. Mă face să simt cumva că celelalte răspunsuri nu dau în cap. Cred că acesta este motivul pentru care SICP este important. –  > Por englealuze.

Recursivitatea cozii este viața pe care o trăiești în acest moment. Reciclezi în mod constant același cadru de stivă, la nesfârșit, deoarece nu există niciun motiv sau mijloc de a te întoarce la un cadru „anterior”. Trecutul s-a terminat și s-a terminat, deci poate fi aruncat. Ai un singur cadru, care se mișcă mereu în viitor, până când procesul tău moare în mod inevitabil.

Analogia se rupe atunci când considerați că unele procese ar putea utiliza cadre suplimentare, dar sunt în continuare considerate „tail-recursive” dacă stiva nu crește la infinit.

Comentarii

  • nu se rupe sub tulburare de personalitate divizată interpretare. 🙂 A Societate a Minții; o Minte ca o Societate. 🙂 –  > Por Will Ness.
  • Wow! Ăsta este un alt mod de a gândi despre asta –  > Por sutanu dalui.

O recursivitate de coadă este o funcție recursivă în care funcția se apelează pe sine la sfârșitul („coada”) funcției în care nu se face niciun calcul după întoarcerea apelului recursiv. Multe compilatoare optimizează pentru a schimba un apel recursiv într-un apel recursiv de coadă sau într-un apel iterativ.

Luați în considerare problema calculului factorialului unui număr.

O abordare simplă ar fi următoarea:

  factorial(n):

    if n==0 then 1

    else n*factorial(n-1)

Să presupunem că apelați factorial(4). Arborele de recursivitate ar fi următorul:

       factorial(4)
       /        
      4      factorial(3)
     /             
    3          factorial(2)
   /                  
  2                factorial(1)
 /                       
1                       factorial(0)
                            
                             1    

Adâncimea maximă de recursivitate în cazul de mai sus este O(n).

Totuși, luați în considerare următorul exemplu:

factAux(m,n):
if n==0  then m;
else     factAux(m*n,n-1);

factTail(n):
   return factAux(1,n);

Arborele de recurență pentru factTail(4) ar fi::

factTail(4)
   |
factAux(1,4)
   |
factAux(4,3)
   |
factAux(12,2)
   |
factAux(24,1)
   |
factAux(24,0)
   |
  24

Și în acest caz, adâncimea maximă de recursivitate este O(n), dar niciunul dintre apeluri nu adaugă o variabilă suplimentară în stivă. Prin urmare, compilatorul poate renunța la stivă.

A coadă recursivă este o funcție recursivă în care ultima operație pe care o face înainte de a se întoarce este apelarea funcției recursive. Aceasta înseamnă că valoarea de întoarcere a apelului funcției recursive este returnată imediat. De exemplu, codul dvs. ar arăta astfel:

def recursiveFunction(some_params):
    # some code here
    return recursiveFunction(some_args)
    # no code after the return statement

Compilatoarele și interpretoarele care implementează optimizarea apelurilor de coadă sau eliminarea apelurilor de coadă pot optimiza codul recursiv pentru a preveni depășirea stivei. Dacă compilatorul sau interpretorul dumneavoastră nu implementează optimizarea apelurilor de coadă (cum ar fi interpretorul CPython), nu există niciun beneficiu suplimentar dacă vă scrieți codul în acest mod.

De exemplu, aceasta este o funcție factorială recursivă standard în Python:

def factorial(number):
    if number == 1:
        # BASE CASE
        return 1
    else:
        # RECURSIVE CASE
        # Note that `number *` happens *after* the recursive call.
        # This means that this is *not* tail call recursion.
        return number * factorial(number - 1)

Și aceasta este o versiune recursivă a funcției factoriale cu apelare de coadă:

def factorial(number, accumulator=1):
    if number == 0:
        # BASE CASE
        return accumulator
    else:
        # RECURSIVE CASE
        # There's no code after the recursive call.
        # This is tail call recursion:
        return factorial(number - 1, number * accumulator)
print(factorial(5))

(Rețineți că, deși este vorba de cod Python, interpretul CPython nu face optimizarea apelurilor de coadă, astfel încât aranjarea codului dvs. în acest mod nu conferă niciun beneficiu în timpul execuției).

Este posibil să trebuiască să vă faceți codul puțin mai greu de citit pentru a utiliza optimizarea apelului de coadă, așa cum se arată în exemplul factorial. (De exemplu, cazul de bază este acum un pic mai puțin intuitiv, iar accumulator este utilizat efectiv ca un fel de variabilă globală).

Dar avantajul optimizării apelului de coadă este că previne erorile de depășire a stivei. (Voi remarca faptul că puteți obține același beneficiu folosind un algoritm iterativ în loc de unul recursiv).

Supraîncărcarea stivei este cauzată atunci când pe stiva de apeluri au fost împinse prea multe obiecte cadru. Un obiect cadru este introdus în stiva de apeluri atunci când o funcție este apelată și este scos din stiva de apeluri atunci când funcția se întoarce. Obiectele cadru conțin informații, cum ar fi variabilele locale și linia de cod la care trebuie să se revină atunci când funcția se întoarce.

Dacă funcția recursivă efectuează prea multe apeluri recursive fără să se întoarcă, stiva de apeluri poate depăși limita de obiecte cadru. (Numărul variază în funcție de platformă; în Python este de 1000 de obiecte cadru în mod implicit). Acest lucru provoacă un depășire a stivei eroare. (Hei, de aici provine și numele acestui site!).

Cu toate acestea, dacă ultimul lucru pe care îl face funcția dvs. recursivă este să facă apelul recursiv și să returneze valoarea de întoarcere, atunci nu există niciun motiv pentru care trebuie să păstreze obiectul cadru curent trebuie să rămână pe stiva de apeluri. La urma urmei, dacă nu există niciun cod după apelul funcției recursive, nu există niciun motiv pentru a păstra variabilele locale ale obiectului cadru curent. Așadar, putem scăpa imediat de obiectul cadru curent, în loc să îl păstrăm în stiva de apeluri. Rezultatul final al acestui lucru este că stiva de apeluri nu crește în dimensiune și, prin urmare, nu se poate supraîncărca stiva.

Un compilator sau un interpretor trebuie să aibă optimizarea apelurilor de coadă ca o caracteristică pentru a putea recunoaște când poate fi aplicată optimizarea apelurilor de coadă. Chiar și în acest caz, este posibil să trebuiască să rearanjați codul din funcția dvs. recursivă pentru a utiliza optimizarea tail call și depinde de dvs. dacă această potențială scădere a lizibilității merită optimizarea.

Comentarii

  • „Recursivitate de coadă (denumită și optimizare a apelurilor de coadă sau eliminare a apelurilor de coadă)”. Nu; eliminarea apelurilor de coadă sau optimizarea apelurilor de coadă este ceva ce se poate aplicați la o funcție recursivă de coadă, dar nu sunt același lucru. Puteți scrie funcții cu recursivitate de coadă în Python (după cum arătați), dar acestea nu sunt mai eficiente decât o funcție non-recursivă de coadă, deoarece Python nu realizează optimizarea apelurilor de coadă. –  > Por chepner.
  • Înseamnă că dacă cineva reușește să optimizeze site-ul și să facă apelul recursiv tail-recursive nu am mai avea site-ul StackOverflow?! Este oribil. –  > Por Nadjib Mami.

Tail Recursion este destul de rapidă în comparație cu recursivitatea normală. este rapidă deoarece ieșirea apelului strămoșilor nu va fi scrisă în stivă pentru a păstra urma. dar în recursivitatea normală toate apelurile strămoșilor ies scrise în stivă pentru a păstra urma.

Pentru a înțelege unele dintre diferențele esențiale dintre recursivitatea cu apeluri la coadă și recursivitatea fără apeluri la coadă, putem explora implementările .NET ale acestor tehnici.

Iată un articol cu câteva exemple în C#, F# și C++CLI: Adventures in Tail Recursion în C#, F# și C++CLI.

C# nu optimizează recursivitatea apelurilor de coadă, în timp ce F# o face.

Diferențele de principiu implică buclele vs. Lambda calculus. C# este proiectat cu buclele în minte, în timp ce F# este construit pe baza principiilor Lambda calculus. Pentru o carte foarte bună (și gratuită) despre principiile Lambda calculus, consultați Structure and Interpretation of Computer Programs (Structura și interpretarea programelor de calculator), de Abelson, Sussman și Sussman.

În ceea ce privește apelurile de coadă în F#, pentru un articol introductiv foarte bun, a se vedea Introducere detaliată a apelurilor de coadă în F#. În cele din urmă, iată un articol care acoperă diferența dintre recursivitatea non-tail-call și recursivitatea tail-call (în F#): Tail-recursion vs. non-tail recursion în F sharp.

Dacă doriți să citiți despre unele dintre diferențele de proiectare ale recursivității tail-call între C# și F#, consultați Generating Tail-Call Opcode in C# și F#.

Dacă vă interesează suficient de mult încât să doriți să aflați ce condiții împiedică compilatorul C# să efectueze optimizări tail-call, consultați acest articol: Condițiile JIT CLR tail-call.

magice

Recursiunea înseamnă o funcție care se apelează pe sine. De exemplu:

(define (un-ended name)
  (un-ended 'me)
  (print "How can I get here?"))

Tail-Recursion înseamnă recursiunea care încheie funcția:

(define (un-ended name)
  (print "hello")
  (un-ended 'me))

Vedeți, ultimul lucru pe care îl face o funcție nesfârșită (procedură, în jargonul Scheme) este să se apeleze pe sine. Un alt exemplu (mai util) este:

(define (map lst op)
  (define (helper done left)
    (if (nil? left)
        done
        (helper (cons (op (car left))
                      done)
                (cdr left))))
  (reverse (helper '() lst)))

În procedura helper, ULTIMUL lucru pe care îl face dacă left nu este nil este să se apeleze pe sine (DUPĂ cons ceva și cdr ceva). Practic, acesta este modul în care se mapează o listă.

Recursiunea de coadă are marele avantaj că interpretul (sau compilatorul, în funcție de limbaj și furnizor) o poate optimiza și o poate transforma în ceva echivalent cu o buclă while. De fapt, în tradiția Scheme, majoritatea buclelor „for” și „while” sunt realizate într-o manieră tail-recursion (nu există for și while, din câte știu eu).

Există două tipuri de bază de recursiuni: recursivitate de cap și recursivitate de coadă.

În recursivitatea de cap, o funcție face apelul recursiv și apoi efectuează alte calcule, poate folosind, de exemplu, rezultatul apelului recursiv.

În cadrul unei recursivă de coadă toate calculele au loc mai întâi, iar apelul recursiv este ultimul lucru care se întâmplă.

Preluat din acest super minunat post. Vă rugăm să vă gândiți să o citiți.

Această întrebare are o mulțime de răspunsuri grozave… dar nu pot să nu intervin și eu cu o abordare alternativă a modului de definire a „recursivității cozii”, sau cel puțin a „recursivității cozii adecvate”. Și anume: ar trebui să o privim ca pe o proprietate a unei anumite expresii dintr-un program? Sau ar trebui să o privim ca pe o proprietate a unei implementare a unui limbaj de programare?

Pentru mai multe informații despre acest din urmă punct de vedere, există un clasic articol clasic de Will Clinger, „Proper Tail Recursion and Space Efficiency” (PLDI 1998), care a definit „recursivitatea corectă a cozii” ca o proprietate a implementării unui limbaj de programare. Definiția este construită astfel încât să permită ignorarea detaliilor de implementare (cum ar fi dacă stiva de apeluri este reprezentată efectiv prin intermediul stivei de execuție sau printr-o listă legată de cadre alocată în heap).

Pentru a realiza acest lucru, se utilizează analiza asimptotică: nu a timpului de execuție a programului, așa cum se întâmplă de obicei, ci mai degrabă a timpului de execuție a programului. utilizarea spațiului programului. În acest fel, utilizarea spațiului unei liste legate alocate în heap față de o stivă de apeluri în timp de execuție sfârșește prin a fi asimptotic echivalentă; astfel, se poate ignora acest detaliu de implementare a limbajului de programare (un detaliu care, cu siguranță, contează destul de mult în practică, dar care poate tulbura destul de mult apele atunci când se încearcă să se determine dacă o anumită implementare îndeplinește cerința de a fi „recursivă în funcție de proprietate”).

Lucrarea merită studiată cu atenție din mai multe motive:

  • Acesta oferă o definiție inductivă a expresii de coadă și apeluri de coadă ale unui program. (O astfel de definiție și de ce sunt importante astfel de apeluri pare să fie subiectul majorității celorlalte răspunsuri date aici).

    Iată aceste definiții, doar pentru a oferi o imagine a textului:

    Definiția 1 expresii de coadă ale unui program scris în Core Scheme sunt definite inductiv după cum urmează.

    1. Corpul unei expresii lambda este o expresie de coadă
    2. Dacă (if E0 E1 E2) este o expresie de coadă, atunci atât E1 și E2 sunt expresii de coadă.
    3. Nimic altceva nu este o expresie de coadă.

    Definiția 2 A apel de coadă este o expresie de coadă care este un apel de procedură.

(un apel recursiv de coadă sau, după cum se spune în lucrare, „self-tail call” este un caz special de apel de coadă în care procedura este invocată de ea însăși).

  • Acesta oferă definiții formale pentru șase „mașini” diferite pentru evaluarea Core Scheme, fiecare mașină având același comportament observabil cu excepția pentru asimptotică clasa de complexitate spațială asimptotică în care se află fiecare.

    De exemplu, după ce oferă definiții pentru mașinile cu, respectiv, 1. gestionarea memoriei pe bază de stivă, 2. colectarea gunoiului, dar fără apeluri de coadă, 3. colectarea gunoiului și apeluri de coadă, lucrarea continuă cu strategii de gestionare a memoriei și mai avansate, cum ar fi 4. „evlis tail recursion”, în care mediul nu trebuie să fie păstrat pe parcursul evaluării ultimului argument al subexpresiei într-un apel de coadă, 5. reducerea mediului unei închideri la doar variabilele libere ale închiderii respective și 6. așa-numita semantică „safe-for-space”, definită de Appel și Shao.

  • Pentru a dovedi că mașinile aparțin de fapt la șase clase distincte de complexitate spațială, lucrarea oferă, pentru fiecare pereche de mașini comparate, exemple concrete de programe care vor expune o explozie asimptotică a spațiului pe o mașină, dar nu și pe cealaltă.


(Citind acum răspunsul meu, nu sunt sigur că am reușit să surprind de fapt punctele cruciale ale lucrării articolul lui Clinger. Dar, din păcate, nu pot dedica mai mult timp dezvoltării acestui răspuns în acest moment).

Mulți oameni au explicat deja recursivitatea aici. Aș dori să citez câteva gânduri despre unele avantaje pe care le oferă recursivitatea din cartea „Concurrency in .NET, Modern patterns of concurrent and parallel programming” de Riccardo Terrell:

„Recursivitatea funcțională este modul natural de a itera în FP, deoarece evită mutația stării. În timpul fiecărei iterații, o nouă valoare este trecută în constructorul buclei în loc să fie actualizată (mutată). În plus, o funcție recursivă poate fi compusă, ceea ce face ca programul să fie mai modular, precum și să introducă oportunități de exploatare a paralelizării.”

Iată, de asemenea, câteva note interesante din aceeași carte despre recursivitatea cozii:

Recursivitatea de tip tail-call este o tehnică care convertește o funcție recursivă obișnuită într-o versiune optimizată care poate gestiona intrări mari fără riscuri și efecte secundare.

NOTĂ Motivul principal pentru un tail call ca optimizare este îmbunătățirea localității datelor, a utilizării memoriei și a utilizării cache-ului. Prin efectuarea unui apel de coadă, apelantul utilizează același spațiu de stivă ca și apelantul. Acest lucru reduce presiunea asupra memoriei. Îmbunătățește marginal memoria cache, deoarece aceeași memorie este reutilizată pentru apelanții următori și poate rămâne în memoria cache, în loc să evacueze o linie de memorie cache mai veche pentru a face loc unei noi linii de memorie cache.

Este o formă specială de recursivitate în care ultima operație a unei funcții este un apel recursiv. Recursivitatea poate fi optimizată prin executarea apelului în cadrul stivei curente și returnarea rezultatului acestuia în loc de crearea unui nou cadru de stivă.

O funcție recursivă este recursivă la coadă atunci când apelul recursiv este ultimul lucru executat de funcție. De exemplu, următoarea funcție C++ print() este recurentă la coadă.

Un exemplu de funcție recursivă de coadă

    void print(int n) 
{ 
if (n < 0)  return; 
cout << " " << n; 
print(n-1);} 



// The last executed statement is recursive call 

Funcțiile recursive de coadă sunt considerate mai bune decât funcțiile care nu sunt recursive de coadă, deoarece compilatorul poate optimiza recursivitatea de coadă. Ideea utilizată de compilatoare pentru a optimiza funcțiile recursive de coadă este simplă: întrucât apelul recursiv este ultima instrucțiune, nu mai este nimic de făcut în funcția curentă, astfel încât salvarea cadrului de stivă al funcției curente nu este de folos.

O funcție este recursivă la coadă dacă fiecare caz recursiv este format din numai dintr-un apel la funcția însăși, eventual cu argumente diferite. Sau, recursivitatea de coadă este recursivitate fără muncă în așteptare. Rețineți că acesta este un concept independent de limbajul de programare.

Luați în considerare funcția definită ca:

g(a, b, n) = a * b^n

O posibilă formulare recursivă de coadă este:

g(a, b, n) | n is zero = a
           | n is odd  = g(a*b, b,   n-1)
           | otherwise = g(a,   b*b, n/2)

Dacă se examinează fiecare RHS din g(...) care implică un caz recursiv, veți descoperi că întregul corp al RHS este un apel la g(...), și doar că. Această definiție este recursivă de coadă.

Pentru comparație, o formulare nerecursivă la coadă ar putea fi:

g'(a, b, n) = a * f(b, n)
f(b, n) | n is zero = 1
        | n is odd  = f(b, n-1) * b
        | otherwise = f(b, n/2) ^ 2

Fiecare caz recursiv din f(...) are o anumită muncă în așteptare care trebuie să aibă loc după apelul recursiv.

Rețineți că atunci când am trecut de la g' la gam utilizat în mod esențial asociativitatea (și comutativitatea) înmulțirii. Acest lucru nu este un accident și majoritatea cazurilor în care va trebui să transformați recursivitatea în recursivitate de coadă vor utiliza astfel de proprietăți: dacă dorim să efectuăm cu nerăbdare o anumită muncă în loc să o lăsăm în așteptare, trebuie să folosim ceva de genul asociativității pentru a dovedi că răspunsul va fi același.

Apelurile recursive de coadă pot fi implementate cu un salt înapoi, spre deosebire de utilizarea unei stive pentru apelurile recursive normale. Rețineți că detectarea unui apel de coadă sau emiterea unui salt înapoi este de obicei simplă. Cu toate acestea, este adesea dificil să se rearanjeze argumentele astfel încât să fie posibilă o salt înapoi. Deoarece această optimizare nu este gratuită, implementările limbajului pot alege să nu implementeze această optimizare sau să solicite opțiunea de a opta prin marcarea apelurilor recursive cu o instrucțiune „tailcall” și/sau prin alegerea unei setări de optimizare mai mari.

Cu toate acestea, unele limbaje (de exemplu, Scheme) necesită toate implementări să optimizeze funcțiile recursive de coadă, poate chiar toate apelurile în poziție de coadă.

Salturile înapoi sunt, de obicei, abstractizate ca o buclă (while) în majoritatea limbajelor imperative, iar funcția tail-recursion, atunci când este optimizată la un salt înapoi, este izomorfă la o buclă.

Comentarii

  • deci, def f(x): f(x+1) este recursiv la coadă, dar def h(x): g(x+2) și def g(x): h(x-1) nu sunt, după definiția dvs. dar cred că și ele sunt TR. Scheme, în special, necesită ca toate apelurile de coadă să fie optimizate, nu doar apelurile de coadă către sine. (exemplul meu de funcții reciproc recursive de coadă este undeva la mijloc). –  > Por Will Ness.
  • Cred că „recursiv” înseamnă de obicei recursivitate directă, cu excepția cazului în care există un modificator „mutual”. Într-o oarecare legătură cu aceasta, mă aștept ca „apelurile recursive de coadă” să însemne salturi înapoi, în timp ce „apelurile normale de coadă” sau „apelurile între frați” sunt utilizate pentru salturi transversale generale. Mă aștept ca „mutually tail-recursive” să fie oarecum neobișnuit și, probabil, să fie suficient de bine acoperit de „tail call” (atât din punct de vedere semantic, cât și din punct de vedere al implementării). –  > Por Hari.
  • Îmi amintesc că am văzut undeva o frază „o funcție este recursivă (la coadă) dacă există în ea un apel de funcție (în poziția de coadă) care conduce în cele din urmă la această funcție să fie apelată din nou”… ceea ce este important, cred eu, este că atunci când spunem „recursiv în coadă” înseamnă că „poate rula în spațiu de stivă constant”, iar funcțiile mutual tail rec se încadrează cu siguranță în această categorie. –  > Por Will Ness.
  • Cred că ar trebui să separăm aspectul implementării (spațiu de stivă) de definiție. Definiția matematică uzuală a recursivității este o „funcție definită în termenii ei însăși”, iar dacă este definită indirect, este deseori denumită recursivă reciprocă. Cred că este util să definim recursivitatea de coadă astfel recursivitate fără muncă în așteptare (adică un salt înapoi). Sunt de acord că, pentru definirea limbajului, este mai avantajos să vorbim despre toate apelurile în poziția de coadă. –  > Por Hari.
  • @ Hari sugestie bună! –  > Por Will Ness.