algorithm - Wat is een staartrecursie?

Terwijl ik Lisp moet leren, ben ik de termijn tegengekomen Tail-recursive . Wat betekent het precies?

1, Autoriteit 100%

Overweeg een eenvoudige functie die de eerste N Natural Numbers toevoegt. (b.v. sum(5) = 1 + 2 + 3 + 4 + 5 = 15).

Hier is een eenvoudige JavaScript-implementatie die Recursion gebruikt:

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

Als u recsum(5)hebt gebeld, is dit wat de JavaScript-interpreter zou evalueren:

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

Merk op hoe elke recursieve oproep moet worden voltooid voordat de JavaScript-interpreter het werk is om het werk van de berekening van de som te berekenen.

Hier is een staartrecursieve versie van dezelfde functie:

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

Hier is de volgorde van gebeurtenissen die zouden optreden als u tailrecsum(5)noemde (die effectief zou zijn tailrecsum(5, 0), vanwege de standaard seconde argument).

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

In het staart-recursieve geval wordt bij elke evaluatie van de recursieve aanroep het running_totalbijgewerkt.

Opmerking: het oorspronkelijke antwoord gebruikte voorbeelden uit Python. Deze zijn gewijzigd in JavaScript, omdat Python-interpreters tail-call-optimalisatieniet ondersteunen. Hoewel optimalisatie van staartaanroepen onderdeel is van ECMAScript 2015 spec, ondersteunen de meeste JavaScript-interpreters het niet.

Antwoord 2, autoriteit 41%

In traditionele recursieis het typische model dat u eerst uw recursieve aanroepen uitvoert, en vervolgens de geretourneerde waarde van de recursieve aanroep neemt en het resultaat berekent. Op deze manier krijg je het resultaat van je berekening pas als je terug bent van elke recursieve aanroep.

In staartrecursievoert u eerst uw berekeningen uit en vervolgens voert u de recursieve aanroep uit, waarbij u de resultaten van uw huidige stap doorgeeft aan de volgende recursieve stap. Dit resulteert in de laatste instructie in de vorm van (return (recursive-function params)). In principe is de retourwaarde van een bepaalde recursieve stap hetzelfde als de retourwaarde van de volgende recursieve aanroep.

Het gevolg hiervan is dat als je eenmaal klaar bent om je volgende recursieve stap uit te voeren, je het huidige stapelframe niet meer nodig hebt. Dit zorgt voor enige optimalisatie. In feite zou je met een correct geschreven compiler nooit een stack overflow snickermoeten hebben met een recursieve staartaanroep. Gebruik gewoon het huidige stapelframe voor de volgende recursieve stap. Ik ben er vrij zeker van dat Lisp dit doet.

Antwoord 3, autoriteit 12%

Een belangrijk punt is dat staartrecursie in wezen gelijk is aan looping. Het is niet alleen een kwestie van compiler-optimalisatie, maar een fundamenteel feit over expressiviteit. Dit gaat in beide richtingen: je kunt elke lus van het formulier nemen

while(E) { S }; return Q

waar Een Quitdrukkingen zijn en Seen reeks instructies, en verander het in een recursieve staartfunctie

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

Natuurlijk moeten E, Sen Qgedefinieerd worden om een interessante waarde voor sommige variabelen te berekenen. Bijvoorbeeld de looping-functie

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

is gelijk aan de staart-recursieve functie(s)

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);
}

(Deze “omhulling” van de staart-recursieve functie met een functie met minder parameters is een algemeen functioneel idioom.)

Antwoord 4, autoriteit 8%

Dit fragment uit het boek Programming in Luatoont hoe je een juiste staartrecursie(in Lua, maar zou ook voor Lisp moeten gelden) en waarom het beter is.

Een tail call[tail recursion] is een soort goto-dressed
als een oproep. Een staartoproep vindt plaats wanneer a
functie roept een andere aan als de laatste
actie, dus het heeft niets anders te doen.
Bijvoorbeeld, in de volgende code,
de oproep naar gis een staartoproep:
function f (x)
  return g(x)
end
Nadat fgheeft aangeroepen, heeft het niets anders
Te doen. In dergelijke situaties kan het programma
hoeft niet terug te keren naar de roeping
functie wanneer de aangeroepen functie
loopt af. Daarom, na de staartoproep,
het programma hoeft er geen te bewaren
informatie over de aanroepfunctie
in de stapel. …

