Recursão em Cauda

by Paco Pomet / from beautifuldecay.com

A recursão de cauda é um tipo especial de recursão, no qual não existe processamento a ser feito depois de encerrada a chamada recursiva. Sendo assim, não é necessário guardar o estado do processamento no momento da chamada recursiva. Um compilador ou interpretador pode (se for construído assim) detectar a ocorrência de recursão de cauda e gerar código em que a chamada recursiva é implementada como um mero desvio do fluxo de instruções.

Desta forma é possível executar código recursivo de forma tão eficiente quanto é possível executar código iterativo. Cabe ao programador encontrar uma forma de descrever a solução de seu problema através de recursão de cauda. Por outro lado, usar recursão de cauda geralmente envolve trabalhar num nível mais baixo de abstração o que prejudica a legibilidade e a manutenção do código.  — Extraído de http://algol.dcc.ufla.br/~bruno/aulas/lp2/recursao.html

Em outras palavras, recursão em cauda é uma recursão onde não há nenhuma linha de código após a chamada do próprio método e, sendo assim, não há nenhum tipo de processamento a ser feito após a chamada recursiva. Comandos após a chamada recursiva são evitados porque alguns compiladores são capazes de identificar isso e não armazenam os estados (variáveis locais e parâmetros não precisam ser salvos na pilha da recursão) para em ser possível retornar e concluir o que estava após a chamada recursiva, já que não há nada após a chamada. A eficiência dessa técnica torna o algoritmo recursivo tão eficiente quanto uma iteração. Segue abaixo um teste de performance com iteração, recursão e recursão em cauda, fazendo uso de arrays com 10, 20, 25, 30, 40, 100 e 1000 elementos.

Capturar

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair /  Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair /  Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair /  Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair /  Alterar )

w

Conectando a %s