find the nth fibonacci number in ruby

Here's a recursive implementation of finding the nth Fibonacci number in Ruby:

main.rb
def fibonacci(n)
  return n if n < 2
  fibonacci(n - 1) + fibonacci(n - 2)
end

puts fibonacci(10) #=> 55
106 chars
7 lines

However, this implementation has an exponential time complexity, which means that it becomes very slow for large values of n.

A more efficient approach is to use memoization to store the results of previous calculations so they can be reused later. Here's an implementation:

main.rb
@fibonacci_cache = {}

def fibonacci(n)
  return n if n < 2
  @fibonacci_cache[n] ||= fibonacci(n - 1) + fibonacci(n - 2)
end

puts fibonacci(10) #=> 55
153 chars
9 lines

This implementation has a linear time complexity and is much faster for large values of n.