// 12. hét – Fibonacci: naiv rekurzió, memoizáció, iteráció
// Futtatás: go run ./h12/fibonacci
package main

import (
	"fmt"
	"time"
)

var calls int

func fib(n int) int {
	calls++
	if n < 2 {
		return n
	}
	return fib(n-1) + fib(n-2)
}

func fibMemo(n int, memo map[int]int) int {
	calls++
	if n < 2 {
		return n
	}
	if v, ok := memo[n]; ok {
		return v
	}
	r := fibMemo(n-1, memo) + fibMemo(n-2, memo)
	memo[n] = r
	return r
}

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

func main() {
	fmt.Println(" n   fib(n)        naiv hívások   memo hívások   idő (naiv)")
	for _, n := range []int{5, 10, 20, 30, 40} {
		calls = 0
		t0 := time.Now()
		r := fib(n)
		t := time.Since(t0)
		naive := calls
		calls = 0
		fibMemo(n, map[int]int{})
		fmt.Printf("%2d %10d %15d %13d %10.1f ms\n", n, r, naive, calls, float64(t.Microseconds())/1000)
	}
	fmt.Println("fibIter(90) =", fibIter(90))
}