O que é recursão da cauda?

A recursão de cauda é um caso especial de recursão em que a função de chamada não faz mais cálculos após fazer uma chamada recursiva. Por exemplo, a função

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

é recursiva na cauda (já que a instrução final é uma chamada recursiva), enquanto esta função não é recursiva na cauda:

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

uma vez que faz alguns cálculos após o retorno da chamada recursiva.

A recursão de cauda é importante porque pode ser implementada de forma mais eficiente do que a recursão geral. Quando fazemos uma chamada recursiva normal, temos que colocar o endereço de retorno na pilha de chamadas e pular para a função chamada. Isso significa que precisamos de uma pilha de chamadas cujo tamanho seja linear na profundidade das chamadas recursivas. Quando temos recursão de cauda, sabemos que assim que retornarmos da chamada recursiva, iremos retornar imediatamente também, então podemos pular toda a cadeia de funções recursivas que retornam e retornar diretamente ao chamador original. Isso significa que não “Não preciso de uma pilha de chamadas para todas as chamadas recursivas e pode implementar a chamada final como um salto simples, o que nos economiza espaço.

Comentários

• você escreveu ” Isso significa que não ‘ não precisamos de uma pilha de chamadas para todas as chamadas recursivas “. A pilha de chamadas sempre estará lá, só que o endereço de retorno não precisa ser escrito na pilha de chamadas, certo?
• Depende do seu modelo de computação até certo ponto 🙂 Mas sim, em um computador real, pilha de chamadas ainda está lá, nós ‘ estamos apenas não a usando.
• E se ‘ for o final call mas em for for loop. Então você faz todos os cálculos acima, mas alguns deles em um loop for como def recurse(x): if x < 0 return 1; for i in range 100{ (do calculations) recurse(x)}
• @ thed0ctor – este recursivo não ‘ t termina.

Simplesmente dito, a recursão final é uma recursão onde o compilador pode substituir a chamada recursiva com um comando “goto”, para que a versão compilada não precise aumentar a profundidade da pilha.

Às vezes, o projeto de uma função recursiva de cauda requer a criação de uma função auxiliar com parâmetros adicionais.

Por exemplo, esta não é uma função recursiva de cauda:

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

Mas esta é uma função de cauda função recursiva:

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

porque o compilador poderia reescrever a função recursiva para uma não recursiva, usando algo assim (um pseudocódigo):

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

A regra para o compilador é muito simples: quando você encontrar “return thisfunction(newparameters);“, substitua-o por “

“. Mas isso pode ser feito apenas se o valor retornado pela chamada recursiva for retornado diretamente.

Se todas as chamadas recursivas em uma função puderem ser substituídas desta forma, então é uma cauda -função recursiva.

Minha resposta é baseada na explicação dada no livro Estrutura e interpretação de programas de computador . Eu recomendo fortemente este livro para cientistas da computação.

Abordagem A: Processo Recursivo Linear

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

A forma do processo para A abordagem A se parece com isto:

(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 

Abordagem B: Processo Iterativo Linear

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

Forma do processo para Abordagem B tem esta aparência:

(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 

O Processo Iterativo Linear (Abordagem B) é executado em espaço constante, embora o processo seja um procedimento recursivo. Também deve ser notado que nesta abordagem um conjunto de variáveis define o estado do processo em qualquer ponto viz. {product, counter, max-count}. Esta também é uma técnica pela qual a recursão de cauda permite a otimização do compilador.

Na abordagem A, há mais informações ocultas que o interpretador mantém, que é basicamente a cadeia de operações adiadas.

Comentários

• Devem ‘ ser apenas (1) em vez de (* 1)?

Tail-recursão é uma forma de recursão em que as chamadas recursivas são as últimas instruções na função (é daí que vem a parte final). Além disso, a chamada recursiva não deve ser composta por referências a células de memória que armazenam valores anteriores (referências diferentes de os parâmetros da função). Desta forma, não nos importamos com os valores anteriores e um frame de pilha é suficiente para todas as chamadas recursivas; A recursão de cauda é uma forma de otimizar algoritmos recursivos. A outra vantagem / otimização é que há uma maneira fácil de transformar um algoritmo recursivo de cauda em um equivalente que usa iteração em vez de recursão. Então, sim, o algoritmo para quicksort é de fato recursivo na cauda.

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

Aqui está a versão iterativa:

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