Eliminação de recursividade

Informática

18/05/2016

Na computação, recursividade é processo ou uma rotina que invoca a si mesmo. Essa é a definição básica. Um exemplo de recursão é a genealogia de alguém: eu quero saber quem foi tataravô de meu pai, eu usaria esse processo como? Começando pelo meu pai menos 1, ou seja (pai – o meu avô), resta (pai – meu bisavô), e continuo assim até chegar aonde quero. O que vou mostra aqui e a eliminação da recursão aplicado na computação e sua atualidade.

Vamos mostrar algumas técnicas que podem ser utilizadas nos subprogramas recursivos tornando em repetitivos, e assim tornando o processamento mais eficientes.

Número de Fibonacci

Um exemplo de cálculo recursivo e complexo é o número de Fibonacci. Essa sucessão foi estudada pelo matemático Fibonacci, quando dizia acerca do crescimento de uma população de coelhos.

Veja um algoritmo de implementação recursiva dos números de Fibonacci:
 

public static long numfibonacci (int pN)

{

if (pN < 2) pN; // condição de paragem

return  numfibonacci ) return (pN -1) + numfibonacci (pN -2); //chamada recursiva

.

 }

Esse algoritmo acima é recursivo, tem pouca linha de código, mas não quer dizer que é eficiente. O que estou querendo dizer que tem situações que a forma recursiva gasta mais processamento para achar o mesmo resultado. Exemplo o cálculo do Fibonacci 5 custa 7 adições e o Fibonacci de 4, dá um total de 12 adições. O Fibonacci de 7 custa 20 adições e o de 8 33 adições. O número de adições duplica. Pensando nisso, antes de usar o método recursivo devemos analisar qual os meios consomem menos processamento e deixa também o código mais dinâmico. Temos três formas básica de analisar isso: o primeiro é a forma recursiva como já vimos, o outro é a programação dinâmica e, por fim, a forma repetitiva. Veja o algoritmo abaixo:

public static long Repetitiva (int pN)

{

long antes = 0, previw = 1, passado = 0;

If(pN < 2) return (long) pN;

for (int i = 2; i<= pN; i++)

{

passado = previw + antes;

antes = previw = passado;

}

return passado;

}

Conclusão

Aqui, eu mostrei explicitamente como usar a eliminação de recursividade usando a memória pilha, aplicando a forma repetitiva. Quando devo usar o método recursivo ou repetitivo? De forma prática, analisando o tempo que ambos levam no processamento para fazer a mesma coisa.