Omdat een goede staartaanroep no . gebruikt
stapelruimte, er is geen limiet aan de
aantal “geneste” staartaanroepen dat a
programma kan maken. We kunnen bijvoorbeeld
roep de volgende functie aan met any
nummer als argument; het zal nooit
overloop de stapel:
function foo (n)
  if n > 0 then return foo(n - 1) end
end
… Zoals ik al eerder zei, een staartoproep is een
soort van goto. Als zodanig een best nuttige
toepassing van de juiste staartaanroepen in
Lua is voor het programmeren van staatsmachines.
Dergelijke toepassingen kunnen elk vertegenwoordigen
staat door een functie; om van staat te veranderen
is om naar (of om te bellen) een specifieke
functie. Laten we als voorbeeld
overweeg een eenvoudig doolhofspel. Het doolhof
heeft meerdere kamers, elk met max
vier deuren: noord, zuid, oost en
westen. Bij elke stap voert de gebruiker een
bewegingsrichting. Als er een deur is
In die richting gaat de gebruiker naar
de bijbehorende kamer; anders de
programma drukt een waarschuwing af. Het doel is
om van een eerste kamer naar een finale te gaan
kamer.

Deze game is een typische staatsmachine,
waar de huidige kamer de staat is.
We kunnen een dergelijk doolhof met één implementeren
Functie voor elke kamer. We gebruiken staart
oproepen om van de ene kamer naar te gaan naar
een ander. Een klein doolhof met vier kamers
kan er als volgt uitzien:
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

Zie je, dus als je een recursieve oproep doet zoals:

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

Dit is geen staart recursief omdat je nog steeds dingen te doen hebt (voeg 1) in die functie nadat de recursieve oproep is gemaakt. Als u een zeer groot aantal invoert, zal het waarschijnlijk een stapeloverloop veroorzaken.

5, Autoriteit 5%

Regelmatige recursie gebruiken, duwt elke recursieve oproep een andere invoer naar de oproepstapel. Wanneer de recursie is voltooid, hoeft de app vervolgens elke ingang van alle weg terug naar beneden te brengen.

Met staartrecursie kan de compiler, afhankelijk van de taal, de stapel mogelijk samenvouwen tot één item, zodat u stapelruimte bespaart… Een grote recursieve query kan in feite een stapeloverloop veroorzaken.

In principe kunnen Tail-recursies in iteratie worden geoptimaliseerd.

Antwoord 6, autoriteit 4%

Het jargonbestand zegt het volgende over de definitie van staartrecursie:

staartrecursie/n./

Als je het nog niet zat bent, zie staartrecursie.

Antwoord 7, autoriteit 4%

In plaats van het met woorden uit te leggen, is hier een voorbeeld. Dit is een schemaversie van de faculteitsfunctie:

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

Hier is een versie van faculteit die staart-recursief is:

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

Je zult in de eerste versie opmerken dat de recursieve aanroep naar feit wordt ingevoerd in de vermenigvuldigingsexpressie, en daarom moet de status op de stapel worden opgeslagen bij het maken van de recursieve aanroep. In de staart-recursieve versie is er geen andere S-expressie die wacht op de waarde van de recursieve aanroep, en aangezien er verder geen werk te doen is, hoeft de status niet op de stapel te worden opgeslagen. In de regel gebruiken de staart-recursieve functies van het schema een constante stapelruimte.

Antwoord 8, autoriteit 3%

Staartrecursie verwijst naar de recursieve aanroep als laatste in de laatste logische instructie in het recursieve algoritme.

Typisch bij recursie heb je een base-casedie de recursieve oproepen stopt en de call-stack begint te laten knallen. Om een klassiek voorbeeld te gebruiken, hoewel meer C-achtig dan Lisp, illustreert de faculteitsfunctie staartrecursie. De recursieve aanroep vindt plaats nahet controleren van de basis-case voorwaarde.

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

De eerste aanroep van de faculteit is factorial(n)waarbij fac=1(standaardwaarde) en n het getal is waarvoor de faculteit moet worden berekend.

Antwoord 9, autoriteit 2%

Het betekent dat in plaats van de instructieaanwijzer op de stapel te moeten duwen, je gewoon naar de top van een recursieve functie kunt springen en de uitvoering kunt voortzetten. Hierdoor kunnen functies voor onbepaalde tijd terugkeren zonder dat de stapel overloopt.

