[resolvido] Como vcs fariam?

System.out.println("Tcharam: " + valor);

“Tcharam” kkkkkkkkkkkkkkkkkkkkkkkkkkk ;x

JuniorMaia:

System.out.println("Tcharam: " + valor);

“Tcharam” kkkkkkkkkkkkkkkkkkkkkkkkkkk ;x

AWUHIUSHUIWHOAHSUAHOUIAW

Da forma que você fez, não é recursiva. Lembre-se, uma função recursiva é aquela que chama a si mesmo. [E o caso da função de Fibonacci, que pode ser calculada assim:
[img]http://upload.wikimedia.org/wikipedia/pt/math/0/d/5/0d5cce25d67941bb4661afd52609d93c.png[/img]

O segredo está em perceber que quando você calcula um número, como o fibonacci de 6, você calcula:
[img]http://www.cs.ucc.ie/~dongen/mpost/jpg/FibonacciTree0.jpg[/img]

Note que o fib(4) teve que ser calculado 2 vezes (para o resultado de fib(6) e de fib(5)). O mesmo vale para o fib(3), que teve que ser calculado 3 vezes. E é justamente o fato de calcular várias vezes a mesma coisa que torna tudo tão ineficiente (alguns números chegam a ser calculados dezenas de vezes).

O que você tem que fazer, então, é guardar os valores já calculados no array. Só recalcule-os se não estiverem calculados.

public class Fibonacci 
{
    private long[] valores = new long[2000];

    public Fibonacci() {
        valores[1] = 1;
    }

    public long calcula(int n) {
        if (n == 0) return 0;

        //Retornamos valores já calculados diretamente
        if (valores[n] != 0) return valores[n];

        //Caso contrário, calculamos e guardamos o valor calculado
        valores[n] = calcula(n-1) + calcula(n-2);

        return valores[n]; //Retornamos o valor calculado
    }
}

System.out.println("Tcharam: " + new Fibonacci().calcula(50));

A técnica de guardar valores pré-calculados na memória chama-se cache.
Esse programa pode ser mais rápido, mas ocupa muito mais memória que o anterior.

Quanto falamos em performance, sempre temos que lidar com o trade-off de processador vs. memória.

ViniGodoy:

Da forma que você fez, não é recursiva. Lembre-se, uma função recursiva é aquela que chama a si mesmo. [E o caso da função de Fibonacci, que pode ser calculada assim: [img]http://upload.wikimedia.org/wikipedia/pt/math/0/d/5/0d5cce25d67941bb4661afd52609d93c.png[/img]

O segredo está em perceber que quando você calcula um número, como o fibonacci de 6, você calcula:
[img]http://www.cs.ucc.ie/~dongen/mpost/jpg/FibonacciTree0.jpg[/img]

Note que o fib(4) teve que ser calculado 2 vezes (para o resultado de fib(6) e de fib(5)). O mesmo vale para o fib(3), que teve que ser calculado 3 vezes. E é justamente o fato de calcular várias vezes a mesma coisa que torna tudo tão ineficiente (alguns números chegam a ser calculados dezenas de vezes).

O que você tem que fazer, então, é guardar os valores já calculados no array. Só recalcule-os se não estiverem calculados.

public class Fibonacci 
{
    private long[] valores = new long[2000];

    public Fibonacci() {
        valores[1] = 1;
    }

    public long calcula(int n) {
        if (n == 0) return 0;

        //Retornamos valores já calculados diretamente
        if (valores[n] != 0) return valores[n];

        //Caso contrário, calculamos e guardamos o valor calculado
        valores[n] = calcula(n-1) + calcula(n-2);

        return valores[n]; //Retornamos o valor calculado
    }
}

No main, rode com:

System.out.println("Tcharam: " + new Fibonacci().calcula(50));

A técnica de guardar valores pré-calculados na memória chama-se cache.
Esse programa pode ser mais rápido, mas ocupa muito mais memória que o anterior.

Quanto falamos em performance, sempre temos que lidar com o trade-off de processador vs. memória.

brigado, se vc tiver algum exercicio parecido com esse me fale, por favor...

Tente fazer fatorial, é clássico pedirem isso.
Na faculdade e as vezes até em entrevista.
Essa do fibonacci do vini foi massa.
mlk zica.

O único que melhorei foi o do método bolha.
Esse do fibonacci sempre fiz da maneira clássica e burra.

A complexidade desse algoritmo é de ordem n², gostaria de saber como ficaria a pilha em um fibonacci.

fatorial de 5 a pilha ficaria nessa ordem.

:1:

::2::
:::3:::
::::4::::
:::::5::::: em um algoritmo como esse literalmente se chega ao topo e depois vc volta multiplicando.(e todos tem critério de parada, nesse caso zero).

Estava pensando como seria a pilha do fibonacci , mas é como o vini fez uma árvore.