I was using recursion to calculate fibonacci. The main purpose is to learn memoization, but I failed.
My first attempt:
https://play.golang.org/p/BQ7Z9QxnS9
the cache didn’t work, and the newfib runs as slow as the old fib. Is there any way to make it work?
Then I tried to build a global cache, it improved the speed, but it returned wrong value when the number goes beyond 93.I really don’t know why.
https://play.golang.org/p/VCegqNgig1
Please help me.
Hi Steven! Thanks for your post 
For your second attempt, I believe that has to do more with integer overflow than with golang not supporting memoization.
Simple proof for you: int64 has a max value of 9223372036854775807
Type the following in google: 9223372036854775807 - (7540113804746346429+4660046610375530309)
That comes up as a negative number which tells you that starting with that fib number, int64 is not good enough anymore to represent your values. I hope that helps.
Thank you very much, Joel. It helps a lot. I thought int64 was far far bigger than 9223372036854775807 
Now problem 2 was solved,But I am still trying to make the first version work.
In the first playground link, main() runs newFib(i) only once for each i, which builds up the cache but does not yet take advantage of it. If you duplicate the loop, the second loop should be considerably faster than the first one.
Thanks,christophberger. English is not my native language, I am not sure whether I totally got you.
Could you help me by correcting my code, how can I duplicate the loop?
My first attempt: I calculate fib(i) from the start(f(1)) in each loop, the cache is for the recursion, not for the “for” the loop.if the cache doesn’t work in the recursion, how can I make it work by duplicating the loop?
My second attempt: the cache is used in boh the recursion and the for loop.
My second attempt is quicker, but I still think the first attempt should also work, I need help to change my first attempt to work.
Your problem is that the memoization doesn’t do what you expect. You memoize the top level fib, so once you’ve called newFib(n) once you’ll get a cached answer the next time, when calling newFib(). But inside the recursive fib you do not call the memoized version, so none of the recursive calls utilize the cache.
Thank you very much, Jakob. Problem solved!
how can I duplicate the loop?
I simply meant copying the loop and running it a second time.
Run this code outside the playground on your own computer, to see the result from memoizing:
(The playground is not reliable on timings, because it caches previous results and also tweaks time, hence any time operations may give inaccurate results. See this blog article, especially sections “Faking time” and “The front end”.)
Thanks for clarifying it, christoph, I get it now.
The problem of my first attempt is this line:
if cache[n] == 0 {
cache[n] = f(n)
}
As Jakob has pointed out, f is a recursive function. when it calls itself, it doesn’t use the cache. so my memoize function actually returns the old fib without changing anything. Is there any way to force the function f to use the cache?
Like javascript . f.apply(this,n). I spent my whole afternoon, and had no luck.
You can’t change the calls inside the existing fib function, unless the function itself is prepared for it by taking a function or interface parameter. In Javascript you may be able to monkey patch it somehow, but in Go you cannot1. You need to apply the memoization inside the function directly. Taking your generator function as an example,
func newMemoizedFib() func(int) int {
cache := make(map[int]int)
var fn func(int) int
fn = func(n int) int {
if n == 1 || n == 2 {
return 1
}
if _, ok := cache[n]; !ok {
cache[n] = fn(n-1) + fn(n-2)
}
return cache[n]
}
return fn
}
In production I’d probably want a type cachedFib struct { ... } instead and have the function be a method on that, to avoid the closure magic. Or just a table of precomputed values if you know the range you’re interested in…
1) … within the constraints of the non-unsafe part of the language, which we should stick to in this exercise.
Thanks again Jakob. I am trying to create a func memoize. it takes in a recursive func without cache, and returns a new recursive func with cache. If this would be possible,the memoize function could have been reused. There is no way to achieve this in Go?
There is no way to modify a compiled Go program from within itself, no, which is what you would need to do. Function calls are not “looked up” at run time like they may be in Javascript; they may even be inlined and thus not even remain as function calls in the compiled code.
Got it, Jakob.
I’ll recheck this problem when I have a deeper understanding of Go.
Today I met a similar problem again, This time it is not that hard. and I recall this problem too, Here is the code I rewrote:
https://play.golang.org/p/H49N6tL4HX7
I think channel is better for this kind of task, but yes, Go can do memoization!
A simple solution for it:
func main() {
var memo = make(map[int]int)
fmt.Print(fib(50, memo)) //12586269025
}
func fib(n int, memo map[int]int) int {
if n <= 2 {
return 1
}
if _, ok := memo[n]; !ok {
memo[n] = fib(n-1, memo) + fib(n-2, memo)
}
return memo[n]
}