A Sequência de Fibonacci: algoritmos em Java e C

Introdução

Para quem desconhece a Sequência de Fibonacci é uma sequência de números naturais onde um número é igual à soma de seus dois anteriores. Tal sequência pode iniciar por 0 (zero) e 1 (um) ou por 1 (um) e 1 (um). A sequência será a mesma o que mudará será o valor inicial. A partir desses valores iniciais, podemos calcular os números posteriores.

Os números que fazem parte da sequência de Fibonacci também são denominados Números de Fibonacci.

A sequência de Fibonacci possui diversas aplicações práticas. É usada, por exemplo, para obter o valor aproximado do número de ouro (Phi, φ). Também encontramos essa sequência na natureza: árvore genealógica das abelhas, número de axilas do talo de uma planta à medida que cresce e etc.

Entretanto o objetivo dessa postagem é apresentar os algoritmos recursivos e iterativos em Java e C que calculam qualquer valor da sequência dado um índice 'n'. É importante ressaltar que pela regra dessa sequência, para achar o valor do índice 'n', precisamos somar os valores de 'n - 1' e 'n - 2', resumindo, precisamos dos dois valores imediatamente anteriores.

Algoritmos

Os algoritmos apresentados calculam a sequência de Fibonacci iniciando pelo 0 (zero).

Algoritmo Recursivo em C:

#include <math.h>
#include <stdio.h>
 
long fibonacci(int n){
    if(n == 0){
        return 0;
    }else if(n == 1){
        return 1;
    }else{
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}
int main(){
    printf("%d", fibonacci(12));
    getch();
    return 0;
}

Algoritmo Iterativo em C:

#include <math.h>
#include <stdio.h>
 
long fibonacci(int n){
    int i = 0;
    int j = 1;
    int k;
    for(k = 1; k < n; k++){
        int t = i + j;
        i = j;
        j = t;
    }
    return j;
}
int main(){
    printf("%d", fibonacci(10));
    getch();
    return 0;
}

Algoritmo Recursivo em Java:

public class FibonacciRecursivo {
    public static long fibonacci(int n){
        if(n == 0){
            return 0;
        }else if(n == 1){
            return 1;
        }else{
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }
    public static void main(String[] args){
        System.out.printf("%d", fibonacci(10));
    }
}

Algoritmo Iterativo em Java:

public class FibonacciIterativo {
    public static long fibonacci(int n){
        int i = 1;
        int j = 0;
        int t;
        for(int k = 1; k <= n; k++){
            t = i + j;
            i = j;
            j = t;
        }
        return j;
    }
    public static void main(String[] args) {
        System.out.printf("%d", fibonacci(10));
    }
}

Download dos Códigos

Clique no link correspondente para realizar o download do código desejado:

• Algoritmo Recursivo em C
• Algoritmo Iterativo em C
• Algoritmo Recursivo em Java
• Algoritmo Iterativo em Java

Referências

• [1] Sequência de Fibonacci (Wikipédia)
• [2] HUNTLEY, H. E. A divina proporção: um ensaio sobre beleza na matemática. Brasília, EdUnB, 1985. p. 156-9.