As formas mais curtas que eu cheguei foram:
Função recursiva:
function f(n){return n<3?1:f(n-1)+f(n-2)}
No caso estou usando o retorno direto e aplicando um operador condicional para testar se o valor é menor que 3 para retornar 1 e senão ele aplica o calculo recursivo.
Dessa maneira da pra eliminar a virgula, declaração de variáveis ou sintaxes muito expressivas. Porém o desempenho é um dos piores possíveis.
Função com cache em variáveis:
function f(n,a,b){return n<3?1:!a?f(n-1)+f(n-2):!b?f(n-1)+a:a+b}
Neste caso usei o mesmo recurso de operador condicional, porém inclui também um teste para ver se as variáveis a
existe e depois b
mudando a formula do calculo para utilizar o cache se este estiver disponível.
A mesma função pode ser escrita da seguinte maneira:
function f(n,a,b){
if (n < 3) return 1;
if (typeof a === 'undefined') return f(n - 1) + f(n - 2);
if (typeof b === 'undefined') return f(n-1)+a;
return a+b;
}
Função com cache em Array:
function f(n,c){c=c|[];return !c[n]?c[n]=n<3?1:f(n-1,c)+f(n-2,c):c[n]}
Primeiro eu testo utilizando |
(operador bitwise or) para ver se a variável c
que representa o cache existe, se ela existe, utilizo ela mesmo, caso não exista ela passa receber como valor uma nova array.
No calculo, será verificado se existe um valor em cache antes de qualquer coisa, não existindo nada no cache, vai verificar se o valor é menor que 3 para retornar 1 ou tentar recursivamente aplicar a mesma função.
Para ter um melhor aproveitamento do cache é possível adapta-la desta maneira:
function f(n){return !f.c[n]?f.c[n]=n<3?1:f(n-1)+f(n-2):f.c[n]};f.c=[];
Neste caso o cache está sendo armazenado como propriedade da função, podendo ser re-aproveitada nas próximas vezes em que a função for executada, não tendo que re-calcular os valores já adicionados no cache.
Uma forma para melhor leitura desta função seria:
function f(n) {
if (typeof f.cache[n] === 'undefined') {
if (n < 3) {
f.cache[n] = 1;
return f.cache[n];
}
f.cache[n] = f(n - 1) + f(n - 2)
return f.cache[n];
}
return f.cache[n];
}
f.cache=[];