Testing for Fibonacci Numbers

2012-09-09

After working out how to check if a number falls within the Fibonacci sequence, I felt assured of the simplicity of my solution:

With the help of memoization, the above solution can easily deal with even large numbers.

After submitting my own solution, though, I had the chance to look at a number of other solutions. Looking back now, I see that the solution above is actually excessively verbose and unnecessarily expensive.

Instead, the following code does a much better job of testing numbers for membership in the Fibonacci sequence without the expense of recursion.

def is_fibonacci?(num)
  arr = [0, 1]
  while num > arr.last
    x, y = arr.pop(2)
    arr.push(x, y, x + y)
  end

  return true if num == arr.last
  return false
end

In effect, the function above is a non-recursive Fibonacci number generator. It also checks the most recent Fibonacci number against the candidate number until it can confirm whether the candidate falls within the series.

Since I've been thinking lots about recursive functions recently, I automatically assumed recursion was the best way to solve the problem. It makes me think of the saying "To someone who only knows how to use a hammer, all problems look like nails."