memoized fib

gistfile1.rb

@max_size = 1000
@placeholder = []
(1..@max_size).each { |i| @placeholder[i] = :not_yet }

def fib(n)
  return "too large" if n > @max_size
  if n <= 1
    n
  elsif @placeholder[n] != :not_yet
    @placeholder[n]
  else
    @placeholder[n] = fib(n - 1) +  fib(n - 2)
    @placeholder[n]
  end
end
def fib_1(n)
  return "too large" if n > @max_size
  if n <= 1
    n
  elsif @placeholder[n] == :not_yet
    @placeholder[n] = fib_1(n - 1) +  fib_1(n - 2)
  else
    @placeholder[n]
  end
end

def non_memo_fib(n)
  return n if n <= 1
  non_memo_fib(n - 1) +  non_memo_fib(n - 2)
end