People love using Fibonacci as an example of recursion but the closed form solution is great

fib.go

package main

import (
	"fmt"
	"math"
)

const Psi = -1.0 / math.Phi

var Sqrt5 = math.Pow(5.0, 0.5)

func Fibr(n int) int {
	if n == 0 {
		return 0
	}
	if n == 1 {
		return 1
	}
	return Fibr(n-1) + Fibr(n-2)
}

func Fibl(n int) int {
	a := 0
	b := 1
	for i := 0; i < n; i++ {
		a, b = b, a+b
	}
	return a
}

func Fibc(n int) int {
	fn := float64(n)
	return int(math.Round((math.Pow(math.Phi, fn) - math.Pow(Psi, fn)) / Sqrt5))
}

func main() {
	fmt.Println("Fibonacci methods")
	fmt.Printf("Recursive: %d\n", Fibr(22))
	fmt.Printf("Linear: %d\n", Fibl(22))
	fmt.Printf("Closed: %d\n", Fibc(22))
}

fib_test.go

package main

import "testing"

const N = 82

// at N=22, 114k ns/op
// at N=42, 1.9 s/op
// at N=82, times out after 11 minutes
// func BenchmarkFibr(b *testing.B) {
// 	for i := 0; i < b.N; i++ {
// 		Fibr(N)
// 	}
// }

// O(n), 10–56 ns/op
func BenchmarkFibl(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Fibl(N)
	}
}

// O(1) ~93 ns/op regardless of N
func BenchmarkFibc(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Fibc(N)
	}
}