Hvad er hale rekursion?

Tail-rekursion er et specielt tilfælde af rekursion, hvor opkaldsfunktionen ikke foretager mere beregning efter et rekursivt opkald. For eksempel er funktionen

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

hale-rekursiv (da den sidste instruktion er et rekursivt opkald), mens denne funktion ikke er hale-rekursiv:

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

da det foretager nogen beregning efter at det rekursive opkald er vendt tilbage.

Tail-rekursion er vigtigt, fordi det kan implementeres mere effektivt end generel rekursion. Når vi foretager et normalt rekursivt opkald, er vi nødt til at skubbe returadressen på opkaldsstakken og derefter springe til den kaldte funktion. Dette betyder, at vi har brug for en opkaldsstak, hvis størrelse er lineær i dybden af de rekursive opkald. Når vi har hale-rekursion, ved vi, at så snart vi vender tilbage fra det rekursive opkald, vil vi straks også vende tilbage, så vi kan springe hele kæden af rekursive funktioner tilbage og vende tilbage direkte til den oprindelige opkalder. Det betyder, at vi ikke “behøver overhovedet ikke en opkaldsstak til alle de rekursive opkald og kan implementere det sidste opkald som et simpelt spring, hvilket sparer os plads.

Kommentarer

• du skrev ” Det betyder, at vi slet ikke ‘ har brug for en opkaldsstak til alle de rekursive opkald “. Call stack vil altid være der, bare at returadressen ikke behøver at blive skrevet i call stack, ikke?
• Det afhænger af din beregningsmodel til en vis grad 🙂 Men ja, på en rigtig computer er opkaldsstak er der stadig, vi ‘ bruger den bare ikke.
• Hvad hvis den ‘ er den sidste ring men ind for for loop. Så du laver alle dine beregninger ovenfor, men nogle af 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 gør ikke ‘ t afsluttes.

Simpelthen sagt, halerekursion er en rekursion, hvor kompilatoren kunne erstatte det rekursive opkald med kommandoen “goto”, så den kompilerede version ikke behøver at øge stakdybden.

Nogle gange kræver design af en tail-rekursiv funktion, at du skal oprette en hjælperfunktion med yderligere parametre. / p>

For eksempel er dette ikke en hale-rekursiv funktion:

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

Men dette er en hale- rekursiv funktion:

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 compileren kunne omskrive den rekursive funktion til en ikke-rekursiv funktion ved hjælp af noget som dette (en pseudokode):

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

Reglen for compileren er meget enkel: Når du finder “return thisfunction(newparameters);“, skal du erstatte den med “

“. Men dette kan kun gøres, hvis den værdi, der returneres af det rekursive opkald, returneres direkte.

Hvis alle rekursive opkald i en funktion kan udskiftes på denne måde, er det en hale -rekursiv funktion.

Mit svar er baseret på forklaringen i bogen Struktur og fortolkning af computerprogrammer . Jeg kan varmt anbefale denne bog til dataloger.

Tilgang A: Lineær rekursiv proces

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

Processens form for Fremgangsmåde A ser sådan ud:

(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 

Fremgangsmåde B: Lineær iterativ proces

(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 af processen til Tilgang B ser sådan ud:

(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 proces (tilgang B) kører i konstant rum, selvom processen er en rekursiv procedure. Det skal også bemærkes, at i denne tilgang definerer et sæt variabler status for processen på et hvilket som helst tidspunkt, dvs. {product, counter, max-count}. Dette er også en teknik, hvormed halerekursion muliggør kompilatoroptimering.

I tilgang A er der mere skjult information, som tolken opretholder, som grundlæggende er kæden af udsatte operationer.

Kommentarer

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

Tail-rekursion er en form for rekursion, hvor rekursive opkald er de sidste instruktioner i funktionen (det er, hvor haledelen kommer fra). Desuden må det rekursive opkald ikke være sammensat med henvisninger til hukommelsesceller, der lagrer tidligere værdier funktionerne). På denne måde er vi ligeglade med tidligere værdier, og en stabelramme er tilstrækkelig til alle de rekursive opkald; tail-rekursion er en måde at optimere rekursive algoritmer på. Den anden fordel / optimering er, at der er en nem måde at omdanne en hale-rekursiv algoritme til en ækvivalent, der bruger iteration i stedet for rekursion. 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 version:

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