Ik heb een bloggeschreven post over het onderwerp, met grafische voorbeelden van hoe de stapelframes eruit zien.

Antwoord 10

Hier is een snel codefragment waarin twee functies worden vergeleken. De eerste is traditionele recursie voor het vinden van de faculteit van een bepaald getal. De tweede maakt gebruik van staartrecursie.

Zeer eenvoudig en intuïtief te begrijpen.

Een gemakkelijke manier om te bepalen of een recursieve functie een staart-recursie is, is als deze een concrete waarde retourneert in het basisgeval. Dit betekent dat het geen 1 of waar of iets dergelijks teruggeeft. Het zal meer dan waarschijnlijk een variant van een van de methodeparameters retourneren.

Een andere manier is om te zien of de recursieve aanroep vrij is van enige toevoeging, rekenkunde, wijziging, enz… Dit betekent dat het niets anders is dan een pure recursieve aanroep.

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);
    }
}

11

In Java is hier een mogelijke staartrecursieve implementatie van de FIBONACCI-functie:

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);
}

Hiermee contrasteer dit met de standaard recursieve implementatie:

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

12

Ik ben geen Lisp-programmeur, maar ik denk dit zal helpen.

In principe is het een stijl van programmering zodanig dat de recursieve oproep het laatste is dat u doet.

Antwoord 13

Hier is een Common Lisp-voorbeeld dat faculteiten uitvoert met behulp van staartrecursie. Vanwege het stapelloze karakter zou men waanzinnig grote factoriële berekeningen kunnen uitvoeren …

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

En dan zou je voor de lol (format nil "~R" (! 25))

Antwoord 14

Kortom, een staartrecursie heeft de recursieve aanroep als de laatste-instructie in de functie, zodat deze niet hoeft te wachten op de recursieve aanroep.

Dus dit is een staartrecursie, d.w.z. N(x – 1, p * x) is de laatste instructie in de functie waarbij de compiler slim uitzoekt dat deze kan worden geoptimaliseerd tot een for-loop (factorieel). De tweede parameter p draagt de tussenproductwaarde.

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

Dit is de niet-staart-recursieve manier om de bovenstaande faculteitsfunctie te schrijven (hoewel sommige C++-compilers deze toch kunnen optimaliseren).

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

maar dit is niet:

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

Ik heb een lang bericht geschreven met de titel “Staartrecursie begrijpen – Visual Studio C++ – Assemblageweergave“

Antwoord 15

hier is een Perl 5-versie van de eerder genoemde functie tailrecsum.

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
}

Antwoord 16

Dit is een fragment uit Structuur en interpretatie van computerprogramma’sover staartrecursie.

Bij het contrasteren tussen iteratie en recursie, moeten we oppassen dat we niet
verwarren de notie van een recursief proces met de notie van a
recursieve procedure. Wanneer we een procedure als recursief beschrijven, zijn we:
verwijzend naar het syntactische feit dat de proceduredefinitie verwijst
(direct of indirect) op de procedure zelf. Maar wanneer we
een proces beschrijven als het volgen van een patroon dat bijvoorbeeld lineair is
recursief, we hebben het over hoe het proces evolueert, niet over
de syntaxis van hoe een procedure is geschreven. Het lijkt misschien verontrustend dat
we verwijzen naar een recursieve procedure zoals fact-iter als het genereren van an
iteratief proces. Het proces is echter echt iteratief: zijn toestand
wordt volledig vastgelegd door zijn drie toestandsvariabelen, en an
tolk hoeft slechts drie variabelen bij te houden om
voer het proces uit.

Een reden waarom het onderscheid tussen proces en procedure kan zijn:
verwarrend is dat de meeste implementaties van gemeenschappelijke talen (inclusief Ada, Pascal en
C) zijn zo ontworpen dat de interpretatie van recursieve
procedure verbruikt een hoeveelheid geheugen die groeit met het aantal
procedureaanroepen, zelfs wanneer het beschreven proces in principe
iteratief. Als gevolg hiervan kunnen deze talen iteratief
processen alleen door toevlucht te nemen tot speciale “looping-constructies”
zoals doen, herhalen, tot, voor en terwijl. De implementatie van
Scheme deelt dit gebrek niet. Het
zal een iteratief proces in constante ruimte uitvoeren, zelfs als de
iteratief proces wordt beschreven door een recursieve procedure. Een
implementatie met deze eigenschap heet staart-recursief.Met a
staart-recursieve implementatie, iteratie kan worden uitgedrukt met behulp van de
gewone procedure-aanroepmechanisme, zodat speciale iteratie
constructen zijn alleen bruikbaar als syntactische suiker.

