The memoization eliminated duplicate calls to a function. A memoized implementation of Fibonacci code is as follows:

```
package complexity
import "fmt"
var mem map[int]int
func fibo(count int) int {
if count == 0 || count == 1 {
return count
}
if mem[count] != -1 {
return mem[count]
}
s := fibo(count-1) + fibo(count-2)
mem[count] = s
return s
}
func Fibo(count int) {
mem = make(map[int]int, count)
for i := 0; i <= count; i++ {
mem[i] = -1
}
fmt.Printf("fibonacci number for count=%+v is %v\n", count, fibo(count))
fmt.Printf("fibonacci map is %v\n", mem)
}
```

```
$ go run main.go
fibonacci number for count=4 is 3
fibonacci map is map[0:-1 1:-1 2:1 3:2 4:3]
```

Since each function in the recursion tree is processed at most once, the worst-case complexity of the above code becomes O(N).

Written with StackEdit.