Fibonacci Golang

Fibonacci Numbers Sequence

The mathematical number series is initiated with its initial two numbers such as 0 and 1. Each subsequent number in the mathematical sequence is the sum of the two previous numbers. This mathematical series is known as the Fibonacci numbers series.

The Pattern

1.Begin with 0 and 1: These are the first two numbers of the series.
2.Add the Last Two Numbers: To find the next number in the series, you add the last two numbers together.

      • For example, 0 + 1 = 1
      • Then, 1 + 1 = 2
      • Next, 1 + 2 = 3
    •     And 2 + 3 = 5

Key Points

  • Each number in the sequence is the sum of the two numbers before it.
  • The sequence starts with 0 and 1.
  • It grows quickly as each number is added to the previous one.

Recursive algorithm

This Golang program computes and displays the first 5 Fibonacci numbers using recursion:

package main

import "fmt"

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

func main() {
   n := 5
   fmt.Println("Fibonacci Numbers:")
   for i := 0; i < n; i++ {
       fmt.Println(fibonacci(i))
   }
}

The recursive approach follows the formula F(n) = F(n-1) + F(n-2). This method has exponential time complexity due to redundant calculations. For more details, visit my GitHub repository.

Iterative algorithm 

package main

import "fmt"

func fibonacciCalculator(n int) int {
   if n <= 1 {
       return n
   }
   a, b := 0, 1
   for i := 2; i <= n; i++ {
       a, b = b, a+b
   }
   return b
}

func main() {
   for i := 0; i < 5; i++ {
       fmt.Println(fibonacciCalculator(i))
   }
}

The algorithm uses a loop from 2 to n, updating values to get the next Fibonacci number. It’s efficient with O(n) complexity. Check my GitHub for the code.

Dynamic Programming 

package main

import "fmt"

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

func main() {
   for i := 0; i < 5; i++ {
       fmt.Println(fibonacciDynamic(i))
   }
}

The algorithm operates in O(n) time complexity and uses O(n) space. Visit my GitHub for the code implementation of the Fibonacci sequence in Golang.

Memoization Algorithm 

package main

import "fmt"

var memo = map[int]int{}

func fibonacciMemoized(n int) int {
   if v, ok := memo[n]; ok {
       return v
   }
   if n <= 1 {
       return n
   }
   result := fibonacciMemoized(n-1) + fibonacciMemoized(n-2)
   memo[n] = result
   return result
}

func main() {
   for i := 0; i < 5; i++ {
       fmt.Println(fibonacciMemoized(i))
   }
}

The algorithm optimizes with memoization, caching results for repeated inputs, reducing recursive calls. Time complexity is O(n). Check my GitHub repository for the code.

Closed-Form Expression (Binet's Formula) 

package main

import (
   "fmt"
   "math"
)

func fibonacciBinet(n int) int {
   phi := (1 + math.Sqrt(5)) / 2
   psi := (1 - math.Sqrt(5)) / 2
   return int((math.Pow(phi, float64(n)) - math.Pow(psi, float64(n))) / math.Sqrt(5))
}

func main() {
   for i := 0; i < 5; i++ {
       fmt.Println(fibonacciBinet(i))
   }
}

This algorithm utilizes Binet’s formula, offering constant time complexity O(1). However, it may face numerical instability for large n values. Visit my GitHub repository for the code.

Summary

Algorithms:

  1. Recursive Algorithm: Exponential time complexity, simple to implement, but inefficient.
  2. Iterative algorithm: It has linear time complexity, is efficient, and is straightforward to comprehend.
  3. Memoization algorithm: It has linear time complexity, is efficient, and reduces recursive calls. 
  4. Dynamic Programming: It has linear time complexity, is efficient, and utilizes a table to store results.
  5. Closed-Form Expression (Binet’s Formula): It has constant time complexity, and is efficient, but may face numerical instability.

Main Points:

  • The recursive algorithm is simple but inefficient.
  • Iterative and dynamic programming algorithms are easy to understand and efficient.
  • The memoization algorithm is efficient and reduces the number of recursive calls.
  • A closed-form expression is efficient but could potentially have numerical instability problems.

Choose the right algorithm based on the following:

  • Performance requirements
  • Code simplicity and readability
  • Numerical stability concerns