[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)
      }
   }
}

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s