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 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

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:

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

}

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.

Algoritmo de Fibonacci Iterativo

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
}

}

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.

Comparação entre fibonacci iterativo e recursivo