Tail Recursion

Este é a continuação do artigo sobre recursão.

Neste post vamos entender o conceito de Tail Recursion, que também pode ser chamado de Recursão em Cauda, nada mas é do que uma técnica para otimizar os algoritmos recursivos. Conforme vimos no artigo anterior, a medida que a recursão cresce, o consumo de memoria Stack(Pilha) também cresce, levando um gasto excessivo para resolver o problema principal. Para evitarmos este consumo, que afeta o desempenho do algoritmo, é necessário usar o conceito de Tail Recursion.
Algoritmos Tail Recursion tem um desempenho próximo a de uma interação do tipo ‘for’, portando de comportamento assintótico de O(n).

Para usufruirmos do desempenho aqui citado, o algoritmo não deve realizar operações que dependam do resultado de métodos recursivo. Mas a frente veremos o porquê.

O compilador

A maneira como um compilador ou uma linguagem são arquitetados podem interferir na implementação do Tail Recursion, em geral linguagem funcionais não tem problemas para implementar este tipo de conceito.
O compilador precisa armazenar os endereços, assim como o estado das execuções dos métodos que precisam esperar um resultado de outro método. Essa rotina consome muito recurso, levando a um baixo desempenho para os algoritmos recursivos. Apesar disso, é possível diminuir este consumo.
O conceito de Tail Recursion envolve o compilador e também o Programador, este ultimo deve permitir que o algoritmo possa ser otimizado. Como ? veremos a seguir.

A chamada recursiva deve ser a última instrução a ser executada. O programador deve ter certeza que sua solução atenda esta frase para implementar um algoritmo Tail Recursion, o resto fica com o compilador.
O compilador deve reconhecer que salvar os endereçamentos e ou instruções serão um desperdício para os algoritmos Tail Recursion.
Se não houver instruções adicionais para executar, ou seja Tail Recursion, então não há necessidade de armazenar o ponteiro de instrução na pilha.

---

Algorítimos – Recursão x Recursão em Cauda x Interação

Os algoritmos a seguir implementam o algoritmo de Fibonacci em Java utilizando Recursão tradicional, Recursão em cauda e Interação. Tais algoritmos foram usados em um pequeno benchmark.

public interface Fibonacci {
	public long calcula(long n);
}

1ª Algoritmo – Uso de interação:

public class AlgoritmoFibonnacciInterativo implements Fibonacci {

	public long calcula(long n){

		long anterior = -1;
		long resultado = 1;

		for(long i=0; i <= n; ++i){
			long soma = resultado + anterior;
			anterior = resultado ;
			resultado = soma;
		}
		return resultado;
	}
}

2ª Algoritmo – Uso de Recursão tradicional:

public class AlgoritmoFibonnacciRecursivo implements Fibonacci{

	public long calcula(long n){
		if(n==0||n==1){
			return n;
		}else{
			return calcula(n-1)+calcula(n-2);
		}
	}

}

3ª Algoritmo – Uso de Recursão em Cauda:

public class AlgoritmoFibonnacciTailRecursion implements Fibonacci{


	public long calcula(long n){
		return fibonnacci(n, 0, 1);
	}
	
	private long fibonnacci(long n, long primeiro, long segundo){
		if( n == 0 ){ 
			return primeiro;
		}
		return fibonnacci(n-1, segundo, primeiro+segundo);
                //Tailrecursion porque a chamada recursiva é a ultima instrução a ser executada.
	}

}

Benchmark

Nos testes apenas foram contabilizados o tempo dos métodos calcula(), desconsiderando o tempo de inicialização das classes e construtores. Cada teste foi realizado individualmente em um Intel Core 2 Duo CPU, E7500 2.93Chz, 4G 64Bits – Windows 7 Ultimate

O teste foi realizado na IDE Eclipse com o complemento ‘Eclipse Test & Performance Tools Platform Project’ (TPTP)

N	Resultado	Interativo (Segundos)	Recursivo (Segundos)	Tail Recursion (Segundos)
10	55	0,000005	0,001312	0,000103
20	6765	0,000005	0,483866	0,000171
25	75025	0,000006	5,037891	0,000211
30	832040	0,000005		0,000301
40	102334155	0,000005		0,000314
100	3736710778780430000	0,000007		0,000715
1000	817770325994397000	0,000026		0,007581

---

Referencias

http://blogs.msdn.com/b/chrsmith/archive/2008/08/07/understanding-tail-recursion.aspx

http://c2.com/cgi/wiki?TailRecursion

http://algol.dcc.ufla.br/~bruno/aulas/lp2/recursao.html

http://www.eclipse.org/tptp/

Estrutura de Dados e Algoritmos: Padrões de Projetos Orientados a Objetos Com Java – Livro

Algoritmos, Java

bechmark, Fibonacci, Recursão, Recursão em Cauda, Recursividade, Tail Recursion

fevereiro 10, 2013

2 Comentários