Algoritmo para Fibonacci Recursivo e Iterativo – Lógica de Programação

Algoritmo para Fibonacci Recursivo e Iterativo

A série de Fibonacci é uma sequência numérica infinita em que cada número subsequente é a soma dos dois números anteriores. A sequência começa com os números 0 e 1, e a partir deles, cada número seguinte é calculado somando os dois números anteriores.

Portanto, a sequência começa da seguinte forma:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, e assim por diante.

A sequência começa em 0 e 1, porém alguns autores dizem que a sequência começa em 1 e 1, e o próprio Fibonacci iniciava a sequência em 1 e 2.

O algoritmo para gerar a sequência permanece o mesmo para todos os casos, com ajustes mínimos no valor inicial.

Por conta desse padrão numérico interessante, a série de Fibonacci é amplamente estudada e aplicada em vários campos, como matemática, ciência da computação, biologia, arte e finanças.

Além disso, a proporção entre os números adjacentes na sequência de Fibonacci, chamada de “razão áurea”, “proporção áurea” ou “número de ouro”, que é aproximadamente 1,618, é considerada esteticamente agradável e é encontrada em muitas formas naturais, como conchas, flores e galáxias (descrevendo uma forma em espiral), além de ser utilizada em projetos de arquitetura e design.

Espiral de Fibonacci

Espiral que representa a sequência de Fibonacci

Neste tutorial vou mostrar como criar algoritmos para lógica de programação com Portugol que permitem gerar a sequência de Fibonacci, tanto de forma recursiva quanto iterativa.

De onde vem o nome “Fibonacci”?

Fibonacci, cujo nome verdadeiro era Leonardo de Pisa, foi um matemático italiano do século XIII. Ele é mais conhecido por introduzir a sequência numérica que leva seu nome, a sequência de Fibonacci, em seu livro “Liber Abaci” (Livro do Ábaco), publicado em 1202. Fibonacci significa filius Bonacci, ou filho de Bonaccio

Fibonacci viajou extensivamente pelo Mediterrâneo e estudou os sistemas numéricos usados na época, incluindo o sistema de numeração hindu-arábico. Ele ficou fascinado pelas propriedades matemáticas desses sistemas e, em seu livro, introduziu essa sequência numérica como um exemplo de progressão aritmética encontrada em um problema envolvendo a reprodução de coelhos.

Leonardo de Pisa, o Fibonacci

Leonardo de Pisa, o Fibonacci

Embora não tenha sido o descobridor da sequência em si, Fibonacci popularizou a sequência e demonstrou suas propriedades matemáticas e aplicações em várias áreas. Seu trabalho teve um impacto duradouro na matemática e continua sendo estudado e aplicado até hoje.

Curiosidade: O nome “sequência de Fibonacci” foi empregado pela primeira vez pelo matemático francês François Édouard Anatole Lucas, no século XIX (o mesmo matemático que inventou a Torre de Hanói).

Algoritmo de Fibonacci Recursivo

Podemos definir a série de fibonacci recursivamente da seguinte forma:

Casos base:
fibonacci(0) = 0
fibonacci(1) = 1

Caso geral:
fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)

Uma sequência de operações semelhantes. Perfeito para a recursão!

Exemplo: Qual o terceiro valor de Fibonacci da sequência?

fib(3) = ?
fib(3) = fib(3-1) + fib(3-2)
fib(3) = fib(2) + fib(1)
fib(3) = fib(2-1) + fib(2-2) + 1
fib(3) = fib(1) + fib(0) + 1
fib(3) = 1 + 0 + 1
fib(3) = 2

Isso significa que o terceiro fibonacci (assumindo que o primeiro é o zerésimo valor) é o número 2:

F0 F1 F2 F3
0 1 1 2

Vamos criar um algoritmo usando o Portugol Studio para obter a sequência de fibonacci com a quantidade de elementos determinados pelo usuário:

programa
{

inteiro num

funcao inicio()
{

  escreva("Obter sequência de Fibonacci\n")
  escreva("Entre com um número: ")
  leia(num)
  escreva(num + "º fibonacci: " + fibonacci(num) + "\n") 

  escreva("\nMostrar a sequência completa:\n")
  para (inteiro i = 0; i < num; i++) {
    escreva(fibonacci(i) + " ")
  }

}

// Função fibonacci recursivo
funcao inteiro fibonacci(inteiro x) {
  se ((x == 0) ou (x == 1)) {
      retorne x
  }
  retorne fibonacci(x-1) + fibonacci(x-2)
}

}
A função é definida como uma função recursiva, o que significa que ela se chama a si mesma repetidamente para calcular o valor desejado. Vejamos o funcionamento dessa função passo a passo:
 
  1. A função “fibonacci()” recebe um número inteiro x como parâmetro.
  2. Primeiro, ela verifica se x é igual a 0 ou 1 usando a condição ((x == 0) ou (x == 1)). Esses são os casos base da sequência de Fibonacci, em que o valor é conhecido e não precisa ser calculado. Se x for igual a 0 ou 1, a função retorna o próprio valor de x, utilizando a instrução “retorne x“.
  3. Se o valor de x não for 0 ou 1, a função chama a si mesma para calcular os termos anteriores necessários para calcular o valor atual. Ela retorna a soma dos resultados de duas chamadas recursivas: fibonacci(x-1) e fibonacci(x-2).
    fibonacci(x-1) calcula o valor do termo anterior ao termo x.
    fibonacci(x-2) calcula o valor do termo dois lugares antes do termo x.
    A soma desses dois valores representa o valor do termo x na sequência de Fibonacci.
  4. A função continua a se chamar recursivamente até que atinja um dos casos base (x = 0 ou x = 1), momento em que retorna o valor correspondente.
  5. A função retorna o valor do termo de Fibonacci correspondente ao número x fornecido.