Antwoord 17

Staartrecursie is het leven dat je nu leidt. Je recyclet constant hetzelfde stapelframe, steeds opnieuw, omdat er geen reden of middel is om terug te keren naar een “vorig” frame. Het verleden is voorbij en klaar, dus het kan worden weggegooid. Je krijgt één frame, voor altijd in de toekomst, totdat je proces onvermijdelijk sterft.

_{De analogie vervalt als je bedenkt dat sommige processen extra frames kunnen gebruiken, maar nog steeds als staart-recursief worden beschouwd als de stapel niet oneindig groeit.}

Antwoord 18

Een staartrecursie is een recursieve functie waarbij de functie aanroept
zichzelf aan het einde (“staart”) van de functie waarin geen berekening is
gedaan na de terugkeer van recursieve oproep. Veel compilers optimaliseren om
verander een recursieve oproep in een recursieve staart of een iteratieve oproep.

Beschouw het probleem van het berekenen van de faculteit van een getal.

Een directe benadering zou zijn:

 factorial(n):
    if n==0 then 1
    else n*factorial(n-1)

Stel dat je faculteit(4) aanroept. De recursieboom zou zijn:

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

De maximale recursiediepte in het bovenstaande geval is O(n).

Beschouw echter het volgende voorbeeld:

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

Recursieboom voor factTail(4) zou zijn:

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

Ook hier is de maximale recursiediepte O(n), maar geen van de aanroepen voegt een extra variabele toe aan de stapel. Daarom kan de compiler een stapel afschaffen.

Antwoord 19

Een recursieve staartfunctie is een recursieve functie waarbij de laatste bewerking die het doet voordat het terugkeert, de recursieve functieaanroep is. Dat wil zeggen, de geretourneerde waarde van de recursieve functieaanroep wordt onmiddellijk geretourneerd. Uw code ziet er bijvoorbeeld als volgt uit:

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

Compilers en interpreters die tail-call-optimalisatieof tail-call-eliminatieimplementeren, kunnen recursieve code optimaliseren om stack-overflows te voorkomen. Als uw compiler of interpreter geen optimalisatie van staartaanroepen implementeert (zoals de CPython-interpreter), heeft het geen bijkomend voordeel om uw code op deze manier te schrijven.

Dit is bijvoorbeeld een standaard recursieve factoriële functie in 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)

En dit is een recursieve versie van de faculteitsfunctie:

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))

(Merk op dat hoewel dit Python-code is, de CPython-interpreter geen staartoproepoptimalisatie uitvoert, dus als u uw code zo rangschikt, levert dit geen runtime-voordeel op.)

Misschien moet u uw code wat onleesbaarder maken om gebruik te kunnen maken van staartoproepoptimalisatie, zoals weergegeven in het voorbeeld van de faculteit. (Het basisscenario is nu bijvoorbeeld een beetje onintuïtief en de parameter accumulatorwordt effectief gebruikt als een soort globale variabele.)

Maar het voordeel van tail-call-optimalisatie is dat het stack-overflow-fouten voorkomt. (Ik merk op dat u hetzelfde voordeel kunt behalen door een iteratief algoritme te gebruiken in plaats van een recursief algoritme.)

Stackoverflows worden veroorzaakt wanneer er te veel frame-objecten op de aanroepstack zijn geduwd. Een frame-object wordt op de call-stack geduwd wanneer een functie wordt aangeroepen en van de call-stack geduwd wanneer de functie terugkeert. Frame-objecten bevatten informatie zoals lokale variabelen en naar welke regel code moet worden teruggekeerd wanneer de functie terugkeert.

Als uw recursieve functie te veel recursieve aanroepen doet zonder terug te keren, kan de aanroepstapel de frame-objectlimiet overschrijden. (Het aantal verschilt per platform; in Python zijn dit standaard 1000 frame-objecten.) Dit veroorzaakt een stack overflow-fout. (Hé, daar komt de naam van deze website vandaan!)

