def fib_naive(n)
  if n == 0 || n == 1
    n
  else
    fib_naive(n-1) + fib_naive(n-2)
  end
end

def fib_iterative_algorithm(n)
  fib_iter(n, 0, 1)
end

def fib_iter(n, k1, k2)
  if n.zero?
    k1
  else
    fib_iter(n-1, k2, k1+k2)
  end
end

def fib_iterative_optimization(n)
  k1 = 0
  k2 = 1
  while n > 0
    n -= 1
    (k1, k2) = [k2, k1+k2]
  end
  k1
end

require 'benchmark'

n = 10_000
Benchmark.bm do |b|
  b.report("naive") { n.times { fib_naive(8) } }
  b.report("iterative algorithm") { n.times { fib_iterative_algorithm(8) } }
  b.report("iterative optimization") { n.times { fib_iterative_optimization(8) } }
end








% ruby fibs.rb
      user     system      total        real
naive  0.560000   0.080000   0.640000 (  0.662477)
iterative algorithm  0.080000   0.020000   0.100000 (  0.088168)
iterative optimization  0.070000   0.000000   0.070000 (  0.079830)