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.

Recursividade

Recursão é o principio de que algo pode ser definido em termos de pedaços menores de si mesmo, na computação a recursividade é alcançada através do uso de funções recursivas, uma função recursiva realiza uma chamada de função para si mesma, aonde cada chamada trabalha de forma a refinar as sucessivas entradas  aproximando-o ao resultado final da solução.

Este estilo de desenvolvimento pode causar algum desconforto ao apresentar a resposta de um problema maior com uma rotina que chama a si própria, do que dividir o problema em vários pedaços e escrever as respectivas funções separadas, leva um tempo para acostumar-se a este estilo de programação.

Para começar, considere um problema simples como calcular o fatorial de um numero n, o fatorial de n, escrito n! é o produto de todos os números inteiros que precedem n até 1, por exemplo, 5! = 5 * 4 * 3 * 2 * 1, com a formula sendo:

n! = (n) (n – 1) (n – 2) ... (1)

Entretanto a expressão resultou de um processo iterativo,  aonde se subtrai um valor cada vez maior de n até alcançar 1. Buscar a resposta  de forma recursiva envolve encontrar o  padrão de recorrência, considere que os passos para n! aonde n será multiplicado pelo fatorial (n-1)!, com  n’ = n-1  resultando em  (n’)(n’-1)! e assim sucessivamente ao qual podemos definir formalmente como:

Descrevendo passo a passo o processo iterativo e recursivo temos:

ITERAÇÃO		RECURSÃO
5* (5-1)!		5* (5-1)!
5*4* (5-2)!		5*4* (4-1)!
5*4*3* (5-3)!		5*4*3* (3-1)!
5*4*3*2* (5-4)!		5*4*3*2* (2-1)!
5*4*3*2*1		5*4*3*2*1

Para ilustrar a computação de 5! usando a abordagem recursiva como descrita, visualiza-se o processo em duas partes, a primeira parte consiste em empilhar chamadas de rotinas sucessivamente até o ponto de encontrar a condição de termino, a condição de termino é o momento em que a rotina recursiva deixa de chamar a si mesma e retorna um valor, iniciando assim a segunda parte do processo ao desempilhar todas as chamadas de funções que retornam em ordem reversa, esta fase termina quando encontrar a chamada original, completando o processo recursivo.

F(5) =	5*F(4)
	F(4) =	4*F(3)
		F(3) =	3*F(2)
			F(2) =	2*F(1)
				F(1) =	1	CONDIÇÃO DE TERMINO
			F(2)=	2*1
		F(3) =	3*2
	F(4) =	4*6
F(5) =	5*24						1ª PARTE
120							2ª PARTE

Para montar a função C de fatorial, terá como entrada o numero positivo n para calcular o fatorial recursivamente, sendo a entrada menor ou igual a 1, isto é 0 e 1, retornamos 1, pois 0! e 1! são ambos definidos como 1, servindo assim como a condição de termino, do contrario a função retorna o resultado de n vezes o fatorial de n-1, como mostrado no detalhamento para o calculo de fatorial de 5.

#include <stdio.h> unsigned int fact(unsigned int n) {       if (n > 1) {             return( n * fact(n-1) );       }       else {             return 1;       } } void main(void) {       unsigned int i;       i = fact(5);       printf("5! = %u\n", i); }

Analisando a maneira que as funções são executadas em C, precisa compreender como um programa fica organizado na memória,  fundamentalmente um programa consiste em 4 áreas:

1)      Código: instruções de maquina que são executadas no programa

2)      Dados estáticos: informações que se mantém durante todo o programa, como variável global e estática.

3)      Heap: espaço para armazenamento dinâmico, como a memória reservada para rotinas como alloc.

4)      Pilha: armazena as informações das chamadas de funções. O bloco de armazenamento colocado na pilha é conhecido como registro de ativação (stack frame), composto por:

a.       Parâmetros de entrada

b.      Valor de retorno

c.       Armazenamento temporário

d.      Copia do estado (registradores)

e.      Parâmetros de saída

PROGRAMA		STACK
CODIGO		Parâmetro de entrada
DADOS ESTATICOS
		Valor de retorno
STACK		Armazenamento temporário
		Copia do estado
HEAP		Parâmetro de saída

Retornando ao exemplo de calcular 5!, a área da pilha da execução do programa em C a cada chamada fica:

n=5

n=5

n=5

n=5

n=5

n=5

n=5

n=5

n=5

?

?

?

?

?

?

?

?

120

n=4

n=4

n=4

n=4

n=4

n=4

n=4

n=4

n=4

?

?

?

?

?

?

24

n=3

n=3

n=3

n=3

n=3

n=3

n=3

?

?

?

?

6

n=2

n=2

n=2

n=2

n=2

?

?

2

n=1

n=1

n=1

1

A pilha é uma solução boa para armazenar informação paras as chamadas de função, graças ao seu comportamento ultimo a entrar, primeiro a sair (LIFO), entretanto seu uso possui fatores contra, manter informações de cada chamada executada pela rotina até seu retorno consome um espaço considerável, adicione também o tempo necessário para salvar e restaurar informações do registro de ativação (stack frame).

Tais preocupações devem ser levadas em conta, recursão é um principio elogiado nos meios acadêmicos como poderoso e elegante, o que não acontece em meios práticos, aonde elaborações profissionais tende a abominar esse tipo de resposta devido aos problemas que um código recursivo agrega.

No livro Code Complete escrito por Steve McConnel apesar de expressar que o uso seletivo da recursividade agrega benefícios, isso não o impede de afirmar que se um programador que trabalha para ele usar recursividade para calcular um fatorial, contrataria outra pessoa (forma elegante de dizer que demitiria).

Entre as opiniões reacionárias do escritor sobre o assunto, temos as seguintes regras para o bom uso da recursão:

1.       Certifique-se de que a recursividade pare.

2.       Use contadores de segurança para evitar a recursividade infinita.

3.       Restrinja a recursividade a uma única rotina (A chama B, que chama C, que chama A).

4.       Fique atento a pilha.

5.       Nunca calcule fatorial ou números de Fibonacci com recursão.

A ironia do texto deve servir como aviso para um trecho discutido anteriormente em ponteiros, código mal planejado resulta em erros catastróficos. Tanto o mau uso de ponteiros, como o uso incorreto da recursividade gera problemas difíceis de detectar, prefira sempre uma solução iterativa.

unsigned int ifact(unsigned int n) {       unsigned int i;       for (i = (n-1); i > 0; --i)             n *= i;       return n; }