Fibonacci Sequence with GO

I recently decided to take some time and teach myself a new programming language. I mostly work with Python and occasionally, JavaScript for and in my profession. I am not a master of either, but out of curiosity, availability of some free time to myself, excitement brought about by challenges and of course, a nasty experience during an Amazon interview, I opted to pick and learn this new language.

Of course I could have picked other languages, be it human, like Xhosa or programming, like Java, C++ etc, but why I mainly opted for Golang is a story for another day.

Fibonacci Sequence

From that nasty experience (that I will write about in the near future), the one thing that came out of that experience, especially as a self-taught developer, is the need to understand data structures and algorithms. And that is why I am writing this article, and a few more later on, to make this series on data structure and algorithms.

Fibonacci sequence, one of the most common mathematical formulas out there, refers to a sequence of numbers in which each number is a sum of its two preceding numbers.

source: https://math.libretexts.org/Bookshelves/Applied_Mathematics/Book%3A_College_Mathematics_for_Everyday_Life_(Inigo_et_al)

The implementation of this algorithm with Go can be achieved with the code:

Give it a try on Go Playground

Fibonacci sequence and generation of the sequence numbers is a recursive exercise. Using the code sample above, as n increases, there is a significantly higher cost, in terms of time and space, required to run to completion this algorithm. This time and space complexity jargon used to measure efficiency in running of an algorithm is referred to as the Big O notation. Discussion on the Big O notation is beyond the scope of this article.

Question is, how do we optimize our script for faster compute times and reduced memory resource usage?

Memoization

This is a concept in computer science used to optimize and speed up expensive or costly processes by cache of results.

With regards to generation of Fibonacci sequence of numbers and the recursive nature of the algorithm, caching of outcome with every iteration helps speed up execution.

Fibonacci Tree Representation (source: https://inst.eecs.berkeley.edu/~cs61bl/r//cur/trees/fibtree5.png)

Using the figure above, the recursive nature of the algorithm can be represented as below (see what I did there? :-) ):

Fib(0) = 0
Fib(1) = 1
Fib(2) = Fib(1) + Fib(0)
Fib(3) = Fib(2) +Fib(1)
Fib(5) = Fib(4) + Fib(3)

The computation of the 5th Fibonacci sequence number can be significantly made faster if the results of the 3rd and 4th terms were cached. Now imagine how much faster the 50th sequence number can be generated, considering all the previously stored/cached sequence values. Its as fast as retrieving the values from storage and summing them up.

Here is the implementation with memoization…

Go Playground link

Don’t take my word for it as regards how blazing fast the execution is. Give it a try.

Conclusion

There is no quicker, fun and better optimized method for learning a new language, than trying the syntax out with data structures and algorithms exercises. In addition to improved retention of the language syntax, it also helps one develop applications that are rather time and memory efficient.

In the example above, through memoization, we have managed to significantly speed up the computation of the algorithm. This definitely leaves the processing compute not exhausted (lol) but with more memory available to undertake other jobs ;-)

PS: — Though I’m a newbie, I’d greatly appreciate feedback. Thanks