summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorCasey Robinson <casey@rampantmonkey.com>2015-06-15 13:05:17 -0400
committerCasey Robinson <casey@rampantmonkey.com>2015-06-15 13:54:40 -0400
commit03477a4796c7f71cc4e025f2942431beea1549e4 (patch)
tree4908ce4bc502c2a4f8061c6946664aa3fdd092bd
parent0d4d6ac4a35d625df15f4bcd51a445d83e6c5f5f (diff)
downloadfibgo-03477a4796c7f71cc4e025f2942431beea1549e4.tar.gz
fibgo-03477a4796c7f71cc4e025f2942431beea1549e4.tar.bz2
fibgo-03477a4796c7f71cc4e025f2942431beea1549e4.zip
memoized implementation
-rw-r--r--main.go21
1 files changed, 21 insertions, 0 deletions
diff --git a/main.go b/main.go
index a1a5ffc..7b909ea 100644
--- a/main.go
+++ b/main.go
@@ -28,6 +28,10 @@ func main() {
fallthrough
case "recursive":
fmt.Printf("fib(%d) = %d\n", n, recursive(n))
+ case "m":
+ fallthrough
+ case "memoize":
+ fmt.Printf("fib(%d) = %d\n", n, memoize(n))
default:
fmt.Printf("Unknown/unimplemented method %s\n", *method)
}
@@ -53,3 +57,20 @@ func recursive(n int) int {
return recursive(n-1) + recursive(n-2)
}
}
+
+func memoize(n int) int {
+ cache := make(map[int] int)
+ cache[0] = 0
+ cache[1] = 1
+ return memoizeInternal(n, cache)
+}
+
+func memoizeInternal(n int, cache map[int] int) int {
+ if res, ok := cache[n]; ok {
+ return res
+ }
+
+ res := memoizeInternal(n-1, cache) + memoizeInternal(n-2, cache)
+ cache[n] = res
+ return res
+}