Go Fibonacci with Memoization

fib.go

package main

import "log"

func main() {
	assert(0, fib(0))
	assert(1, fib(1))
	assert(1, fib(2))
	assert(2, fib(3))
	assert(3, fib(4))
	assert(5, fib(5))
	assert(8, fib(6))
	assert(13, fib(7))
	assert(21, fib(8))
}

func fib(n int) int {
	cache := make(map[int]int)
	return fibR(cache, n)
}

func fibR(cache map[int]int, n int) int {
	if n <= 1 {
		return n
	}

	if val, hit := cache[n]; hit {
		return val
	}
	cache[n] = fibR(cache, n-1) + fibR(cache, n-2)

	return cache[n]
}

func assert(expected, actual interface{}) {
	if expected != actual {
		log.Panicf("%s != %s", expected, actual)
	}
}