3 ways to implement Fibonacci series in Golang
9:17 PM
Since we working with Go, it’s good time to play a bit with Fibonacci numbers. First of all it’s great in case of learning a new programming language and second, we will try to analyze a bit recurrent function and write it’s short iterative implementation. As a bonus we will write function that return function that return int
But let’s starts from a theory. The definition of Fibonacci numbers state : Fn = Fn-1 + Fn-2 . The whole idea is find number by given its index.
- Recursive implementation
func fibbRecc(numIndex int) (numValue int){
if numIndex == 0 || numIndex == 1 {
return numIndex
}
return fibbRecc(numIndex - 2) + fibbRecc(numIndex -1)
}
Note: Simple well known recursive approach. The first problem is possibility of stack overflow. The second one it’s exponential time of execution. Third problem is repetitive calculations. For example if we will calculate value at index 4 -> f(3) + f(2), it mean that f(2) will be calculated twice. And if we will calculate value at index 5 -> f(4) + f(3), it mean that f(3) will be calculated 3 times. And so on..
So suitable solution for third problem may be using some data structure (slice for instance) to store data and avoid unnecessary calculations.
2. Iterative function.
There are a short mathematical representation developed by Binet based ongolden ratio:
func fibShortIterative(numIndex float64) (float64){
Phi := (1 + math.Sqrt(5)) / 2
phi := (1 - math.Sqrt(5)) / 2
return (math.Pow(Phi, numIndex) - math.Pow(phi, numIndex)) / math.Sqrt(5)
}
3. There is another way to write iterative Fibonacci function in Golang. Actually its a function that return function. And last one return int !
func fibIterFunc() func() int{
x:=0
y:=1
return func() int{
x,y = y,x+y
return x
}
}
Usage:
f:=fibIterFunc()
for i := 0; i < 10; i++ {
fmt.Print(f() )
}
Code (as always) can be found and downloaded from Github
1 comments.
Can you please explain the last third way. What does x, y = y, x +y . does. I was checking with this, an wondering what does ret do in here and above case
ReplyDelete