The Fibonacci Sequence Printed With Golang

I figured I would change it up a bit and get into the basics of Golang and common Computer Science study material taught in school, but often used in software engineering type positions. We’re going to revisit a post I wrote back in 2015 regarding the Fibonacci number and generating the sequence in JavaScript. This time I figured it would be useful to walk through how to accomplish the same using the Go programming language.

Why do I want to talk about Fibonacci related material?

Well, it is a good way to learn about a development language such as Golang and like I said previously, it would benefit you as a refresher when it comes to interviewing for a job.

Going into this, you should note that there are many ways to calculate the Fibonacci number and I won’t be going over all of them. Just a few of the common strategies will be shown here.

Fibonacci via Wikipedia:

By definition, the first two numbers in the Fibonacci sequence are either 1 and 1, or 0 and 1, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

An example of the sequence is as follows:

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 …

As a disclaimer, I am no mathematician, but you should note that the sequence can start with a zero or a one.

Let’s take a look at some of the ways that we can calculate the Fibonacci number, not the sequence.

Calculating the Fibonacci Number with Recursion

Recursion is a good thing to know even if it isn’t always the most efficient. Heck, I like it because it greatly reduces excess or repetitive code.

func FibonacciRecursion(n int) int {
    if n <= 1 {
        return n
    }
    return FibonacciRecursion(n-1) + FibonacciRecursion(n-2)
}

In the above function we accept a placeholder number which represents which number in the sequence we wish to return. The return value is an integer.

With recursion, we’ll continue to perform operations using the function until we’ve drilled into too small of a placeholder value, at which point we just return the placeholder value.

For example, the flow would look something like the following:

recursive(4) + recursive(3)
(recursive(3) + recursive(2)) + (recursive(2) + recursive(1))
((recursive(2) + recursive(1)) + 1) + (1 + 1)
((1 + 1) + 1) + (1 + 1)
5

Of course the result is dependent on whether or not you’re starting at zero or one.

Calculating the Fibonacci Number with Slices and Loops

What if you’re not into recursion and want to stick to some old fashion loops? Well that is still a possibility. The same code for what we just saw would look like the following in loop format:

func FibonacciLoop(n int) int {
    f := make([]int, n+1, n+2)
    if n < 2 {
        f = f[0:2]
    }
    f[0] = 0
    f[1] = 1
    for i := 2; i <= n; i++ {
        f[i] = f[i-1] + f[i-2]
    }
    return f[n]
}

So what is happening in the above code?

We still provide a placeholder number of the sequence and return the particular Fibonacci value, but how we accomplish this is different.

We are working with slices because we cannot create arrays with numeric lengths that are not constant. The first thing we do is create the slice which has a length of n+1 and a capacity of n+2. The length needs to be more than n because if we pass in a value of two, we also need to accommodate the zero index which means our slice needs to be of length three, not two.

If our placeholder is less than two, we need to increase the length of our slice to hold at least the first and second Fibonacci numbers. Finally we can loop similarly to how we did with recursion and return the final value of the slice. Each resulting value in the loop is stored in the slice.

Calculating the Finonacci Sequence

If you want to see this in a working application for generating the sequence up to a particular placeholder value, you can check out the Golang code below:

package main

import (
    "fmt"
    "strconv"
)

func FibonacciLoop(n int) int {
    f := make([]int, n+1, n+2)
    if n < 2 {
        f = f[0:2]
    }
    f[0] = 0
    f[1] = 1
    for i := 2; i <= n; i++ {
        f[i] = f[i-1] + f[i-2]
    }
    return f[n]
}

func FibonacciRecursion(n int) int {
    if n <= 1 {
        return n
    }
    return FibonacciRecursion(n-1) + FibonacciRecursion(n-2)
}

func main() {
    for i := 0; i <= 9; i++ {
        fmt.Print(strconv.Itoa(FibonacciLoop(i)) + " ")
    }
    fmt.Println("")
    for i := 0; i <= 9; i++ {
        fmt.Print(strconv.Itoa(FibonacciRecursion(i)) + " ")
    }
    fmt.Println("")
}

Essentially we are creating a loop, continuously calling one of the Fibonacci number functions.

Conclusion

You just saw two ways to calculate the Fibonacci number with the Go programming language. There are plenty of other ways to calculate this number, some of which are even more efficient at runtime. For example you can use the matrix strategy which I didn’t discuss. If you want to see how to do this with JavaScript, check out my previous tutorial on the subject.

If you have your own way of calculating the Fibonacci number, share it in the comments. You’ll help a lot of people by sharing.

Nic Raboy

Nic Raboy

Nic Raboy is an advocate of modern web and mobile development technologies. He has experience in Java, JavaScript, Golang and a variety of frameworks such as Angular, NativeScript, and Apache Cordova. Nic writes about his development experiences related to making web and mobile development easier to understand.

Search

Follow Us

Subscribe

Subscribe to my newsletter for monthly tips and tricks on subjects such as mobile, web, and game development.

Subscribe on YouTube

Support This Site