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.

The Rule is xn = xn−1 + xn−2

where:

  • xn is term number “n”
  • xn−1 is the previous term (n−1)
  • xn−2 is the term before that (n−2)

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

recursive function is a function that calls itself in order to break down complex input into simpler ones.

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

Try this in Go Playground (restrict to 2 digit number only, otherwise timeout by the Go Playground server.

https://play.golang.org/p/QfhbCWN9KwE