Fibonacci series in depth, using Swift

An iterative approach

f(0) = 0
f(1) = 1
var a = 0
var b = 1

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.

The recursion tree
return fib(n - 1) + fib(n - 2)
f(4) = f(3) + f(2) = f(2) + f(1) = f(1) + f(0) + f(1)

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
Passing the cache requires the use of inout parameters

Bottom-up Dynamic programming

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



Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store