Farok rekurziója

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.

Leírás

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:

  1. A hívási ponton a függvénynek átadott paraméterek és a visszatérési cím a verembe kerülnek.
  2. A meghívott függvény futás közben elhelyezi saját helyi változóit a veremben.
  3. A számítások befejeztével a függvény törli a verem helyi változóit, az eredményt kiírja (általában valamelyik processzor regiszterbe).
  4. A függvény visszatérési utasítása kidobja a visszatérési címet a veremből, és erre a címre ugrik. Akár közvetlenül a függvény visszatérése előtt, akár közvetlenül utána, a verem törlődik a paraméterektől.

Í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.

Alkalmazás

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éldák

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

Problémák

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.

Lásd még

Jegyzetek

  1. Paul E. Black, " tail recursion ", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, szerk., US National Institute of Standards and Technology. 2008. augusztus 14.  (  Hozzáférés: 2011. október 6.)
  2. Revised 5 Report on the Algorithmic Language Scheme  ( Hozzáférés  : 2010. szeptember 16.)