A Better Way to Generate the Fibonacci Sequence

The Fibonacci sequence is well-known in math and engineering. It starts with 0 and 1; each subsequent number is defined as the sum of the preceding two. Thus, the sequence looks like this:

0 1 1 2 3 5 8 13 21 ...

Traditionally, implementations of the Fibonacci sequence are recursive. For example, to compute the nth number of the sequence (n starting at 0), you could write the following Clojure code:

(defn fibonacci [n]
  (if (> n 1)
    (+ (fibonacci (dec n)) (fibonacci (- n 2)))
    n))

In other words, for any n greater than 1, we compute the nth number using the preceding two numbers; for any n less than or equal to 1, we simply return n since the first two Fibonacci numbers coincide with their indices.

One problem with this approach is that it consumes the stack, meaning the attempt to compute the nth number for a sufficiently large n will result in a stack overflow. Also, the function calls branch out exponentially – the first invocation results in two sub-invocations, each of which calls itself twice over, and so on. Therefore, computing only the 40th number already takes several seconds. Lastly, the two recursive calls duplicate a lot of work: computing the number at index n - 1 already computes the number at n - 2, yet the latter step is repeated regardless.

Popular approaches to these problems include the use of memoization to avoid redundant computations; you could also use a loop instead of recursion to avoid stack overflows. Both approaches greatly improve performance, reducing time complexity from exponential to linear. But I recently learned about an approach you may not have heard of: it is non-recursive, indeed non-iterative, reducing time complexity to O(1).

It’s called Binet’s formula (proof). It computes each number directly using the golden ratio, denoted by phi, bypassing the need for iterative computation:

(defn fibonacci' [n]
  (let [phi (/ (+ 1 (Math/sqrt 5)) 2)]
    (Math/round (/ (- (Math/pow phi n) (Math/pow (- 1 phi) n)) (Math/sqrt 5)))))

(Rounding counteracts the imprecision of floating-point arithmetic introduced through the use of the golden ratio, which is an irrational, ie floating-point, number. Note also that the actual performance of Binet’s formula depends on how the language/runtime handles floating-point operations and large-number arithmetic.)

The reason Binet’s formula can compute Fibonacci numbers directly, ie without having to compute preceding numbers, is that it takes advantage of a fascinating underlying connection between the Fibonacci sequence and the golden ratio. I’m not a mathematician, but I understand that, as n increases, F(n + 1)/F(n) converges to the golden ratio (where F denotes the Fibonacci function). For instance, 5/3 is 1.666..., which is somewhat close to the golden ratio of approximately 1.61803. When we look at the next pair of numbers in the sequence, 8/5 equals 1.6, inching closer to the golden ratio. 13/8 is 1.625, which is closer yet again, and so on. This pattern continues as we progress in the sequence.

Using Binet’s formula, calculating even the 40th number is lightning fast:¹

(fibonacci' 40)
; => 102334155

To generate the sequence for the first x numbers, we can leverage Clojure’s built-in support for sequences:

(->> (range) (map fibonacci') (take x))

Next time you’re in a coding interview, you may wow the interviewer with this improved approach.