Um Fibonacci Melhor

melhorias podem ser encontradas nesta dica

A série Fibonacci. Você não sabe o que é até entender por que isso funciona:

PHI = 1.6180339887498948482045868
fib = lambda do |n|
  (
    ( PHI**n - ( 1 - PHI )**n ) /
    Math.sqrt(5)
  ).
  floor
end

Com este código Ruby, simplesmente chame fib [n] onde n é qualquer número para obter o elemento correspondente da série (clássica) de Fibonacci.

Por que isso funciona? Porque a constante PHI é definida recursivamente. A lição aqui é que, se você puder isolar a recursão em um valor constante, poderá escrever uma expressão matemática não recursiva.

(A dificuldade, é claro, é escolher a constante adequada. Mas essa é a arte da análise matemática!)

NOTA: pegue os primeiros 2.000 números Fibonacci aqui: http://oeis.org/A000045/b000045.txt