Stupid Ruby Trick: Using a Hash to generate the Fibonacci Sequence

by gabebw

Via http://gist.github.com/173565, which is in turn via Nick Quaranto.

The gist pointed out that Hash.new, with its default values, is good for implementing Fibonacci sequences. So I decided to check:

fib = Hash.new do |hash,key|
  k = key.to_i
  hash[key] = case k
    when 0 then 0
    when 1 then 1
    else hash[k-1] + hash[k-2]
  end
end

This recursive (and memoized!) definition means that you can do fib[18] and get back 2584, plus you get the Fibonacci numbers from F0 (fib[0]) to F17 (fib[17]). Recursively defined Hashes are useful auto-memoized structures.

Advertisements