[Algorithms] – The classic Fibonacci with and without recursion in golang

What is Fibonacci?

See more here

What is Fibonacci formula?

Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

Fibonacci code solution

Following the code implementation.

package algoTest

// a(1) =1, a(2) = 1, a(n) = a(n-1) + a(n-2)
// Closer solution
func Fibonacci() func() int {
   first := true
   a, b := 0, 1
   return func() int {
      if first {
         first = false
         return 0
      }
      a, b = b, a + b
      return a
   }
}

Following the code test for it.

package algoTest

import (
   "fmt"
   "github.com/stretchr/testify/assert"
   "testing"
)

func TestFibonacci(t *testing.T) {
   // 0,1,2,3,5,8,13,21
   f:= Fibonacci()
   for i := 0; i < 10; i++ {
      res := f()
      fmt.Println(res)
      switch i {
      case 0:
         assert.Equal(t, 0, res)
      case 1:
         assert.Equal(t, 1, res)
      case 2:
         assert.Equal(t, 1, res)
      case 3:
         assert.Equal(t, 2, res)
      case 4:
         assert.Equal(t, 3, res)
      case 5:
         assert.Equal(t, 5, res)
      case 6:
         assert.Equal(t, 8, res)
      case 7:
         assert.Equal(t, 13, res)
      case 8:
         assert.Equal(t, 21, res)
      }
   }

   assert.NotNil(t, f)
}

Fibonacci with recursion solution

Following the code implementation.

package algoTest

func FiboRec(n int) int {

   if n == 0 || n == 1{
      return n
   }
   return FiboRec(n - 2) + FiboRec(n - 1)

}

Following the code test for it.

package algoTest

import (
   "fmt"
   "testing"
   "github.com/stretchr/testify/assert"
)

func TestFiboRec(t *testing.T) {
   // 0,1,2,3,5,8,13,21
   for i := 0; i < 10; i++ {
      res := FiboRec(i)
      fmt.Println(res)
      switch i {
      case 0:
         assert.Equal(t, 0, res)
      case 1:
         assert.Equal(t, 1, res)
      case 2:
         assert.Equal(t, 1, res)
      case 3:
         assert.Equal(t, 2, res)
      case 4:
         assert.Equal(t, 3, res)
      case 5:
         assert.Equal(t, 5, res)
      case 6:
         assert.Equal(t, 8, res)
      case 7:
         assert.Equal(t, 13, res)
      case 8:
         assert.Equal(t, 21, res)
      }
   }
}