With caching...
fib = Hash.new do |k, v|
next 1 if v == 0 || v == 1
unless k.key? v
k[v] = k[v-1] + k[v-2]
end
k[v]
end