package main

import "fmt"

func memoize(fn func(int) int) func(int) int {
    var memo = make(map[int]int)
    return func(n int) int {
        if _, ok := memo[n]; !ok {
            memo[n] = fn(n)
        }        
        return memo[n]
    }    
}

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

func main() {
    fib := memoize(fib)
    for i := 1; i < 11; i++ {
        fmt.Println(fib(i))
    }
}