patterngoMinor
Four algorithms to find the Nth Fibonacci number
Viewed 0 times
nththenumberfibonaccifouralgorithmsfind
Problem
I'm implementing some basic algorithms in Go as an introductory exercise. Here are four different algorithms to find the Nth Fibonacci number.
I'm looking for general feedback, but I'm specially interested in the Go idiom. Are the algorithms implemented idiomatically? If not, how can I correctly use the Go idiom to implement them?
Any other feedback you can think of is also welcome.
I'm looking for general feedback, but I'm specially interested in the Go idiom. Are the algorithms implemented idiomatically? If not, how can I correctly use the Go idiom to implement them?
Any other feedback you can think of is also welcome.
// Algorithms to calculate the nth fibonacci number
package main
import (
"fmt"
"math"
)
func main() {
for i := 0; i <= 20; i++ {
fmt.Println(fibonacci(i))
fmt.Println(fibonacciRecursive(i))
fmt.Println(fibonacciTail(i))
fmt.Println(fibonacciBinet(i))
println()
}
}
// Iterative
func fibonacci(n int) int {
current, prev := 0, 1
for i := 0; i < n; i++ {
current, prev = current + prev, current
}
return current
}
// Recursive
func fibonacciRecursive(n int) int {
if n < 2 {
return n
}
return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2)
}
// Tail recursion
func fibonacciTail(n int) int {
return tailHelper(n, 1, 0)
}
func tailHelper(term, val, prev int) int {
if term == 0 {
return prev
}
if term == 1 {
return val
}
return tailHelper(term - 1, val + prev, val)
}
// Analytic (Binet's formula)
func fibonacciBinet(num int) int {
var n float64 = float64(num);
return int( ((math.Pow(((1 + math.Sqrt(5)) / 2), n) - math.Pow(1 - ((1 + math.Sqrt(5)) / 2), n)) / math.Sqrt(5)) + 0.5 )
}Solution
For
In
However, none of these four solutions is particularly idiomatic for Go. The most expressive way to write a Fibonacci sequence in Go is as an iterator, such as this one.
tailHelper(), the term == 1 case is superfluous and should be eliminated.In
fibonacciBinet(), the quantity \$\frac{1 + \sqrt{5}}{2}\$ appears twice. Since that quantity is known as the Golden Ratio, I would define an intermediate valuevar phi = (1 + math.Sqrt(5)) / 2;However, none of these four solutions is particularly idiomatic for Go. The most expressive way to write a Fibonacci sequence in Go is as an iterator, such as this one.
Code Snippets
var phi = (1 + math.Sqrt(5)) / 2;Context
StackExchange Code Review Q#48020, answer score: 4
Revisions (0)
No revisions yet.