Als het laatste wat uw recursieve functie echter doet de recursieve aanroep is en de geretourneerde waarde retourneert, dan is er geen reden waarom het huidige frame-object op de aanroepstack moet blijven. Immers, als er geen code is na de recursieve functieaanroep, is er geen reden om vast te houden aan de lokale variabelen van het huidige frame-object. Dus we kunnen het huidige frame-object onmiddellijk verwijderen in plaats van het op de call-stack te houden. Het eindresultaat hiervan is dat uw call-stack niet groter wordt en dus niet kan overlopen.

Een compiler of interpreter moet tail-call-optimalisatie als functie hebben om te kunnen herkennen wanneer tail-call-optimalisatie kan worden toegepast. Zelfs dan kan het zijn dat u de code in uw recursieve functie moet herschikken om gebruik te maken van staartaanroepoptimalisatie, en het is aan u of deze potentiële afname in leesbaarheid de optimalisatie waard is.

Antwoord 20

Staartrecursie is vrij snel in vergelijking met normale recursie.
Het is snel omdat de uitvoer van de voorouders-aanroep niet in de stapel wordt geschreven om het spoor te behouden.
Maar bij normale recursie roept alle voorouders output aan die in de stapel is geschreven om het spoor te behouden.

Antwoord 21

Om enkele van de belangrijkste verschillen tussen tail-call-recursie en non-tail-call-recursie te begrijpen, kunnen we de .NET-implementaties van deze technieken onderzoeken.

Hier is een artikel met enkele voorbeelden in C#, F# en C++\CLI: Adventures in Tail Recursion in C#, F# en C++\CLI.

C# optimaliseert niet voor tail-call-recursie, terwijl F# dat wel doet.

De verschillen in principe hebben betrekking op lussen versus Lambda-calculus. C# is ontworpen met lussen in het achterhoofd, terwijl F# is gebouwd op basis van de principes van Lambda-calculus. Voor een zeer goed (en gratis) boek over de principes van Lambda-calculus, zie Structure and Interpretation of Computer Programs, door Abelson, Sussman en Sussman.

Over staartaanroepen in F#, zie voor een zeer goed inleidend artikel Gedetailleerde introductie tot staartoproepen in F#. Ten slotte is hier een artikel dat het verschil behandelt tussen non-tail-recursie en tail-call-recursie (in F#): Staartrecursie vs. niet-staartrecursie in Fis.

Als u meer wilt weten over enkele ontwerpverschillen van tail-call-recursie tussen C# en F#, gaat u naar Tail-Call Opcode genereren in C# en F#.

Als je er genoeg om geeft om te weten welke omstandigheden de C#-compiler ervan weerhouden om tail-call-optimalisaties uit te voeren, bekijk dan dit artikel: JIT CLR tail-call voorwaarden.

Antwoord 22

Recursie betekent een functie die zichzelf aanroept. Bijvoorbeeld:

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

Staartrecursie betekent de recursie die de functie afsluit:

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

Kijk, het laatste wat een functie zonder einde (procedure, in Schema-jargon) doet, is zichzelf aanroepen. Een ander (nuttiger) voorbeeld is:

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

In de helperprocedure is het LAATSTE wat het doet als links niet nul is, zichzelf aanroepen (NA tegens iets en cdr iets). Dit is eigenlijk hoe je een lijst in kaart brengt.

De staart-recursie heeft een groot voordeel dat de interpreter (of compiler, afhankelijk van de taal en leverancier) deze kan optimaliseren en transformeren in iets dat gelijk is aan een while-lus. In feite, in de traditie van het schema, worden de meeste “voor” en “terwijl” lussen gedaan op een staart-recursie-manier (er is geen voor en terwijl, voor zover ik weet).

Antwoord 23

Er zijn twee basissoorten recursie: koprecursieen staartrecursie.

In head recursiedoet een functie zijn recursieve aanroep en dan
voert nog wat berekeningen uit, misschien met behulp van het resultaat van de
recursieve oproep, bijvoorbeeld.

In een staart recursievefunctie gebeuren alle berekeningen eerst en
de recursieve oproep is het laatste wat er gebeurt.

Genomen uit ditsuper geweldige bericht .
Overweeg om het te lezen.

Antwoord 24

Deze vraag heeft veel goede antwoorden… maar ik kan het niet laten om een alternatieve kijk te geven op het definiëren van “staartrecursie”, of op zijn minst “juiste staartrecursie”. Namelijk: moet je het zien als een eigenschap van een bepaalde expressie in een programma? Of moet je het zien als een eigenschap van een implementatie van een programmeertaal?

