# 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:**

**Recursive Algorithm:**Exponential time complexity, simple to implement, but inefficient.**Iterative algorithm:**It has linear time complexity, is efficient, and is straightforward to comprehend.**Memoization algorithm:**It has linear time complexity, is efficient, and reduces recursive calls.**Dynamic Programming**: It has linear time complexity, is efficient, and utilizes a table to store results.**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