recursion may be faster

main.go

package main

import (
	"fmt"
	"time"
)

func main() {
	startTime := time.Now()
	fmt.Println("Run -> Fib")
	res := wrapCachedFib(1000)
	fmt.Println(res)
	endTime := time.Now()
	fmt.Printf("Duration: %dmicros\n", endTime.UnixMicro()-startTime.UnixMicro())
	fmt.Println("------------------------------------------------------------")
	sTime := time.Now()
	fmt.Println("Run -> Fib")
	r := classicFib(50)
	fmt.Println(r)
	eTime := time.Now()
	fmt.Printf("Duration: %dmicros\n", eTime.UnixMicro()-sTime.UnixMicro())
}

func classicFib(n uint64) uint64 {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	a := classicFib(n - 2)
	b := classicFib(n - 1)
	return a + b
}

func cachedFib(n uint64, cache []uint64) uint64 {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	if cache[n] == 0 {
		a := cachedFib(n-2, cache)
		b := cachedFib(n-1, cache)
		cache[n] = a + b
	}
	return cache[n]
}

func wrapCachedFib(n uint64) uint64 {
	cache := make([]uint64, n+1)
	return cachedFib(n, cache)
}

Result output:

Run -> wrapCachedFib
817770325994397771
Duration: 155micros
--------------------------------------
Run -> classicFib
12586269025
Duration: 69302681micros

WOW!