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.
A 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