examples of iterative and recursive fibonacci

fibonacci.rb

# n       0  1  2  3  4  5  6   7   8   9  10  11  12  13  14
# fib(n)  0  1  1  2  3  5  8  13  21  34  55  89 144 233 377

# iterative solution
def fib(n)
  return n if n == 0 || n == 1
  fibs = [0,1]
  (n - 2).times do
    temp_fib = fibs.reduce(:+)
    fibs[0] = fibs[1]
    fibs[1] = temp_fib
  end
  fibs.reduce(:+)
end

# recursive solutions

# If I give this n, it does 2^n units of work
def fib(n)
  return 0 if n == 0
  return 1 if n == 1
  return fib(n - 1) + fib(n - 2)
end

# If I give this n, it does n units of work
def fib(n, indentation = 0)
  # puts "  " * indentation + "fib(#{n})"
  return 0 if n == 0
  return 1 if n == 1
  return fib(n - 1, indentation + 1) + fib(n - 2, indentation + 1)
end