Svansrekursion är ett specialfall av rekursion , där varje rekursivt anrop är den sista operationen innan du återvänder från funktionen. [1] Denna typ av rekursion är anmärkningsvärd genom att den lätt kan ersättas av iteration genom formellt och garanterat korrekt omarrangering av funktionskoden. Svansrekursionsoptimering genom att konvertera den till platt iteration implementeras i många optimerande kompilatorer. I vissa funktionella programmeringsspråk garanterar specifikationen obligatorisk svansrekursionsoptimering.
En typisk mekanism för att implementera ett funktionsanrop är baserad på att lagra returadressen, parametrar och lokala variabler för funktionen i stacken och ser ut så här:
Med varje rekursivt funktionsanrop skapas alltså en ny uppsättning av dess parametrar och lokala variabler, som tillsammans med returadressen placeras på stacken, vilket begränsar det maximala rekursionsdjupet till stackens storlek. I rent funktionella eller deklarativa (som Prolog) språk, där rekursion är det enda möjliga sättet att organisera repetitiva beräkningar, blir denna begränsning extremt betydande, eftersom den i själva verket förvandlas till en gräns för antalet iterationer i alla cykliska beräkningar, ovan vilket ett stackspill kommer att inträffa .
Det är lätt att se att behovet av att utöka stacken för rekursiva anrop dikteras av kravet att återställa tillståndet för den anropande instansen av funktionen (det vill säga dess parametrar, lokala data och returadress) efter att ha återvänt från den rekursiva ringa upp. Men om det rekursiva anropet är den sista operationen innan den anropande funktionen avslutas och resultatet av den anropande funktionen bör vara resultatet att det rekursiva anropet kommer tillbaka, spelar det inte längre någon roll att spara sammanhanget - varken parametrar eller lokala variabler kommer att användas längre, och returadressen finns redan i högen. Därför, i en sådan situation, istället för ett fullfjädrat rekursivt funktionsanrop, kan du helt enkelt byta ut parametervärdena på stacken och överföra kontrollen till ingångspunkten. Så länge exekveringen går längs denna rekursiva gren kommer den vanliga slingan faktiskt att exekveras. När rekursionen slutar (det vill säga exekveringen passerar genom terminalgrenen och når returkommandot från funktionen), kommer returen att ske omedelbart till startpunkten varifrån den rekursiva funktionen anropades. På vilket djup av rekursion som helst, kommer stapeln inte att svämma över.
Svansrekursion används ofta i program i funktionella programmeringsspråk . Det är naturligt att uttrycka många beräkningar på sådana språk i form av rekursiva funktioner, och kompilatorns förmåga att automatiskt ersätta svansrekursion med iteration gör att den i termer av beräkningseffektivitet är lika med motsvarande kod skriven i iterativ form .
Skaparna av det funktionella språkschemat , en av dialekterna i Lisp , uppskattade vikten av svansrekursion så mycket att de i språkspecifikationen beordrade varje kompilator av detta språk att implementera svansrekursionsoptimering utan att misslyckas och beskrev den exakta uppsättningen villkor som en rekursiv funktion måste uppfyllas för att rekursionen ska optimeras i den. [2]
Ett exempel på en rekursiv funktion för faktoriell användning av svansrekursion i programmeringsspråken Scheme , C och Scala :
| Schema | C | Scala |
|---|---|---|
| ( definiera ( factorial n ) ( definiera ( fac-tider n acc ) ( if ( = n 0 ) acc ( fac-tider ( - n 1 ) ( * acc n )))) ( fac-tider n 1 )) | int fac_times ( int n , int acc ) { returnera ( n == 0 ) ? acc : fac_times ( n - 1 , acc * n ); } int factorial ( int n ) { return fac_times ( n , 1 ); } | @tailrec def factorial ( it : Int , resultat : Int = 1 ) : Int = { om ( det < 1 ) resultat annan faktoriell ( it - 1 , resultat * it ) } |
Det bör noteras att inte alla enkla rekursiva program är svansrekursiva. Mekanismen för optimering av svansrekursion som beskrivs ovan pålägger ett antal betydande begränsningar för de program som den kan tillämpas på, som utvecklare som förlitar sig på användningen av denna optimering måste ta hänsyn till.
Som ett exempel på en enkel rekursiv funktion som inte är svansrekursiv och inte automatiskt kan omvandlas till en iterativ funktion, här är det mest uppenbara rekursiva sättet att beräkna faktorial , som vanligtvis anges i läroböcker som det enklaste exemplet på en rekursiv funktion:
| Schema | C |
|---|---|
| ( definiera ( faktoriellt n ) ( om ( = n 0 ) 1 ( * n ( faktoriellt ( - n 1 )))))) | int factorial ( int n ) { returnera ( n == 0 ) ? 1 : n * faktorial ( n -1 ); } |
I det här exemplet, trots att det rekursiva anropet är på den sista platsen i funktionstexten, kommer automatisk optimering av rekursionen inte att fungera, eftersom den senast utförda operationen faktiskt är operationen att multiplicera med n , vilket betyder att svansen rekursionsvillkoret inte är uppfyllt. Ovanstående svansrekursiva varianter av att beräkna faktorialet är en modifiering av den uppenbara metoden, som just syftar till att överföra multiplikationsoperationen. Metoden som används för detta är för övrigt ett av de typiska sätten att föra rekursion till en svansrekursiv form. Det ligger i det faktum att en uppsättning lokal data som behöver sparas under ett rekursivt samtal överförs till funktionsanropsparametrarna. När det gäller de givna exemplen på faktoriell beräkning är denna parameter variabeln acci vilken resultatet ackumuleras.
I allmänhet kan sådana modifieringar vara ganska otriviala. I synnerhet är en variant möjlig när endast en, den mest "problematiska" grenen av funktionsutförandet görs svansrekursiv, medan resten förblir rekursiv.