argcv

codes and stuff

Fibonacci com apenas uma chamada recursiva

leave a comment »

Uma solução clássica para o problema de encontrar um número da sequência de Fibonacci com um algoritmo recursivo é a seguinte:

int calculaFibonacci (int n) {
    if (n < 2) return n;
    else return calculaFibonacci (n - 1) + calculaFibonacci (n - 2);
}

Entretanto, é sabido que duas chamadas recursivas podem pesar bastante.

Pensando nisso, eu escrevi uma solução que usa uma só chamada recursiva aliada a um vetor. Para isso, ao invés de começar os cálculos por n, a função começa por i, que vale 2. A lógica disso é que, sabendo v[i-2] = 0 e v[i-1] = 1, eu posso determinar v[i] (que é v[i-2] + v[i-1]), e, assim, determinar v[i+1…n], usando uma chamada recursiva para cada v[i], até que i seja igual a n e a função tenha achado o que se pede, que é sempre v[n].

Para conseguir o efeito de começar a calcular por i = 2 e usar um vetor v[n] sem que, quando quiser encontrar o número de Fibonacci preterido o usuário da função tenha que especificar esses dois dados à função sem qualquer motivo aparente, eu criei uma função chamada fibonacci(), que funciona como um pacote, simplesmente criando v[n], especificando os dois valores iniciais para v[] e chamando calculaFibonacci() com n, i = 2 e v.

Eis, então, o algoritmo.

#include <stdio.h>

int fibonacci (int n);
int calculaFibonacci (int n, int i, int v[]);

void main () {
    int a = fibonacci (40);
    printf ("%d\n", a);
}

/*  Esta função recebe n >= 0 e devolve o número  */
/*  de fibonacci presente na (n+1)-ésima posição. */

int fibonacci (int n) {
    int v[n];
    v[0] = 0; v[1] = 1;
    return calculaFibonacci (n, 2, v);
}

/*  A função abaixo recebe n >= 0, i = 2 e v[].  */
/*  Preenche o subvetor v[2...n] e retorna v[n]  */
/*  para a função chamadora.                     */

int calculaFibonacci (int n, int i, int v[]) {
    if (i >= n) return ((n == 0) ? 0 : v[i-1] + v[i-2]);
    else v[i++] = v[i-1] + v[i-2];
    calculaFibonacci (n, i, v);
}

Até mais.

Anúncios

Written by rntreis

junho 2, 2012 às 1:29 pm

Publicado em C, dicas, programação

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s

%d blogueiros gostam disto: