fib.go

package main

import (
	"fmt"
)

func fib(n int) int {
	fibs := make(map[int]int, n+1)
	fibs[0] = 0
	fibs[1] = 1

	var memFib func(n int, fibs map[int]int) int
	memFib = func(n int, fibs map[int]int) int {
		switch {
		case n < 0:
			panic("Don’t feed fib a negative number!")
		default:
			if f, ok := fibs[n]; ok {
				return f
			}
			f := memFib(n-1, fibs) + memFib(n-2, fibs)
			fibs[n] = f
			return f
		}
	}

	result := memFib(n, fibs)
	return result
}

func fib2(n int) int {
	switch {
	case n < 0:
		panic("Don’t feed fib a negative number!")
	case n <= 1:
		return n
	default:
		return fib2(n-1) + fib2(n-2)
	}
}

func fib3(n int) int {
	if n <= 1 {
		return n
	}

	n2, n1 := 0, 1

	for i := 2; i < n; i++ {
		n2, n1 = n1, n1+n2
	}

	return n2 + n1
}

func main() {
	fmt.Printf("fib(50) = %d\n", fib(50))
}

fib_test.go

package main

import (
	"testing"
)

func BenchmarkFib(b *testing.B) {
	for i := 0; i < b.N; i++ {
		fib(50)
	}
}

func BenchmarkFib2(b *testing.B) {
 	for i := 0; i < b.N; i++ {
 		fib2(50)
 	}
}

func BenchmarkFib3(b *testing.B) {
	for i := 0; i < b.N; i++ {
		fib3(50)
	}
}

$ GO111MODULE=off go test -benchmem -bench .
goos: linux
goarch: amd64
cpu: Intel(R) Core(TM) i7-9850H CPU @ 2.60GHz
BenchmarkFib-12           351270              3429 ns/op            1468 B/op          6 allocs/op
BenchmarkFib2-12               1        64827585488 ns/op              0 B/op          0 allocs/op
BenchmarkFib3-12        91441062                12.34 ns/op            0 B/op          0 allocs/op
PASS
ok      _/tmp/fib       67.213s