Fibonacci series in depth, using Swift

I’ve been learning about dynamic programming, and a good place to start is the Fibonacci sequence. The sequence itself is often used as an introduction to recursion in programming, due to its simplicity and familiarity to mathematicians.

This is intended to provide clarity for both dynamic programming and the implementation of such in Swift.

The Fibonacci sequence itself is the sequence of the two numbers that precede it, and has been said to govern the dimensions of everything from the Great Pyramid at Giza to seashells. That’s right, it is one of those mathematical sequences that seem to appear everywhere (including in nature) and is connected to the golden ratio (a favourite number for designers everywhere, as it is said to be the factor that makes the Mona Lisa beautiful).

The sequence begins with these first few numbers:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

Leading to the next number in the sequence 55 (as the result of the previous two numbers in the sequence, 21 + 34)

An iterative approach

This passes my most basic set of tests BasicTestSuite.playground that test to see if the result conforms to the sequence above.

Essentially the algorithm needs to be fed the first two numbers of the sequence :

f(0) = 0
f(1) = 1

which is equivalent to our coded

var a = 0
var b = 1

then we calculate each subsequent element of the sequence (each element is the sum of the previous two elements, according to the Fibonacci sequence).

The first two elements have already been defined (in the first pass as 0 and 1) so the result will be the addition of the two previous numbers. We loop, meaning we need to keep a reference to the previous number but one.

A recursive approach

Since each element of the Fibonacci sequence is made up of the previous two elements in the sequence, it is a perfect candidate for a recursive strategy.

Once again we need to know the first two elements of the sequence, and we think of these as the base cases, here represented by the guard statement within the code below (which will deliver fib[0] = 0 and fib[1] = 1, which is indeed the first two elements of the sequence).

Time O(2^n), Space O(n)

We can see this illustrated by the tree shown below:

The recursion tree

to work out the 4th element in the sequence we need to know fib(3), fib(2) and fib(1).

We make this happen recursively through the line:

return fib(n - 1) + fib(n - 2)

as each element of the sequence (n) is defined by the two that preceed it.

To put it another way:

f(4) = f(3) + f(2) = f(2) + f(1) = f(1) + f(0) + f(1)

We can see the disadvantage to this technique though, the tree shows that we are calculating fib(2) and fib(1) multiple times. When we are doing more work than is absolutely necessary we can often optimise our code to do better.

In this case, we can minimise work by using Dynamic programming.

Top-Down Dynamic programming (Memorization)

In Swift, the simplest way to improve our recursive approach is through memoization.

The external cache defined here can be accessed by any instance of fib

Time O(n), Space O(n)

Essentially it is the same algorithm, but with a cache to prevent having to recalculate already computed values. With Swift it is possible to pass the cache from instance of the function. To do so uses some more advanced features of Swift, but is included here for completeness.

Passing the cache requires the use of inout parameters

Time O(n), Space O(n) [Unchanged from above]

Bottom-up Dynamic programming

Bottom up is perhaps best thought of as starting from the beginning, and therefore avoiding recursion.

Bottom up approaches typically avoid the problem in recursion where the call stack can be built up to such a level that we see the infamous stack overflow (and it seems Swift does not guarantee tail recursion, so we don’t have an easy get-out).

The Fibonacci solution would look like the following:

Time O(n), Space O(n)

But there is one last optimisation that we can make, since we are looking at that space complexity and thinking…we can do a little better.

For Fibonacci sequence we only require the previous two values, yet in the solution above we have an array of size n. Surely we can simply store the previous two values as we walk along the Fibonacci sequence? It turns out we can, and a sample solution is below:

Time O(n), Space O(1)

I hope this has been of some help, although these ideas are feely available on the Internet it can be tricky to find Swift resources so I hope this has been of some value. If it has, you might want to “clap me do” or leave a comment below.

Thanks