Hva er hale rekursjon?

Tail-rekursjon er et spesielt tilfelle av rekursjon der anropsfunksjonen ikke gjør mer beregning etter å ha foretatt et rekursivt anrop. For eksempel er funksjonen

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

hale rekursiv (siden den siste instruksjonen er en rekursiv samtale) mens denne funksjonen ikke er hale rekursiv:

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

siden det gjør noe beregning etter at den rekursive samtalen har kommet tilbake.

Tail-rekursjon er viktig fordi den kan implementeres mer effektivt enn generell rekursjon. Når vi foretar et normalt rekursivt anrop, må vi skyve returadressen på samtalestakken og deretter hoppe til den ringte funksjonen. Dette betyr at vi trenger en samtalestabel hvis størrelse er lineær i dybden av de rekursive samtalene. Når vi har halerekursjon, vet vi at så snart vi kommer tilbake fra det rekursive anropet, kommer vi også umiddelbart tilbake, så vi kan hoppe over hele kjeden av rekursive funksjoner som kommer tilbake og tilbake direkte til den opprinnelige innringeren. «trenger ikke en samtalestak i det hele tatt for alle rekursive samtaler, og kan implementere den endelige samtalen som et enkelt hopp, noe som sparer oss plass.

Kommentarer

• du skrev » Det betyr at vi ikke trenger ‘ ikke trenger en samtalestabel i det hele tatt for alle de rekursive samtalene «. Samtalsstak vil alltid være der, bare at returadressen ikke trenger å skrives inn i samtalestakken, ikke sant?
• Det avhenger av beregningsmodellen din til en viss grad 🙂 Men ja, på en ekte datamaskin er samtalestakelen er der fremdeles, vi ‘ bruker bare ikke den.
• Hva om den ‘ er finalen ring men inn for for loop. Så du gjør alle beregningene dine ovenfor, men noen av dem i en for loop som def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – denne rekursive gjør ikke ‘ t avsluttes.

Enkelt sagt, tail recursion er en rekursjon der kompilatoren kan erstatte det rekursive anropet med en «goto» -kommando, slik at den kompilerte versjonen ikke trenger å øke bunndybden.

Noen ganger krever det å lage en hjelperfunksjon med flere parametere for å designe en hale-rekursiv funksjon. / p>

Dette er for eksempel ikke en hale-rekursiv funksjon:

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

Men dette er en hale- rekursiv funksjon:

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

fordi kompilatoren kunne omskrive den rekursive funksjonen til en ikke-rekursiv, ved å bruke noe som dette (en pseudokode):

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

Regelen for kompilatoren er veldig enkel: Når du finner «return thisfunction(newparameters);«, erstatt den med «

«. Men dette kan bare gjøres hvis verdien som returneres av den rekursive samtalen returneres direkte.

Hvis alle rekursive samtaler i en funksjon kan erstattes slik, er det en hale -rekursiv funksjon.

Mitt svar er basert på forklaringen i boka Struktur og tolkning av dataprogrammer . Jeg anbefaler denne boka på det sterkeste til informatikere.

Tilnærming A: Lineær rekursiv prosess

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

Formen på prosessen for Tilnærming A ser slik ut:

(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 

Tilnærming B: Lineær Iterativ prosess

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

Form av prosessen for Tilnærming B ser slik ut:

(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 

Den lineære iterative prosessen (tilnærming B) kjører i konstant rom selv om prosessen er en rekursiv prosedyre. Det skal også bemerkes at i denne tilnærmingen definerer et sett variabler prosessens tilstand til enhver tid, nemlig. {product, counter, max-count}. Dette er også en teknikk der halerekursjon tillater kompilatoroptimalisering.

I tilnærming A er det mer skjult informasjon som tolken opprettholder, som i utgangspunktet er kjeden av utsatt operasjon.

Kommentarer

• Skal ‘ t være bare (1) i stedet for (* 1)?

Tail-rekursion er en form for rekursjon der rekursive samtaler er de siste instruksjonene i funksjonen (det er der haledelen kommer fra). Dessuten må det rekursive anropet ikke bestå av referanser til minneceller som lagrer tidligere verdier (referanser parametrene til funksjonen). På denne måten bryr vi oss ikke om tidligere verdier, og en stabelramme er tilstrekkelig for alle rekursive samtaler; tail-rekursion er en måte å optimalisere rekursive algoritmer på. Den andre fordelen / optimaliseringen er at det er en enkel måte å transformere en hale-rekursiv algoritme til en ekvivalent som bruker iterasjon i stedet for rekursjon. Så ja, algoritmen for quicksort er faktisk hale-rekursiv.

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

Her er den iterative versjonen:

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