I just saw this in another thread. Try this version instead:
(defn f [n]
(println "f called with" n)
(if (zero? n)
0
(min (#'f (dec n))
(#'f (dec n)))))
What's happening is that inside the body of f, the "f" is a symbol
whose contents point to the anonymous function being defined, so when
you recurse, you're recursing to the original anonymous function, not
the current value of "f". By using the #' macro in front of the f,
you're saying "Use the current value of the symbol f to calculate the
following value."
On Mon, Mar 28, 2011 at 8:47 PM, Benny Tsai <[email protected]> wrote:
> I was playing with "memoize" when I ran into some puzzling behavior. A test
> case:
>
> (defn f [n]
> (println "f called with" n)
> (if (zero? n)
> 0
> (min (f (dec n))
> (f (dec n)))))
> (def f (memoize f))
>
> *The usage of "def" to rebind a function to its memoized version is taken
> from Programming Clojure.
>
> The output when I call f with 2:
>
> user=> (f 2)
> f called with 2
> f called with 1
> f called with 0
> f called with 0
> f called with 1
> f called with 0
> f called with 0
> 0
>
> Since f is memoized, my expectation was that I would see "f called with 2",
> "f called with 1", "f called with 0" each printed just once. Instead, it's
> as though I didn't memoize f at all. I know I did, because if I call f with
> 2 again, I get 0 back right away.
>
> user=> (f 2)
> 0
> This leads me to the second issue: Having evaluated (f 2), I assumed that
> the results for (f 2), (f 1), and (f 0) are all now available for immediate
> retrieval. If I call (f 3), I thought I would only see "f called with 3"
> printed and then the result. Instead, this is what I saw:
>
> user=> (f 3)
> f called with 3
> f called with 2
> f called with 1
> f called with 0
> f called with 0
> f called with 1
> f called with 0
> f called with 0
> f called with 2
> f called with 1
> f called with 0
> f called with 0
> f called with 1
> f called with 0
> f called with 0
> 0
>
> It's as though the recursive calls go to the unmemoized version of the
> function instead of the memoized one.
>
> I did find a way to get the expected behavior:
>
> (def g
> (memoize
> (fn [n]
> (println "g called with" n)
> (if (zero? n)
> 0
> (min (g (dec n))
> (g (dec n)))))))
>
> user=> (g 2)
> g called with 2
> g called with 1
> g called with 0
> 0
> user=> (g 3)
> g called with 3
> 0
>
> Up until now, I assumed the first formulation would work with recursive
> functions as well. Was that incorrect? Is something like the second
> formulation the only way to memoize recursive functions?
>
> --
> You received this message because you are subscribed to the Google
> Groups "Clojure" group.
> To post to this group, send email to [email protected]
> Note that posts from new members are moderated - please be patient with your
> first post.
> To unsubscribe from this group, send email to
> [email protected]
> For more options, visit this group at
> http://groups.google.com/group/clojure?hl=en
--
You received this message because you are subscribed to the Google
Groups "Clojure" group.
To post to this group, send email to [email protected]
Note that posts from new members are moderated - please be patient with your
first post.
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/clojure?hl=en
