Mikä on hännän rekursio?

Hännän rekursio on erityinen rekursiotapaus, jossa kutsuva toiminto ei enää laske rekursiivisen puhelun soittamisen jälkeen. Esimerkiksi funktio

 int f(int x, int y) { if (y == 0) { return x; } return f(x*y, y-1); } 

on hännän rekursiivinen (koska viimeinen käsky on rekursiivinen puhelu), kun taas tämä toiminto ei ole hännän rekursiivinen:

 int g(int x) { if (x == 1) { return 1; } int y = g(x-1); return x*y; } 

koska se suorittaa jonkin verran laskentaa rekursiivisen puhelun palattuaan.

Hännän rekursio on tärkeä, koska se voidaan toteuttaa tehokkaammin kuin yleinen rekursio. Kun soitamme normaalin rekursiivisen puhelun, meidän on työnnettävä paluuosoite puhelupinoon ja sitten siirryttävä kutsuttuun toimintoon. Tämä tarkoittaa, että tarvitsemme puhelupinon, jonka koko on lineaarinen rekursiivisten puheluiden syvyydessä. Kun meillä on hännän rekursio, tiedämme, että heti kun palaamme rekursiivisesta puhelusta, palaamme myös heti, jotta voimme ohittaa koko rekursiivisten toimintojen ketjun palaamisen ja palata suoraan alkuperäiselle soittajalle. ”Ei tarvitse puhelupinoa ollenkaan kaikille rekursiivisille puheluille, ja se voi toteuttaa viimeisen puhelun yksinkertaisena hyppynä, mikä säästää tilaa.

Kommentit

• kirjoitit ” Tämä tarkoittaa sitä, että emme ’ tarvitse puhelupinoa ollenkaan kaikille rekursiivisille puheluille ”. Puhelupino on aina olemassa, vain että paluuosoitetta ei tarvitse kirjoittaa puhelupinoon, eikö?
• Se riippuu jossain määrin laskentamallistasi 🙂 Mutta kyllä, todellisessa tietokoneessa puhelupino on edelleen olemassa, me ’ emme vain käytä sitä.
• Entä jos se ’ s viimeinen soita, mutta silmukkaa varten. Joten teet kaikki laskelmat yllä, mutta osa niistä for-silmukassa, kuten def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – tämä rekursiivinen ei ’ t päättyy.

Yksinkertaisesti sanottuna hännän rekursio on rekursio, jonka kääntäjä voi korvata rekursiivinen kutsu ”goto” -komennolla, joten käännetyn version ei tarvitse lisätä pinon syvyyttä.

Joskus hännän rekursiivisen funktion suunnittelu edellyttää, että sinun on luotava apufunktio, jolla on lisäparametreja.

Esimerkiksi tämä ei ole ei hännän rekursiivinen toiminto:

int factorial(int x) { if (x > 0) { return x * factorial(x - 1); } return 1; } 

Mutta tämä on rekursiivinen toiminto:

int factorial(int x) { return tailfactorial(x, 1); } int tailfactorial(int x, int multiplier) { if (x > 0) { return tailfactorial(x - 1, x * multiplier); } return multiplier; } 

koska kääntäjä voisi kirjoittaa rekursiivisen funktion uudelleen ei-rekursiiviseksi käyttämällä jotain tällaista (pseudokoodi):

int tailfactorial(int x, int multiplier) { start: if (x > 0) { multiplier = x * multiplier; x--; goto start; } return multiplier; } 

Kääntäjän sääntö on hyvin yksinkertainen: Kun löydät ”return thisfunction(newparameters);”, korvaa se sanalla ”

”. Mutta tämä voidaan tehdä vain, jos rekursiivisen puhelun palauttama arvo palautetaan suoraan.

Jos funktion kaikki rekursiiviset puhelut voidaan korvata tällä tavoin, se on häntä -rekursiivinen funktio.

Vastaukseni perustuu kirjassa annettuun selitykseen Tietokoneohjelmien rakenne ja tulkinta . Suosittelen tätä kirjaa atk-tutkijoille.

Lähestymistapa A: Lineaarinen rekursiivinen prosessi

(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1))))) 

Prosessin muoto mallille Lähestymistapa A näyttää tältä:

(factorial 5) (* 5 (factorial 4)) (* 5 (* 4 (factorial 3))) (* 5 (* 4 (* 3 (factorial 2)))) (* 5 (* 4 (* 3 (* 2 (factorial 1))))) (* 5 (* 4 (* 3 (* 2 (* 1))))) (* 5 (* 4 (* 3 (* 2)))) (* 5 (* 4 (* 6))) (* 5 (* 24)) 120 

Lähestymistapa B: Lineaarinen iteratiivinen prosessi

(define (factorial n) (fact-iter 1 1 n)) (define (fact-iter product counter max-count) (if (> counter max-count) product (fact-iter (* counter product) (+ counter 1) max-count))) 

Prosessin muoto mallille Lähestymistapa B näyttää tältä:

(factorial 5) (fact-iter 1 1 5) (fact-iter 1 2 5) (fact-iter 2 3 5) (fact-iter 6 4 5) (fact-iter 24 5 5) (fact-iter 120 6 5) 120 

Lineaarinen iteratiivinen prosessi (lähestymistapa B) kulkee vakiotilassa, vaikka prosessi on rekursiivinen toimenpide. On myös huomattava, että tässä lähestymistavassa joukko muuttujia määrittelee prosessin tilan missä tahansa vaiheessa eli. {product, counter, max-count}. Tämä on myös tekniikka, jolla hännän rekursio sallii kääntäjän optimoinnin.

Lähestymistavassa A on enemmän piilotettua tietoa, jota tulkki ylläpitää ja joka on periaatteessa lykättyjen toimintojen ketju.

kommentit

• Ei pidä olla ’ t oltava vain (1) sijasta (* 1)?

Hännän rekursio on rekursiomuoto, jossa rekursiiviset puhelut ovat funktion viimeisiä ohjeita (siitä, mistä hännän osa tulee). Lisäksi rekursiivinen puhelu ei saa koostua viitteistä muistisoluihin, jotka tallentavat aikaisempia arvoja (muut viitteet kuin Tällä tavoin emme välitä edellisistä arvoista ja yksi pinokehys riittää kaikille rekursiivisille puheluille; hännän rekursio on yksi tapa optimoida rekursiiviset algoritmit. Toinen etu / optimointi on se, että on helppo tapa muuntaa hännän rekursiivinen algoritmi vastaavaksi, joka käyttää iteraatiota rekursiivisen sijasta. Joten kyllä, pikalajin algoritmi on todellakin hännän rekursiivinen.

QUICKSORT(A, p, r) if(p < r) then q = PARTITION(A, p, r) QUICKSORT(A, p, q–1) QUICKSORT(A, q+1, r) 

Tässä on iteratiivinen versio:

QUICKSORT(A) p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) r = q - 1 p = 0, r = len(A) - 1 while(p < r) q = PARTITION(A, p, r) p = q + 1