Sequ�ncia de Fibonacci em Java

A Sequ�ncia de Fibonacci tem como primeiros termos os n�meros 0 e 1 e, a seguir, cada termo subsequente � obtido pela soma dos dois termos predecessores:


0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...

Nenhuma outra sequ�ncia de n�meros foi t�o estudada e possui aplicaç�es em �reas t�o distintas, como por exemplo Biologia, Arquitetura, Arte e outras. A raz�o entre dois n�meros consecutivos da sequ�ncia converge para um valor constante de 1,618... conhecido como n�mero de ouro, n�mero �ureo ou proporç�o �urea (golden ratio). Este n�mero � muito "apreciado" por artistas e cientistas porque est� presente em diversos fen�menos da natureza.

Os n�meros da sequ�ncia de Fibonacci podem ser gerados por uma regra (recorr�ncia) simples:


Fibonacci(0) = 0
Fibonacci(1) = 1
Fibonacci(n) = Fibonacci(n-1) + Fibonacci(n-2)

A seguir s�o apresentadas quatro diferentes formas para implementar a sequ�ncia de Fibonacci na linguagem Java. Todas as implementaç�es criam uma classe denominada Fibonacci e um m�todo fibo(n) do tipo long. Este m�todo � o respons�vel por computar e retornar o en�simo termo da s�rie.

Implementaç�o 1 - Recursiva Tradicional

Consiste na traduç�o direta da recorr�ncia para um algoritmo recursivo.


public class Fibonacci {
 
    static long fibo(int n) {
        if (n < 2) {
            return n;
        } else {
            return fibo(n - 1) + fibo(n - 2);
        }
    }
 
    public static void main(String[] args) {   
	
	// teste do programa. Imprime os 30 primeiros termos       
	for (int i = 0; i < 30; i++) {
            System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");
        }
 
    }
 
}

Implementaç�o 2 - Recursiva Utilizando o Operador Tern�rio

Com o uso do operador tern�rio do Java � poss�vel construir uma implementaç�o bem mais compacta do m�todo recursivo.


public class Fibonacci {
 
    static long fibo(int n) {
        return (n < 2) ? n : fibo(n - 1) + fibo(n - 2);
    }
 
 
    public static void main(String[] args) {
	
	 // teste do programa. Imprime os 30 primeiros termos
        for (int i = 0; i < 30; i++) {
            System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");
        }
 
    }
 
}

Implementaç�o 3 - Interativa

Embora as duas implementaç�es recursivas apresentadas sejam muito elegantes, as mesmas apresentam o problema de apresentar desempenho muito lento, pois as diversas chamadas recursivas fazem com que os mesmos valores sejam recalculados diversas vezes. Tente, por exemplo, rodar os programas recursivos para calcular fibo(50) e veja que o programa levar� um longo tempo para apresentar a resposta. A seguir apresenta-se uma soluç�o iterativa que computa o en�simo termo de uma maneira bem mais r�pida.


public class Fibonacci {
 
    static long fibo(int n) {
        int F = 0;     // atual
        int ant = 0;   // anterior
 
        for (int i = 1; i <= n; i++) {
 
            if (i == 1) {
                F = 1;
                ant = 0;
            } else {
                F += ant;
                ant = F - ant;
            }
 
        }
 
        return F;
    }
 
    public static void main(String[] args) {
 
	// teste do programa. Imprime os 30 primeiros termos
        for (int i = 0; i < 30; i++) {
            System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");
        }
 
    }
 
}

Implementaç�o 4 - Recursiva com Vetor

Por fim, � apresentada uma implementaç�o recursiva que consegue o mesmo desempenho da iterativa. O "truque" consiste em utilizar um vetor que armazena termos j� calculados (ou seja, nesta soluç�o recursiva nenhum termo � recalculado). Veja que a soluç�o ficou mais complicada - foi necess�rio criar mais m�todos e vari�veis auxiliares.


public class Fibonacci {    

    private static int[] vetAux = new int[50];
    private static int k;

    public static long fibo(int n) {      
             k = 1; // inicializa k
             return recursao(n);
           }

    private static long recursao(int n) {
            if (n < 0) { 
               return vetAux[0];  
          } else { 
           if (k < 3) {
              vetAux[n] = k - 1; 
              k++; 
           } else {
                 vetAux[n] = vetAux[n + 1] + vetAux[n + 2]; 
                 }
              return recursao(n - 1);
           }
    }
    
    public static void main(String[] args) {  // teste do programa. Imprime os 30 primeiros termos
    for (int i = 0; i < 30; i++) {
        System.out.print("(" + i + "):" + Fibonacci.fibo(i) + "\t");
        }
    }
}

Sequ�ncia de Fibonacci em Java

Este artigo apresenta quatro diferentes maneiras para implementar a sequência de Fibonacci em Java

Implementaç�o 1 - Recursiva Tradicional

Implementaç�o 2 - Recursiva Utilizando o Operador Tern�rio

Implementaç�o 3 - Interativa

Implementaç�o 4 - Recursiva com Vetor

Artigos relacionados