Terceiro Desafio Fibonnaci da apostila Caelum

Você pode usar um mapa para armazenar os valores já calculados.

private Map<Integer, BigInteger> fibonacciMap = new HashMap<Integer, BigInteger>(1000);
	
	{
		//as condições de parada triviais são adicionadas ao mapa de valores conhecidos
		fibonacciMap.put(0, BigInteger.ZERO);
		fibonacciMap.put(1, BigInteger.ONE);
	}
	
	public BigInteger fibonacci(int n) {
		if (n < 0) {
			throw new IllegalArgumentException("n < 0");
		}
		if (fibonacciMap.containsKey(n)) {
			return fibonacciMap.get(n);
		} else {
			BigInteger n1 = fibonacci(n - 1);
			fibonacciMap.put(n - 1, n1); //insere o valor calculado no cache
			BigInteger n2 = fibonacci(n - 2);
//			não é necessário gravar este valor pois ele já se encontra no mapa
			return n1.add(n2);
		}
	}

Ataxexe:

Você pode usar um mapa para armazenar os valores já calculados.

private Map<Integer, BigInteger> fibonacciMap = new HashMap<Integer, BigInteger>(1000);
	
	{
		//as condições de parada triviais são adicionadas ao mapa de valores conhecidos
		fibonacciMap.put(0, BigInteger.ZERO);
		fibonacciMap.put(1, BigInteger.ONE);
	}
	
	public BigInteger fibonacci(int n) {
		if (n < 0) {
			throw new IllegalArgumentException("n < 0");
		}
		if (fibonacciMap.containsKey(n)) {
			return fibonacciMap.get(n);
		} else {
			BigInteger n1 = fibonacci(n - 1);
			fibonacciMap.put(n - 1, n1); //insere o valor calculado no cache
			BigInteger n2 = fibonacci(n - 2);
//			não é necessário gravar este valor pois ele já se encontra no mapa
			return n1.add(n2);
		}
	}

ahh! mas aki so vai ficar rapido da segunda vez que rodar neh?
ou se vc ja deixar o vetor populado antes de inicializar o programa?

:) vlw pela atencao

Na verdade não. Na primeira vez ele irá rodar a toda.

O problema da recursividade no Fibonnaci é aqui:

fibo2(estamos-1) + fibo2(estamos-2)

Repare que duas chamadas a função são feitas. Com isso serão calculados sempre dois valores iguais para resolver o problema.

Exemplo:
f(5) = f(4) + f(3). Só que f(4) depende do f(3), depois que o f(3) for calculado para o primeiro membro da soma, a função irá calcular f(3) novamente para o segundo membro, desperdiçando todo o trabalho feito anteriormente. Se você armazenar os valores já calculados, o segundo membro não será calculado novamente pois seu valor estará armazenado no mapa.

Repare que somente as condições triviais (0 e 1) são adicionadas ao mapa. Os outros valores serão adicionados conforme forem calculados.

Eu sinceramente duvido que haja uma versão recursiva tão rápida quanto a iterativa, mesmo usando técnicas de memoização.

Só o overhead gerado por cada chamada já mata. Isso sem falar no StackOverflowException.

Ataxexe:

Na verdade não. Na primeira vez ele irá rodar a toda.

O problema da recursividade no Fibonnaci é aqui:

fibo2(estamos-1) + fibo2(estamos-2)

Repare que duas chamadas a função são feitas. Com isso serão calculados sempre dois valores iguais para resolver o problema.

Exemplo:
f(5) = f(4) + f(3). Só que f(4) depende do f(3), depois que o f(3) for calculado para o primeiro membro da soma, a função irá calcular f(3) novamente para o segundo membro, desperdiçando todo o trabalho feito anteriormente. Se você armazenar os valores já calculados, o segundo membro não será calculado novamente pois seu valor estará armazenado no mapa.

Repare que somente as condições triviais (0 e 1) são adicionadas ao mapa. Os outros valores serão adicionados conforme forem calculados.

entendi!

funcionou!

só uma ultima pergunta sobre o seu programa:

o que eu fiz se voce poe o numero 40 primeiro por exemplo, ele ja deixa calculado de 0 a 40 no vetor,.
O seu deixa de 0 a 40 tambem ou popula somente o 40?

vlw

Ele retorna o resultado para o número 40, mas deixa no mapa todos os resultados de 2 a 40 (o 0 e o 1 já estão armazenados).

perfect 8)

vlw denovo

Ataxexe, vc poderia explicar de novo pq a versao com o vetor e mais rapida? Nao entendi aquilo de o segundo membro e tals.se usar arrays para armazenar, qual a vantagem ja que ele tera que calcular tudo da mesma forma?

Esta é justamente a vantagem, você NÃO terá que calcular tudo de novo.

Num fibonacci de 50, o algoritmo reentra pra calcular fibonacci de 1 umas… 2^50 vezes, de 2 umas 2^50 também, de 3 umas 2^49, e vai indo.

Se você já guardar o valor de retorno dessas funções, não precisará calcular tudo, no final só fazendo umas 50 e poucas operações.

Um exemplo com vários Fibonaccis que andei coletando(e fazendo):

import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;

