Tail-rekursio on rekursion erikoistapaus , jossa mikä tahansa rekursiivinen kutsu on viimeinen operaatio ennen funktiosta paluuta. [1] Tämäntyyppinen rekursio on merkittävä siinä mielessä, että se voidaan helposti korvata iteraatiolla järjestämällä muodollisesti ja taatusti oikea funktiokoodin uudelleenjärjestely. Tail-rekursion optimointi muuttamalla se tasaiseksi iteraatioksi on toteutettu monissa optimointikääntäjissä. Joissakin toiminnallisissa ohjelmointikielissä spesifikaatio takaa pakollisen tail-rekursion optimoinnin.
Tyypillinen funktiokutsun toteuttamismekanismi perustuu funktion paluuosoitteen, parametrien ja paikallisten muuttujien tallentamiseen pinoon ja näyttää tältä:
Siten jokaisella rekursiivisella funktiokutsulla luodaan uusi joukko sen parametreja ja paikallisia muuttujia, jotka yhdessä paluuosoitteen kanssa sijoitetaan pinoon, mikä rajoittaa maksimirekursiosyvyyden pinon kokoon. Puhtaasti funktionaalisissa tai deklaratiivisissa (kuten Prolog) kielissä, joissa rekursio on ainoa mahdollinen tapa järjestää toistuvia laskutoimituksia, tästä rajoituksesta tulee erittäin merkittävä, koska itse asiassa se muuttuu iteraatioiden lukumäärän rajoitukseksi kaikissa syklisissä laskuissa, edellä. jossa pinon ylivuoto tapahtuu .
On helppo nähdä, että tarve laajentaa pinon rekursiivisia kutsuja sanelee vaatimus palauttaa funktion kutsuvan ilmentymän tila (eli sen parametrit, paikalliset tiedot ja paluuosoite) rekursiivisesta palaamisen jälkeen. soittaa puhelimella. Mutta jos rekursiivinen kutsu on viimeinen operaatio ennen kutsuvasta funktiosta poistumista ja kutsufunktion tuloksena pitäisi olla se, että rekursiivinen kutsu palaa, kontekstin tallennuksella ei ole enää väliä - parametreja tai paikallisia muuttujia ei enää käytetä, ja palautusosoite on jo pinossa. Siksi tällaisessa tilanteessa täysimittaisen rekursiivisen funktiokutsun sijaan voit yksinkertaisesti korvata pinon parametriarvot ja siirtää ohjauksen tulopisteeseen. Niin kauan kuin suoritus kulkee tätä rekursiivista haaraa pitkin, tavallinen silmukka itse asiassa suoritetaan. Kun rekursio päättyy (eli suoritus kulkee päätehaaran läpi ja saavuttaa funktion paluukäskyn), paluu tapahtuu välittömästi aloituspisteeseen, josta rekursiivinen funktio kutsuttiin. Siten pino ei vuoda yli millä tahansa rekursion syvyydellä.
Tail-rekursiota käytetään usein toiminnallisten ohjelmointikielien ohjelmissa . On luonnollista ilmaista monet laskennat tällaisilla kielillä rekursiivisten funktioiden muodossa, ja kääntäjän kyky korvata häntärekursio automaattisesti iteraatiolla tarkoittaa, että se on laskennallisen tehokkuuden kannalta yhtä suuri kuin vastaava iteratiiviseen muotoon kirjoitettu koodi. .
Funktionaalisen kieliskeeman , yhden Lispin murteista, luojat ymmärsivät tail-rekursion tärkeyden niin paljon, että he määräsivät kielimäärittelyssä jokaisen tämän kielen kääntäjän toteuttamaan virheetöntä tail-rekursion optimoinnin ja kuvasivat tarkan joukon ehtoja, jotka rekursiivisen funktion on täytettävä, jotta rekursio voidaan optimoida siinä. [2]
Esimerkki rekursiivisesta funktiosta faktoriaaliselle funktiolle, joka käyttää tail-rekursiota ohjelmointikielissä Scheme , C ja Scala :
| Kaavio | C | Scala |
|---|---|---|
| ( define ( factorial n ) ( define ( fac - kertaa n acc ) ( if ( = n 0 ) acc ( fac - kertaa ( - n 1 ) ( * acc n )))) ( fac - kertaa n 1 )) | int fac_times ( int n , int acc ) { paluu ( n == 0 ) ? acc : fac_times ( n - 1 , acc * n ); } int factorial ( int n ) { palauttaa fac_times ( n , 1 ); } | @tailrec def factorial ( it : Int , tulos : Int = 1 ) : Int = { jos ( se < 1 ) tulos muu kertoja ( it - 1 , tulos * se ) } |
On huomattava, että kaikki yksinkertaiset rekursiiviset ohjelmat eivät ole häntärekursiivisia. Yllä kuvattu tail-rekursion optimointimekanismi asettaa useita merkittäviä rajoituksia ohjelmille, joihin sitä voidaan soveltaa, jotka kehittäjien, jotka luottavat tämän optimoinnin käyttöön, on otettava huomioon.
Esimerkkinä yksinkertaisesta rekursiivisesta funktiosta, joka ei ole häntärekursiivinen ja jota ei voida automaattisesti muuntaa iteratiiviseksi funktioksi, tässä on ilmeisin rekursiivinen tapa laskea factorial , joka yleensä annetaan oppikirjoissa yksinkertaisimpana esimerkkinä rekursiivisesta funktiosta:
| Kaavio | C |
|---|---|
| ( define ( factorial n ) ( if ( = n 0 ) 1 ( * n ( factorial ( - n 1 ))))) | int factorial ( int n ) { paluu ( n == 0 ) ? 1 : n * tekijä ( n -1 ); } |
Tässä esimerkissä huolimatta siitä, että rekursiivinen kutsu on funktiotekstin viimeisellä paikalla, rekursion automaattinen optimointi ei toimi, koska itse asiassa viimeinen suoritettu operaatio on n :llä kertomisoperaatio , mikä tarkoittaa, että häntä rekursioehto ei täyty. Yllä olevat tail-rekursiiviset kertoimen laskemisen muunnelmat ovat muunnelmia ilmeisestä menetelmästä, joka on juuri suunnattu kertolaskuoperaation siirtämiseen. Tähän käytetty menetelmä on muuten yksi tyypillisistä tavoista tuoda rekursio häntärekursiiviseen muotoon. Se johtuu siitä, että joukko paikallisia tietoja, jotka on tallennettava rekursiivisen kutsun aikana, siirretään funktiokutsuparametreihin. Annetuissa kertoimien laskennan esimerkeissä tämä parametri on muuttuja acc, johon tulos kerätään.
Yleensä tällaiset muutokset voivat olla melko ei-triviaaleja. Varsinkin variantti on mahdollinen, kun vain yksi, "ongelmallisin" funktion suorituksen haara tehdään tail-rekursiiviseksi, kun taas muut jäävät rekursiivisiksi.