recursivitate coada

Coada recursivitate - un caz special de recursivitate. în care orice apel recursiv este ultima tranzacție înainte de a reveni la funcția. [1] Acest tip de recursivitate este remarcabil prin faptul că acesta poate fi ușor înlocuită cu iterație de cod formal și garantate funcția de reglare corectă. Optimizarea recursivitatii cozii prin conversia într-o iterație plată este implementată în multe compilatoare de optimizare. Unele limbaje de programare funcționale, caietul de sarcini asigură o optimizare obligatorie coada-recursivitate.

recursie Coada este adesea folosit în programe limbaje de programare funcționale. Multe calcule cu privire la aceste limbi exprimate în mod natural sub forma funcțiilor recursive, și capacitatea de a înlocui automat recurență traducător coadă la iterație înseamnă că eficiența de calcul este egal cu codul echivalent scris într-un mod iterativ.

Creatorii Schema de limbaj funcțional. unul dintre dialectele Lisp. Am apreciat importanța recursivitatii coadă, astfel încât caietul de sarcini limba prescrise în fiecare compilator acestei limbi este obligatorie pentru a pune în aplicare de optimizare coada-recursivitate și să descrie exact setul de condiții care trebuie îndeplinite de către o funcție recursivă pentru a recursivitate a fost optimizat. [2]

Un exemplu de funcție recursivă pentru calculul factorialului. folosind recursia coadă limbajul de programare C și schema:

În acest exemplu, în ciuda faptului că funcția apel recursiv în text este în partea de jos, optimizarea automată recursie nu funcționează, pentru că, de fapt, ultima operație efectuată este operația de înmulțire cu n. și, astfel, starea recursivitatii cozii nu este realizată. Cele de mai sus-caudal variantele factoriale recursive sunt modificări mod evident, care are ca scop tocmai multiplicarea transferului. Aplicată la această metodă, de altfel, este una dintre modalitățile standard pentru a aduce o recursivitate la minte-coada recursiv. Acesta se află în faptul că setul de date locale, care trebuie să fie stocate atunci când un apel recursiv este transferat la parametrii apelului funcției. În cazul exemplului dat factoriale un astfel de parametru este acc variabilă. care are ca rezultat are loc acumularea.

In general, astfel de modificări pot fi suficient de non-triviale. În special, este posibil ca caudală-recursiv este doar una, cele mai „problematice“ ramură a execuției funcției, în timp ce altele sunt recursiv.