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:
| 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 “fibonacci()” recebe um número inteiro x como parâmetro.
- 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“.
- 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. - 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.
- 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
}
}
- A função “fibonacci()” recebe um número inteiro x como parâmetro.
- 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.
- É 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.
- 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.
- Em seguida, a variável numAtual é atualizada somando antepNum e penNum. Essa soma representa o próximo termo da sequência de Fibonacci.
- O loop continua até que i alcance o valor x, momento em que todos os termos necessários terão sido calculados.
- 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.