Essa implementação algorítmica da função Fibonacci é simples, mas pode se tornar ineficiente para valores de x grandes, devido à natureza recursiva da função. Isso ocorre porque a função realizará várias chamadas repetidas para calcular os mesmos termos novamente. Nesses casos, pode ser mais eficiente usar uma abordagem iterativa, que é o que faremos a seguir.
 

Algoritmo de Fibonacci Iterativo

Outra opção para gerar uma sequência de fibonacci é empregar um algoritmo iterativo em vez de recursivo. Neste caso, em vez de a função realizar chamadas a si própria repetidas vezes (recursividade), usamos um laço de repetição comum para realizar o cálculo dos valores a serem gerados.
 
Vamos ao algoritmo:
programa
{

inteiro num

funcao inicio()
{

  escreva("Obter sequencia de Fibonacci\n")
  escreva("Entre com um número: ")
  leia(num)
  
  escreva("\nMostrar a sequência completa:\n")
  para (inteiro i = 1; i <= num; i++) {
    escreva(fibonacci(i) + " ")
  }

}

// Função fibonacci iterativo
funcao inteiro fibonacci(inteiro x) {
  inteiro antepNum, penNum = 0, numAtual = 1

  se ((x == 0) ou (x == 1)) {
       retorne x
  }
  para (inteiro i = 2; i <= x; i++) {
    antepNum = penNum
    penNum = numAtual
    numAtual = antepNum + penNum
  }
  retorne numAtual
}

}
Diferente da abordagem anterior, que era recursiva, este algoritmo utiliza uma abordagem iterativa. Vamos analisar o funcionamento dessa função passo a passo:
 
  1. A função “fibonacci()” recebe um número inteiro x como parâmetro.
  2. Em seguida, três variáveis inteiras são declaradas: antepNum, penNum e numAtual. Inicialmente, antepNum e penNum são definidos como 0, e numAtual é definido como 1. Essas variáveis são usadas para acompanhar os valores dos termos anteriores e atual da sequência de Fibonacci.
  3. É iniciado um loop “para” com uma variável de controle inteira i, que começa em 2 e vai até x. Esse loop irá iterar x-2 vezes, pois os primeiros termos já são conhecidos.
  4. Dentro do loop, os valores antigos são atualizados para avançar na sequência de Fibonacci. A variável antepNum recebe o valor de penNum, que é o termo anterior, e penNum recebe o valor de numAtual, que é o termo atual.
  5. Em seguida, a variável numAtual é atualizada somando antepNum e penNum. Essa soma representa o próximo termo da sequência de Fibonacci.
  6. O loop continua até que i alcance o valor x, momento em que todos os termos necessários terão sido calculados.
  7. Após o término do loop, a função retorna o valor de numAtual, que é o termo de Fibonacci correspondente ao número x fornecido.
Note que a função que gera a sequência de fibonacci se tornou um pouco mais complexa, porém provavelmente mais fácil de entender. A seguir vamos comparar a performance de ambas as funções.
 

Comparação entre fibonacci iterativo e recursivo

Às vezes, o código de aparência mais limpa não é o melhor. Em termos de notação Big O, a solução iterativa será executada mais rapidamente com uma notação de O(n), enquanto a solução recursiva é O(2^n), e isso se torna facilmente perceptível ao tentar gerar sequências de fibonacci maiores.
 
Se executarmos os dois algoritmos passando um valor como 40 para gerar sequência, poderemos claramente perceber a diferença. O resultado é a abordagem iterativa executando muito mais rápido do que a recursiva.
 
A abordagem iterativa do algoritmo Fibonacci é mais eficiente do que a abordagem recursiva, especialmente para valores de x maiores. A função itera apenas uma vez, atualizando os valores necessários em cada iteração, em vez de realizar chamadas recursivas repetidas. Isso torna o algoritmo mais rápido e eficiente em termos de uso de memória.
 
Portanto, cuidado ao empregar algoritmos recursivos – nem sempre são a maneira mais adequada de resolver problemas em computação.
 
Sobre Fábio dos Reis (1214 Artigos)
Fábio dos Reis trabalha com tecnologias variadas há mais de 30 anos, tendo atuado nos campos de Eletrônica, Telecomunicações, Programação de Computadores e Redes de Dados. É um entusiasta de Ciência e Tecnologia em geral, adora Viagens e Música, e estuda idiomas, além de ministrar cursos e palestras sobre diversas tecnologias em São Paulo e outras cidades do Brasil.

Escreva um comentário

Seu e-mail não será divulgado


*