Voor meer informatie over de laatste visie is er een klassieke paperdoor Will Clinger, “Proper Tail Recursion and Space Efficiency” (PLDI 1998), dat “juiste staartrecursie” definieerde als een eigenschap van een programmeertaalimplementatie . De definitie is zo geconstrueerd dat men implementatiedetails kan negeren (zoals of de call-stack daadwerkelijk wordt weergegeven via de runtime-stack of via een heap-toegewezen gekoppelde lijst met frames).

Om dit te bereiken gebruikt het asymptotische analyse: niet van de uitvoeringstijd van het programma zoals men gewoonlijk ziet, maar eerder van het ruimtegebruikvan het programma. Op deze manier wordt het ruimtegebruik van een aan een heap toegewezen gekoppelde lijst versus een runtime-aanroepstack uiteindelijk asymptotisch equivalent; dus men mag dat implementatiedetail van de programmeertaal negeren (een detail dat in de praktijk zeker van belang is, maar het water behoorlijk kan vertroebelen wanneer men probeert te bepalen of een bepaalde implementatie voldoet aan de vereiste om “eigendomsstaart recursief” te zijn )

Het artikel is om een aantal redenen de moeite van het bestuderen waard:

Het geeft een inductieve definitie van de staartuitdrukkingenen staartaanroepenvan een programma. (Een dergelijke definitie, en waarom dergelijke oproepen belangrijk zijn, lijkt het onderwerp te zijn van de meeste andere antwoorden die hier worden gegeven.)

Hier zijn die definities, om een idee van de tekst te geven:
Definitie 1De staartuitdrukkingenvan een programma geschreven in Core Scheme worden als volgt inductief gedefinieerd.
1. De body van een lambda-expressie is een staartexpressie
2. Als (if E0 E1 E2)een staartuitdrukking is, dan zijn zowel E1als E2staartuitdrukkingen.
3. Niets anders is een staartuitdrukking.
Definitie 2Een staartaanroepis een staartuitdrukking die een procedureaanroep is.

(een recursieve staartaanroep, of zoals de krant zegt, “zelfbewakende aanroep” is een speciaal geval van een staartaanroep waarbij de procedure zelf wordt aangeroepen.)

Het biedt formele definities voor zes verschillende “machines” voor het evalueren van het kernschema, waarbij elke machine hetzelfde waarneembare gedrag heeft behalvevoor de asymptotischeruimtecomplexiteitsklasse dat elk binnen is.

Na bijvoorbeeld definities te hebben gegeven voor machines met respectievelijk 1. stack-gebaseerd geheugenbeheer, 2. garbage collection maar geen tail calls, 3. garbage collection en tail calls, gaat het artikel verder met nog geavanceerdere opslagbeheerstrategieën , zoals 4. “evlis-staartrecursie”, waarbij de omgeving niet hoeft te worden behouden tijdens de evaluatie van het laatste subuitdrukkingsargument in een staartaanroep, 5. de omgeving van een afsluiting tot slechtsreduceert em>de vrije variabelen van die sluiting, en 6. de zogenaamde “safe-for-space”-semantiek zoals gedefinieerd door Appel en Shao.
Om te bewijzen dat de machines eigenlijk tot zes verschillende ruimtecomplexiteitsklassen behoren, geeft het artikel voor elk paar machines dat wordt vergeleken, concrete voorbeelden van programma’s die asymptotische ruimte-opgeblazenheid op één machine blootleggen, maar niet de andere.

(Als ik mijn antwoord nu lees, weet ik niet zeker of het me is gelukt om de cruciale punten van de Clinger paper. Maar helaas, ik kan op dit moment niet meer tijd besteden aan het ontwikkelen van dit antwoord. )

Antwoord 25

Veel mensen hebben recursie hier al uitgelegd. Ik zou graag een paar gedachten willen citeren over enkele voordelen die recursie biedt uit het boek “Concurrency in .NET, Modern patterns of concurrent and parallel programming” van Riccardo Terrell:

“Functionele recursie is de natuurlijke manier om in FP te itereren omdat het
vermijdt staatsmutatie. Tijdens elke iteratie wordt een nieuwe waarde doorgegeven
in plaats daarvan in de lusconstructor om te worden bijgewerkt (gemuteerd). In
daarnaast kan een recursieve functie worden samengesteld, waardoor uw programma
meer modulair, evenals het introduceren van mogelijkheden om te exploiteren
parallellisatie.”

