A farokrekurzió a rekurzió egy speciális esete , amelyben minden rekurzív hívás az utolsó művelet a függvényből való visszatérés előtt. [1] Ez a fajta rekurzió figyelemre méltó, hogy könnyen helyettesíthető iterációval a függvénykód formális és garantáltan helyes átrendezésével. A farok rekurzió optimalizálása annak lapos iterációvá alakításával számos optimalizáló fordítóban megvalósul. Néhány funkcionális programozási nyelvben a specifikáció garantálja a kötelező farokrekurzió optimalizálást.
A függvényhívás megvalósításának egy tipikus mechanizmusa a függvény visszatérési címének, paramétereinek és helyi változóinak a veremben való tárolásán alapul, és így néz ki:
Így minden rekurzív függvényhívásnál annak paramétereiből és helyi változóiból egy új halmaz jön létre, amely a visszatérési címmel együtt a veremre kerül, ami a maximális rekurziós mélységet a verem méretére korlátozza. A tisztán funkcionális vagy deklaratív (mint például a Prolog) nyelvekben, ahol a rekurzió az egyetlen lehetséges módja az ismétlődő számítások megszervezésének, ez a korlátozás rendkívül jelentőssé válik, mivel valójában korlátozza az iterációk számát minden ciklikus számításban. amely veremtúlcsordulás következik be .
Könnyen belátható, hogy a rekurzív hívások veremének bővítésének szükségességét az a követelmény diktálja, hogy vissza kell állítani a függvény hívó példányának állapotát (vagyis paramétereit, helyi adatait és visszatérési címét) a rekurzívból való visszatérés után. hívás. De ha a rekurzív hívás az utolsó művelet a hívó függvényből való kilépés előtt, és a hívó függvény eredménye az az eredmény, hogy a rekurzív hívás visszatér, akkor a kontextus mentése már nem számít - sem a paraméterek, sem a helyi változók nem kerülnek felhasználásra, és a visszaküldési cím már a veremben van. Ezért ilyen helyzetben a teljes értékű rekurzív függvényhívás helyett egyszerűen lecserélheti a veremben lévő paraméterértékeket, és átviheti a vezérlést a belépési pontra. Mindaddig, amíg a végrehajtás ezen a rekurzív ágon halad, valójában a szokásos ciklus kerül végrehajtásra. Amikor a rekurzió véget ér (vagyis a végrehajtás áthalad a terminál ágon és eléri a függvény visszatérési parancsát), a visszatérés azonnal megtörténik arra a kiindulási pontra, ahonnan a rekurzív függvény meghívásra került. Így a rekurzió bármely mélységében a verem nem fog túlcsordulni.
A farokrekurziót gyakran használják a funkcionális programozási nyelvek programjaiban . Természetes, hogy sok számítást ilyen nyelveken rekurzív függvények formájában fejezünk ki, és a fordító azon képessége, hogy a farokrekurziót automatikusan iterációra cserélje, azt jelenti, hogy a számítási hatékonyság szempontjából megegyezik az iteratív formában írt ekvivalens kóddal. .
A Lisp egyik dialektusa, a funkcionális nyelvi séma megalkotói annyira felértékelték a farokrekurzió fontosságát, hogy a nyelvi specifikációban megparancsolták a nyelv minden fordítójának, hogy hiba nélkül hajtsák végre a farokrekurzió optimalizálását, és leírták a pontos feltételeket, egy rekurzív függvénynek meg kell felelnie ahhoz, hogy a rekurzió optimalizálva legyen benne. [2]
Példa a faktoriális rekurzív függvényre farokrekurziót használva a Scheme , C és Scala programozási nyelvekben :
| Rendszer | C | Scala |
|---|---|---|
| ( define ( faktoriális n ) ( define ( fac-times n acc ) ( if ( = n 0 ) acc ( fac-times ( - n 1 ) ( * acc n )))) ( fac-times n 1 )) | int fac_times ( int n , int acc ) { visszatérés ( n == 0 ) ? acc : fac_times ( n - 1 , acc * n ); } int faktoriális ( int n ) { return fac_times ( n , 1 ); } | @tailrec def faktoriális ( it : Int , eredmény : Int = 1 ) : Int = { ha ( ez < 1 ) eredmény más faktoriális ( it - 1 , eredmény * it ) } |
Meg kell jegyezni, hogy nem minden egyszerű rekurzív program farokrekurzív. A fent leírt farokrekurziós optimalizálási mechanizmus számos jelentős korlátozást támaszt azokkal a programokkal szemben, amelyekre alkalmazható, amelyeket figyelembe kell venniük azoknak a fejlesztőknek, akik ezt az optimalizációt használják.
Példaként egy egyszerű rekurzív függvényre, amely nem farokrekurzív, és nem konvertálható automatikusan iteratív függvényté, itt van a faktoriális kiszámításának legkézenfekvőbb rekurzív módja , amelyet a tankönyvek általában a rekurzív függvény legegyszerűbb példájaként adnak meg:
| Rendszer | C |
|---|---|
| ( define ( n faktoriális ) ( if ( = n 0 ) 1 ( * n ( faktoriális ( - n 1 ))))) | int faktoriális ( int n ) { visszatérés ( n == 0 ) ? 1 : n * faktoriális ( n -1 ); } |
Ebben a példában annak ellenére, hogy a rekurzív hívás az utolsó helyen van a függvényszövegben, a rekurzió automatikus optimalizálása nem működik, mivel valójában az utolsó művelet az n -nel való szorzás művelete , ami azt jelenti, hogy a farok rekurziós feltétel nem teljesül. A faktoriális számításának fenti farok-rekurzív változatai a nyilvánvaló módszer módosításai, amely pontosan a szorzási művelet átvitelére irányul. Az erre használt módszer egyébként az egyik tipikus módja annak, hogy a rekurziót farokrekurzív formába hozzuk. Ez abban rejlik, hogy a rekurzív hívás során elmentendő helyi adatok halmaza átkerül a függvényhívás paraméterei közé. Az adott faktorszámítási példák esetében ez a paraméter az a változó acc, amelyben az eredmény halmozódik.
Általában az ilyen módosítások meglehetősen nem triviálisak lehetnek. Konkrétan egy olyan változat lehetséges, amikor a függvényvégrehajtásnak csak egy, a „legproblémásabb” ága van farokrekurzív, míg a többi rekurzív marad.