Números de Fibonacci

A sequência:     0, 1, 1, 2, 3, 5, 8, 13, 21, 34,...,

Aonde cada número é a soma dos dois valores precedentes é um exemplo de sequência facilmente calculada pela recursão, os números da sequência são denotados por F(n), e definimos formalmente como:

Esta famosa sequência foi publicada em 1202 por Leonard Pisano (Leonardo de Pisa), também conhecido como Leonardo Fibonacci (Fillius Bonaccii, filho de Bonaccii). Seu Livro do Ábaco contem o seguinte exercício: “Quantos pares de coelhos podem ser produzidos a partir de um par durante um ano?”. Para resolver este problema, pede-se para assumir que cada par gera um novo par, e cada novo par se torna fértil com um mês, alem disso, os coelhos nunca morrem. Após um mês, serão dois pares de coelhos, após dois meses serão três pares, no mês seguinte o par nascido no primeiro mês ira gerar um novo par junto do par inicial e irá ter um total de cinco, e assim prossegue.

                Considere que cada par de coelhos é simbolizado como uma vogal.

JAN

FEV

MAR

ABR

MAI

JUN

JUL

M

H

A

B

E

L

K

C

G

D

J

F

I

ORIGEM
A
B
C
D
E

Simulando o ano temos a tabela com o total de pares de coelhos de cada mês.

Mês	Pares	Total de pares
Jan	A	1
Fev	A	1
Mar	A B	2
Abr	A B C	3
Mai	A B C D E	5
Jun	A B C D E F G H	8
Jul	A B C D E F G H I J K L M	13
...

Simplificado o modelo, voltamos para uma tabela menor, sem o uso de vogais que se mostrariam insuficientes, para o numero crescente de pares.

Jan	Fev	Mar	Abr	Mai	Jun	Jul	Ago	Set	Out	Nov	Dez
1	1	2	3	5	8	13	21	34	55	89	144

                Fibonacci foi um dos grandes matematicos da idade media, ele estudou a obra de al-Khwārizmī (através do qual o termo algoritmo foi criado) e adicionou varias contribuições originais para aritmética e geometria. Antes de Fibonacci ter redigido seu trabalho, os escolares indianos já haviam discutido sobre o a sequência F(n), devido aos interesses dos mesmos por padrões rítmicos. A primeira utilidade pratica para os números de Fibonacci surgiu quando o matemático E. Léger usou a sequência para estudar a eficiência do algoritmo de Euclides, mais tarde outro matemático É. Lucas obteve resultado para provar a validade de números primos utilizando a sequência F(n) que ele chamou de “números de Fibonacci”, e desde então o termo passou a ser utilizado.

                Ao aplicar a definição de números de Fibonacci em uma rotina para C:

typedef unsigned int    uint; uint fib(uint uN) {       if (uN <= 1)             return uN;       else             return ( fib(uN - 1) + fib(uN - 2) ); }

                Observe como a definição recursiva dos números de Fibonacci difere da definição recursiva para calculo de fatorial, com a rotina recursiva fib chamando a si mesma por duas vezes, por exemplo, fib(5) = fib(4) + fib(3), de modo que ao calcular fib(5), a rotina fib será calculada duas vezes, e dentro de fib(4), requer o calculo de fib(3) e fib(2) e assim sucessivamente gerando uma quantidade grande de redundância computacional, com o caso de fib(2) sendo calculada três vezes até retornar a solução de fib(5), se ao programar uma solução, aumenta-se a eficiência ao lembrar valores já calculados anteriormente, utilizando um método iterativo:

uint ifib(uint uN) {       uint uX, uPrev, uAns, uTmp;       if (uN <= 1)             return uN;       uPrev = 0;       uAns = 1;       for ( uX = 2; uX <= uN; ++uX) {             uTmp = uAns + uPrev;             uPrev = uAns;             uAns = uTmp;       }       return uAns; }

                Diferente do que ocorre no caso da função fatorial, o mesmo numero de multiplicações ocorre para calcular n! por meio das rotinas iterativas e recursivas, ao comparar o numero de adições (não incluindo o do incremento usado pelo loop) efetuadas para calcular fib(5) da rotina iterativa com a recursiva, o método recursivo consome mais recursos que o iterativo, razão que tende a aumentar junto ao avanço da sequência.

Figura. Em uma sequência até 13 fica visível a grande diferença no desempenho entre o numero de adições realizadas pelas rotinas recursiva e iterativa.

                Como discutido anteriormente, uma versão não recursiva de um programa executara com mais eficiência em termos de tempo e espaço do que uma versão recursiva, isso acontece porque o trabalho extra dispendido para entrar e sair de um bloco é evitado, a versão não recursiva pode identificar um numero considerável de variáveis locais e temporárias que não precisam ser salvas e restauradas pelo uso da pilha, o compilador dificilmente consegue identificar tais fatores para eliminar a atividade de empilhamento desnecessária.

                Uma resposta recursiva é em vários casos uma implementação lógica e simples de uma definição apresentada, o que nos leva ao ponto em que a criação da versão não recursiva deve ser criada ao adaptar a solução recursiva simulando o funcionamento, ao invés de buscar diretamente uma resolução não recursiva do enunciado proposto.