public class Fibonacci
{
    private static long reentradas;

    public static BigInteger fib(int n)
    {
        reentradas++;
        if (n <= 2)
            return BigInteger.ONE;
        else
            return fib(n - 1).add(fib(n - 2));
    }

    public static BigInteger fibTail(int n, BigInteger current, BigInteger next)
    {
        reentradas++;
        if (n == 0)
            return current;
        else
            return fibTail(n - 1, next, current.add(next));
    }
    private static List<BigInteger> list = new ArrayList<BigInteger>(0);

    public static BigInteger fibMem(int n)
    {
        reentradas++;
        if (n < list.size())
            return list.get(n);
        else
        {
            BigInteger resultado;

            if (n <= 1)
                resultado = new BigInteger(new Integer(n).toString());
            else
                resultado = (fibMem(n - 2).add(fibMem(n - 1)));

            list.add(resultado);

            return resultado;
        }
    }

    public static BigInteger fibIter(int n)
    {
        if (n <= 2)
        {
            reentradas++;
            return BigInteger.ONE;
        }

        BigInteger a = BigInteger.ONE;
        BigInteger b = BigInteger.ONE;

        for (int i = 3; i <= n; i++)
        {
            reentradas++;
            BigInteger c = a.add(b);
            a = b;
            b = c;
        }
        return b;
    }

    public static void main(String[] args)
    {
        int numero = 40;
        long t = System.currentTimeMillis();

        System.out.println("Fibonacci Normal: " + fib(numero));
        System.out.println("Reentradas: " + reentradas + " - " + (System.currentTimeMillis() - t) + " ms");
        t = System.currentTimeMillis();

        reentradas = 0;
        System.out.println("Fibonacci Memoizado: " + fibMem(numero));
        System.out.println("Reentradas: " + reentradas + " - " + (System.currentTimeMillis() - t) + " ms");
        t = System.currentTimeMillis();

        reentradas = 0;
        System.out.println("Fibonacci Tail Recursion: " + fibTail(numero, BigInteger.ZERO, BigInteger.ONE)); // deve imprimir 102334155
        System.out.println("Reentradas: " + reentradas + " - " + (System.currentTimeMillis() - t) + " ms");
        t = System.currentTimeMillis();

        reentradas = 0;
        System.out.println("Fibonacci Iterativo: " + fibIter(numero));
        System.out.println("Reentradas: " + reentradas + " - " + (System.currentTimeMillis() - t) + " ms");
    }
}

Fibonacci Normal: 102334155
Reentradas: 204668309 - 17828 ms
Fibonacci Memoizado: 102334155
Reentradas: 79 - 0 ms
Fibonacci Tail Recursion: 102334155
Reentradas: 41 - 0 ms
Fibonacci Iterativo: 102334155
Reentradas: 38 - 0 ms

1. Um método pode chamar ele mesmo. Chamamos isso de recursão. Você pode resolver a série de fibonacci
   usando um método que chama ele mesmo. O objetivo é você criar uma classe, que possa ser usada da
   seguinte maneira:

Fibonacci fibo = new Fibonacci(); int i = fibo.calculaFibonacci(6); System.out.println(i);
Aqui imprimirá 8, já que este é o sexto número da série.
Este método calculaFibonacci não pode ter nenhum laço, só pode chamar ele mesmo como método. Pense
nele como uma função, que usa a própria função para calcular o resultado.

Bom não estou conseguindo entender o que é realmente p fazer alguém pode me explicar direito!

Rafaela, recursão é quando um método(função, subprograma, é tudo a mesma coisa) chama ele mesmo.

Por exemplo:

int metodoComNomeEstranho(int entrada)
{
   int umNumeroInteressante = entrada + 1;

   return metodoComNomeEstranho(umNumeroInteressante);
}

Aqui o metodoComNomeEstranho recebe um número inteiro como entrada, e dentro do corpo dele ele chama a si próprio, passando o número da entrada + 1. Assim se no começo eu chamar com 42, ele vai adicionar mais 1, virando 42, e chamará a si próprio com 43, onde começa o nome método, adiciona mais 1, vira 44, chama com 44, vira 45, 46, 47, 48…

Um problema desses métodos recursivos é que eles nunca acabarão se ficarem chamando a si próprios. É por isso que existe algo chamado Condição de Parada.

int metodoComNomeEstranho(int entrada)
{
   int umNumeroInteressante = entrada + 1;

   if (umNumeroInteressante >= 42)
      return 100;
   else
      return metodoComNomeEstranho(umNumeroInteressante);
}

Nesta versão, quando a entrada chegar pelo menos a 41, esse número incrementa mais 1, e vira 42. Depois vem a condição que se o número for 42 ou maior, o método retornará 100, acabando aí a recursão. Este número 100 será repassado para as chamadas anteriores, até o método original, que finalmente retorna 100.

O fibonacci é uma função definida por:

O número de entrada vai diminuindo até chegar à condição de parada, se for igual a zero, retorna zero, igual a 1 retorna 1, para o resto é a soma das chamadas com a entrada menos um, com a chamada com entrada menos dois.

Acima neste tópicos fizemos várias maneiras de calcular este número, algumas com recursão, algumas usando laço.