implement fibonacci numbers

fibonacci.rb

# this is constant space, linear time, no memoization.
def fib(n)
  counter, current, previous = 0, 0, 1
  while counter < n
    counter, current, previous = counter + 1, current + previous, current
  end

  current
end

# linear time the first time (for fib(n)) and constant time for subsequent access.
# linear heap space (storing all the fib(n) up to a value) for the memoization
# but - because it's recursive still, you have linear stack space as well during computation
@fibs = [0, 1]
def fibm(n)
  unless @fibs.size > n
    @fibs.push(fibm(n-1) + fibm(n-2))
  end
  @fibs[n]
end

# can we merge these?
# 1: redefine our linear fib method to build from given position and return the next n - counter values
def fibb(n, counter=0, current=0, previous=1)
  # fib builder - generate an array of fibonacci numbers using the same process, but from given position
  fibs = []
  while counter <= n
    counter, current, previous = counter + 1, current + previous, current
    fibs.push(current)
  end

  fibs
end

# leverage that to merge them - build an array of missing values from the array of known values rather than ab initio
def fibc(n)
  # @fibs.size should be at 1 greater than n before reading @fibs[n] 
  if n >= @fibs.size
    # append new numbers to existing array
    @fibs = @fibs + fibb(n, @fibs.size, @fibs[-1], @fibs[-2])
  end
  @fibs[n]
end

of course, there's the version that's not linear time, used as a straw man in freshman computer courses to discuss recursion and memoization and programming techniques to avoid this problem. It has the benefit of looking just like the definition given:

def badfib(n)
  if n == 0
    0
  elsif n == 1
    1
  else
    badfib(n-1) + badfib(n-2)
  end
end

but lets assume we're past that. This answers badfib(10) fine, don't call badfib(100) if you're in an hurry. On my machine badfib(30) is visibly delayed (Benchmark.measure gives is 200ms time), badfib(40) takes 17s, badfib(41) takes 27s, badfib(42) takes 45s, badfib(43) takes 72s, and it continues growing, effectively in line with the size of the result, since the same process is unfolding: time to compute badfib(n+1) is time to compute badfib(n) + time to compute badfib(n-1), as we recalculate completely all prior vales.

Using a smaller range to illustrate the additive nature of the time:

 [30, 31, 32, 33, 34, 35, 36, 37].map {|n| Benchmark.measure { badfib(n) }.real }
=> 
[0.15843276598025113,
 0.22394006402464584,
 0.36120777600444853,
 0.5835691520187538,
 0.9502950809837785,
 1.5418475820042659,
 2.498658891010564,
 4.102677893009968]