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