Fibonacci sequence - a simple recursion and two performance improvements

The Fibonacci sequence is a sequence of numbers where each number is equal to the previous two numbers added together. Here's an example of this:

 1  1  2  3  5  8  13  21  34

So, 1 plus 1 is 2, 2 plus 3 is 5, 5 plus 8 is 13, and so on.

Let's use the Fibonacci sequence to help illustrate a number of concepts.

A recursive function is a function that calls itself in order to break down complex input into simpler ones. With each recursive call, the input problem must be simplified in such a way that eventually the base case must be reached.

The Fibonacci sequence can be easily implemented as a recursive function:

func Fibonacci(x int) int {
    if x == 0 {
        return 0
    } else if x <= 2 {
        return 1
    } else {
        return Fibonacci(x-2) + Fibonacci(x-1)
    }
}

In the preceding recursive function (Fibonacci), if the input is the simple case of 0 then it returns 0. Similarly, if the input is 1 or 2 then return 1.

An input of 0, 1 or 2 is called the base case or stopping condition; else, fib will call itself twice, adding the previous value in the sequence to the one preceding it:

Fibonacci(5) calculation graph

In the preceding figure Fibonacci(5) calculation graph, we can visually see how the fifth element in the Fibonacci sequence is calculated. We see f(3) is calculated twice and f(2) is calculated thrice. Only the final leaf nodes of 1 are added together to calculate the sum total of 5:

func main() {
   fib := Fibonacci
   fmt.Printf("%vn", fib(5))
}

Run that code and you'll get 5. Recursive functions perform identical calculations over and over again; f(3) is calculated twice and f(2) is calculated thrice. The deeper the graph, the more redundant calculations get executed. That is terribly inefficient. Try it yourself. Pass a value greater than 50 to fib and see how long you have to wait for the final result.

Go provides many ways to improve this performance. We'll look at two options: memoization and concurrency.

Memoization is an optimization technique used to increase performance by storing the results of expensive function calls and returning the cached result when the same input occurs again.

Memoization works well because of the following two properties of pure functions:

• They always return the same result given the same input(s)
• They have no side effects in the environment in which they run