require 'benchmark'

class Fibonacci
  def self.calculate(n)
    return n if n <= 1
    calculate(n - 1) + calculate(n - 2)
  end

  def self.calculate_with_memoization(n)
    @calculate ||= {}
    @calculate[n] ||= begin
      if n <= 1
        n
      else
        calculate_with_memoization(n - 1) + calculate_with_memoization(n - 2)
      end
    end
  end
end

n = 30

Benchmark.bm(15) do |bm|
  bm.report('Without memoization') { Fibonacci.calculate(n) }
  bm.report('With memoization') { Fibonacci.calculate_with_memoization(n) }
end