É possível fazer um cache do dado, que é o princípio básico da memoização, algo assim:
function fibonacci($n) {
static $cache = array();
if (isset($cache[$n])) return $cache[$n];
$a = 0;
$b = 1;
$c = 1;
for ($i = 1; $i < $n ; $i++) {
$c = $a + $b;
$a = $b;
$b = $c;
}
$cache[$n] = $c;
return $c;
}
Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.
A variável local estática foi usada para manter o estado entre as chamadas da função. Enquanto o código estiver sendo executado ela mantém seu valor. Ela funciona de forma semelhante à uma variável global, ou seja, seu tempo de vida é global. Mas seu escopo é local.
Esta solução é simplificada e ingênua, não tem nenhum tipo de persistência e não escala bem. Teria que fazer algo bem mais elaborado para atender outras demandas não tão triviais. Mas resolve legal para a maioria.
Se a preocupação é performance, neste tipo de algoritmo, é interessante pré-calcular uma sequência grande de números mais prováveis de uso e alocar no array já no código. Claro que poderá ter um consumo maior de memória. Até certo ponto compensa.
Esta técnica não funciona em todo tipo de algoritmo, especialmente em algoritmos não determinísticos, o que não é o caso presente.
Mas tem um jeito de já dar uma boa melhorada sem pré-calcular em tempo de desenvolvimento, ainda que vá consumir mais memória sem, potencialmente, precisar de todos os valores.
function fibonacci($n) {
static $cache = array();
static $prox = 3;
$cache[0] = 0;
$cache[1] = 1;
$cache[2] = 1;
if ($n < $prox) {
echo "cache -> "; //está aqui só para mostrar que entrou aqui
return $cache[$n];
}
for ($i = $prox; $i <= $n; $i++) $cache[$i] = $cache[$i - 1] + $cache[$i - 2];
echo $i - $prox . " passos -> "; //está aqui só para mostrar que entrou aqui
$prox = $n + 1;
return $cache[$n];
}
Veja funcionando no ideone. E no repl.it. Também coloquei no GitHub para referência futura.
Se quiser otimizar em tempo de desenvolvimento, pode adicionar $cache[3] = 2;
, $cache[3] = 3;
, $cache[4] = 5;
, etc. O ganho será pequeno.
Se sabe que vai usar em uma sequência grande e sabe o maior valor (mesmo aproximado) pode ajudar mandando executar este número maior, assim popula o cache.
A resposta que originou esta pergunta agora tem uma variação de cálculo que não precisa passar por toda sequência. O que diminui a necessidade do cache.
Tem um módulo para ajudar fazer cache de forma mais intensiva. Provavelmente pensaram em muita coisa que pode acontecer nessa situação e testaram bem. Mas pode ser um canhão pra matar passarinho.
Achei esta outra solução.
Particularmente prefiro a solução usando laço porque ela é mais natural em sequencia de dados. Recursão é para árvores e assemelhados.