Fibonacci sequence

fib.go

package main

import (
	"flag"
	"fmt"
)

// Time: O(2^n)
// Space: O(n)
func FibRecursive(n uint64) uint64 {
	if n <= 1 {
		return n
	}

	return FibRecursive(n-1) + FibRecursive(n-2)
}

// Time: O(n)
// Space: O(1)
func FibIterative(n uint64) uint64 {
	var fib uint64
	var i uint64
	var x, y uint64 = 0, 1

	for i = 0; i < n; i++ {
		x = y
		y = fib
		fib = x + y
	}

	return fib
}

func main() {
	method := flag.String("method", "iterative", "Either recursive or iterative")
	num := flag.Uint64("number", 10, "nth fibonacci number")

	flag.Parse()

	if *method == "recursive" {
		fmt.Println(FibRecursive(*num))
	} else if *method == "iterative" {
		fmt.Println(FibIterative(*num))
	}
}

fib_test.go

package main

import "testing"

func BenchmarkFibRecursive(b *testing.B) {
	for n := 0; n < b.N; n++ {
		FibRecursive(30)
	}
}

func BenchmarkFibIterative(b *testing.B) {
	for n := 0; n < b.N; n++ {
		FibIterative(30)
	}
}