The famous Fibonacci sequence starts off [1, 1, 2, 3, 5, 8, 13, 21, …] and continues forever. Each number in the series, except the first two, is the sum of the previous two numbers. For example, 3+5=8.

The canonical algorithm to calculate the series uses recursion and is elegant enough to be a common example of a recursive function. But while elegant conceptually, the algorithm is deadly computationally. In this post I’ll look at several ways to dodge the bullet.

Continue reading →