13

No site codility existe um desafio inicial para você refatorar esse código:

var yourself = {
    fibonacci : function(n) {
        if (n === 0) {
            return 0;
        }
        if (n === 1) {
            return 1;
        }
        else {
            return this.fibonacci(n - 1) +
                this.fibonacci(n - 2);
        }
    }
};

E mesmo fazendo alterações acabo preso ao uso da recursão, e com isso recebo a mensagem de que a execução está muito lenta (Correct value, but the execution takes too long. Improve it!).

A pergunta é: Quais são as outras formas de fazer esse cálculo?

3 Respostas 3

21

A sequência de Fibonacci gera números que crescem muito rapidamente. Ocorre que do jeito que você está fazendo, cada chamada recursiva vai criar outras chamadas recursivas que criam outras chamadas recursivas que criam outras chamadas recursivas... até que no final de cada chamada recursiva, é produzido um resultado 0 ou 1.

Eis um exemplo do que ocorre, com fibonacci(8):

Fibonacci(8)

Nesta tabela aí em cima, a coluna da esquerda representa a primeira chamada de fibonacci(8). Ela se reduz a duas outras chamadas a fibonacci(7) e a fibonacci(6), que estão na segunda coluna. Cada uma dessas chamadas vai se subdividir várias vezes até que no final teremos um monte de zeros e uns.

Com isso podemos formar uma árvore de chamadas. Nas folhas dessas árvores temos zeros e uns que serão retornados para as funções chamadoras e serão somados até fornecer o resultado final, que é 21.

Observe que temos o número 1 aparecendo em 21 folhas. Também temos o número 0 aparecendo em 13 folhas. 13 também é o resultado de fibonacci(7). No total são 34 folhas, que é o resultado de fibonacci(9).

Se você montar essa árvore com outros números, você verá que para qualquer número n, o número de folhas será fibonacci(n + 1), o número de folhas com 1 será fibonacci(n) e o número de folhas com 0 será fibonacci(n - 1).

Cada uma dessas folhas requer um processamento para ser atingida. E no final, podemos ver que estamos na verdade apenas somando os resultados de um monte de zeros e uns. Isso é um número bem grande de somas. No total a operação de soma acontece fibonacci(n + 1) - 1 vezes.

Agora, peguemos o resultado de fibonacci(80), que é 23.416.728.348.467.684. Isso significa que o seu programa demorará uma eternidade para ficar somando um monte de zeros e uns até chegar a esse número. É por isso que o programa é lento. Utilizando a abordagem demonstrada na resposta do Antonio Carlos, isso é solucionado. Para calcular-se fibonacci(n), na verdade só são necessárias apenas (n - 1) somas. Ou seja, para calcular fibonacci(80) só precisamos de 79 somas na verdade.

Se observarmos essa árvore aí em cima, veremos que um monte de resultados são recalculados várias e várias e várias vezes. Assim sendo, se armazenarmos resultados intermediários já obtidos anteriormente em uma tabela, podemos posteriormente consultá-los ao invés de recalculá-los, deixando o programa mais eficiente. Esse é o princípio da programação dinâmica. Para calcular o fibonacci(n), temos que calcular primeiro o fibonacci(n - 1), até aí ok. Mas ao calcular o fibonacci(n - 1), já teremos calculado também o fibonacci(n - 2). Desta forma, não precisamos recalcular o fibonacci(n - 2), se tivermos guardado o resultado dele ao calcular o fibonacci(n - 1), basta somar esse resultado já guardado, o que evita ter que recomputá-lo.

No programa da resposta do Antonio Carlos, ele utiliza apenas as variáveis a e b. Isso ocorre porque na verdade só precisamos dos dois resultados mais recentes da tabela, pois ao calcular fibonacci(n), esses dois resultados mais antigos serão o fibonacci(n - 1) e o fibonacci(n - 2). Desta forma, qualquer coisa depois do fibonacci(n - 3) pode ser esquecida porque não será mais necessária. Assim sendo, podemos manter a tabela só com os dois últimos resultados ao representá-la apenas com duas variáveis, a e b. A variável f é apenas uma variável auxiliar para que nada seja perdido enquanto a tabela está sendo alterada, fato esse evidenciado se o código dele for reescrito assim:

var fibonacci = function(n) {
    var a = 0, b = 1;
    for (var i = 2; i <= n; i++) {
        var f = a;
        a = b;
        b += f;
    }
    return b;
};
5
  • Obrigado por uma resposta tão completa. Commented 13/01/2017 às 10:46
  • Victor Stafusa, cool (+1). Eu não sei javascript. Não queres pensar numa tabela com o time(fib(80)) das variantes que foram aparecendo? :)
    – JJoao
    Commented 13/01/2017 às 16:32
  • @JJoao Não sei se entendi direito o que você quer. Quer fazer um experimento para mensurar o tempo de cada algoritmo? Commented 13/01/2017 às 16:45
  • Acho que ele quer que você faça essa tabela com 80 ao invés de 8 :) Commented 13/01/2017 às 17:21
  • Acho que seria legal o operador ++ ficar no lado esquerdo: ++i ao invés de i++, não faz muita diferença, mas isso vai causar uma optimização extra de qualquer forma.
    – user37626
    Commented 13/01/2017 às 19:52
11

Uma maneira fácil de se implementar tal função eficientemente é utilizando programação dinâmica, o que consiste, basicamente, em armazenar resultados intermediários que serão reutilizados.

No caso do Fibonacci, basta armazenar os dois últimos resultados, ao invés de calcula-los a cada chamada. Assim, temos:

var fibonacci = function(n) {
    var a = 0, b = 1, f = 1;
    for(var i = 2; i <= n; i++) {
        f = a + b;
        a = b;
        b = f;
    }
    return f;
};

Fonte: The Polyglot Developer

1
  • Obrigado Antonio Carlos, acabei chegando a mesma conclusão. Commented 13/01/2017 às 10:47
6

Uma abordagem memorizadora, usando directamente o algoritmo inicial:

var yourself = {
    cache:{},
    fibonacci : function(n) {
        if (n in this.cache){ return this.cache[n] }
        if (n === 0)        { return 0;            }
        if (n === 1)        { return 1;            }
        return this.cache[n]=this.fibonacci(n-1) + this.fibonacci(n-2);
    }
};

yourself.fibonacci(100);
5
  • 1
    Não entendi muito bem mas sua alternativa também deu sucesso. Apenas modifiquei para retornar 0 e 1 e não this.cache[0]=0; e this.cache[1]=1; Commented 13/01/2017 às 16:40
  • 5
    @MBecker É que o algoritmo resultante é muito parecido com o seu algoritmo original. De fato ele é nada mais do que o seu algoritmo original com uma cache adicionada. Uma solução muito elegante. +1. Commented 13/01/2017 às 16:42
  • A otimização vem do fato de salvar o resultado em cache, evitando executar a operação e recursão novamente? Commented 13/01/2017 às 16:53
  • @MBecker, realmente fazer cache do 0 e 1, é excesso de zelo :)
    – JJoao
    Commented 13/01/2017 às 16:54
  • @MBecker, sim: evita a repetição dos cálculos elegantemente tabelados naquela medonha tabela do Victor Stafusa :)
    – JJoao
    Commented 13/01/2017 às 16:56

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .