package main

import "fmt"

func main() {
	val := 4
	var fib int = fib(val)
	fmt.Printf("fib(%v) = %v\n", val, fib)

	fib2 := fib2(val)
	fmt.Printf("fib(%v) = %v\n", val, fib2)
}

// recursive implementation
func fib(n int) int {
	if n == 0 || n == 1 {
		return n
	}
	return fib(n-1) + fib(n-2)
}

// iterative implementation
func fib2(n int) int {
	if n == 0 || n == 1 {
		return n
	}
	a := 0
	b := 1
	c := 0
	for i := 2; i <= n; i++ {
		c = a + b
		a = b
		b = c
	}
	return c
}