Fibonacci

Olá!

Hoje, mais um post sobre recursão, abordando a sequência de Fibonacci.
Se você perdeu o meu post sobre recursão, você pode acessá-lo aqui. E também há um sobre a função recursiva que faz a potência de números inteiros, que você pode ver por aqui.

A sequência de Fibonacci é uma sequência matemática definida da seguinte forma:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...

Como podemos observar, a sequência tem uma característica: Ela começa com 0, 1 e os próximos números são definidos pela soma dos dois anteriores.
Você observa pelas contas:

Dois primeiros: 0, 1
0 + 1 = 1
1 + 1 = 2
2 + 1 = 3
3 + 2 = 5
5 + 3 = 8
8 + 5 = 13
13 + 8 = 21
...

Tendo isso em mente, podemos definir a seguinte relação matemática:

F(n) =
   | 0, se n = 0
   | 1, se n = 1
   | F(n - 1) + F(n - 2), em outros casos

Utilizando essa definição, facilmente podemos construir uma função recursiva que calcule a sequência de fibonacci, certo?
Pensando em um caso base para nossa recursão, o que temos? Sabemos que quando n = 0 ou n = 1, não precisamos retornar nossa função de novo, e a resposta é o próprio n.

Agora, vamos definir o passo da recursão. Caso n não seja 0 ou 1, qual o valor da resposta? É a soma dos dois anteriores à n, certo? Ou seja:

Pronto! Construimos nosso algoritmo que calcula o número de fibonacci:

E para visualizar a sequência de Fibonacci como demonstrada no começo? Como fazer? Calma, pequeno padawan. Vamos utilizar um laço de repetição para poder calcular os números de fibonacci e imprimi-los na tela.

Agora, pra brincar, é preciso apenas chamar a função fibonacci com o número de elementos da sequência desejado!
fibonacci(5) Irá nos retornar a seguinte sequência:

0, 1, 1, 2, 3

Nessa hora muitas pessoas não compreendem o que exatamente está acontecendo pra que a sequência esteja certa. De onde estão vindo os números?
Tentei ilustrar como ocorrem as chamadas recursivas:

Veja, para cada iteração do laço for, um número fibonacci é calculado, e a função fibo realiza a recursão para este cálculo. Perceba que todas chegam até f(0) ou f(1), e vão retornando seus valores. Como em fibo(2), que precisa da resposta de f(1) + f(0), trazendo a soma 1 + 0, fazendo com que fibo(2) retorne 1.

Esse é um clássico da recursão. Sua solução recursiva é muito elegante, mas como se verifica na imagem, nem tanto eficiente. A solução iterativa é bem menos elegante, mas muito mais eficiente.

Postarei a solução iterativa em breve!
Até a próxima!

As matrizes

Já vimos o conceito de vetores, anteriormente. Veremos agora o que chamamos de vetores bi-dimensionais, ou ainda arrays bi-dimensionais.

Matriz, de acordo com a wikipedia: "In mathematics, a matrix (plural matrices, or less commonly matrixes) is a rectangular array of numbers". Ou: "Em matemática, a matriz é um vetor retangular de números".

Amplamente utilizado nas ciências matemáticas, esse conceito ajuda a resolver problemas de álgebra linear, resolução de sistemas lineares, análise numérica, etc. E como a Ciência da Computação é muito matemática, as matrizes também são utilizadas. Uma área bem interessante que se aplica - e muito - é a da computação gráfica. Matrizes de projeção, transformação, etc, são a base de todo trabalho gráfico renderizado pelo computador que estamos acostumados a ver.

Uma matriz A é composta por m linhas e n colunas, e é representada matematicamente da seguinte maneira:

A = (	1	2	3	)
	4	5	6

Nesse caso, A é 2 x 3.

Em computação nós dizemos que uma matriz é um vetor de vetores. Hã?
Calma, pequeno padawan. Imagine um vetor v, com 2 posições. Imaginou? Agora, imagine outros dois vetores, k e r, com 3 posições cada, e preenchidos com números inteiros qualquer.
Se v for um vetor de vetores, atribuimos as duas primeiras posições de v para k e r:

k = { 1      ,2      ,3 };

r = { 4        ,5        ,6 };

v[0] = k;
v[1] = r;

Agora, podemos dizer que v é um array bi-dimensional. Porque? Porque podemos acessar, por exemplo, o número 5 da seguinte maneira: v[1][1]. Assim, acessamos o número na segunda linha, na segunda coluna.

Entendeu, pequeno padawan? v é uma matriz, um vetor de vetores.

Vamos ilustrar como se faz o algoritmo de soma de duas matrizes:


O algoritmo faz o seguinte:

• Inicializamos as variáveis i e j, para poder iterar sobre a matriz


• Inicializamos a matriz a, que é 2 x 3 e a matriz b, de mesmo tamanho.


• Criamos a matriz c, para poder guardar o valor da soma de a e b.


• Vem a parte que realiza a soma. Aqui, iteramos com dois laços de repetição, dois for's. O primeiro for faz o loop pelas linhas, enquanto o segundo faz o loop pelas colunas. Ou seja, para cada linha, o for de j itera em todas as colunas. Assim, colocamos a soma dos valores de a[i][j] com b[i][j] em c[i][j].

Por hoje é isso! Em breve, passarei as operações básicas sobre matrizes.