Hier zijn ook enkele interessante opmerkingen uit hetzelfde boek over staartrecursie:

Tail-call recursie is een techniek die een regulier recursief converteert
functie in een geoptimaliseerde versie die grote invoer aankan
zonder risico’s en bijwerkingen.

OPMERKING De belangrijkste reden voor een staartaanroep als optimalisatie is om:
de gegevenslocatie, het geheugengebruik en het cachegebruik te verbeteren. Door een staart te doen
oproep gebruikt, gebruikt de gebelde dezelfde stapelruimte als de beller. Dit vermindert
geheugen druk. Het verbetert de cache marginaal omdat hetzelfde
geheugen wordt hergebruikt voor volgende bellers en kan in de cache blijven,
in plaats van een oudere cacheregel te verwijderen om ruimte te maken voor een nieuwe cache
lijn.

Antwoord 26

Het is een speciale vorm van recursie waarbij de laatste bewerking van een functie een recursieve aanroep is. De recursie kan worden geoptimaliseerd door de aanroep in het huidige stapelframe uit te voeren en het resultaat te retourneren in plaats van een nieuw stapelframe te maken.

Een recursieve functie is staart-recursief wanneer recursieve aanroep het laatste is dat door de functie wordt uitgevoerd. De volgende C++-functie print() is bijvoorbeeld staart recursief.

Een voorbeeld van een recursieve staartfunctie

   void print(int n) 
{ 
if (n < 0)  return; 
cout << " " << n; 
print(n-1);} 
// The last executed statement is recursive call

De staart recursieve functies worden als beter beschouwd dan niet-staart recursieve functies, aangezien staart-recursie door de compiler kan worden geoptimaliseerd. Het idee dat door compilers wordt gebruikt om staart-recursieve functies te optimaliseren is eenvoudig, aangezien de recursieve aanroep de laatste instructie is, is er niets meer te doen in de huidige functie, dus het heeft geen zin om het stapelframe van de huidige functie op te slaan.

Antwoord 27

Een functie is staart recursief als elk recursief geval alleenbestaat uit een aanroep van de functie zelf, mogelijk met verschillende argumenten. Of, staartrecursie is recursie zonder wachtend werk. Merk op dat dit een programmeertaalonafhankelijk concept is.

Beschouw de functie gedefinieerd als:

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

Een mogelijke staart-recursieve formulering is:

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

Als je elke RHS van g(...)bekijkt die een recursief geval betreft, zul je zien dat het hele lichaam van de RHS een aanroep is naar g(...), en alleendat. Deze definitie is staart recursief.

Ter vergelijking: een niet-staart-recursieve formulering kan zijn:

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

Elke recursieve case in f(...)heeft wat in afwachting van werkdat moet gebeuren na de recursieve aanroep.

Merk op dat toen we van g'naar ggingen, we essentieel gebruik maakten van associativiteit
(en commutativiteit) van vermenigvuldiging. Dit is geen toeval, en de meeste gevallen waarin je recursie moet transformeren naar staart-recursie, zullen gebruik maken van dergelijke eigenschappen: als we gretig wat werk willen doen in plaats van het te laten wachten, moeten we zoiets als associativiteit gebruiken om te bewijzen dat het antwoord hetzelfde zal zijn.

Staart recursieve aanroepen kunnen worden geïmplementeerd met een achterwaartse sprong, in tegenstelling tot het gebruik van een stapel voor normale recursieve aanroepen. Merk op dat het detecteren van een staartoproep of het uitzenden van een achterwaartse sprong meestal eenvoudig is. Het is echter vaak moeilijk om de argumenten zo te herschikken dat de achterwaartse sprong mogelijk is. Aangezien deze optimalisatie niet gratis is, kunnen taalimplementaties ervoor kiezen deze optimalisatie niet te implementeren, of een opt-in vereisen door recursieve oproepen te markeren met een ‘tailcall’-instructie en/of een hogere optimalisatie-instelling te kiezen.

Sommige talen (bijv. Schema) vereisen echter alleimplementaties om staart-recursieve functies te optimaliseren, misschien zelfs alle aanroepen in staartpositie.

Achterwaartse sprongen worden in de meeste gebiedende talen meestal geabstraheerd als een (terwijl) lus, en staartrecursie, wanneer geoptimaliseerd voor een achterwaartse sprong, is isomorf met lusvorming.

Wat is een staartrecursie?