With memoize there are additional calls (the new function and apply) per
recursion, so I guess that will produce the stack overflow to happen
sooner. You can use memoization once you remove the stack issue with
iteration:
(defn gauss-iter [n]
(letfn [(f [n acc]
(if (< n 1)
acc
(recur (dec n) (+ acc (dec n)))))]
(f n n)))
(def gauss-memo (memoize gauss-iter))
On Sunday, September 22, 2013 8:19:23 AM UTC-7, John Lawrence Aspden wrote:
>
> Hi Guys,
>
> I'm trying to memoize a fairly complicated double recursion, and it's
> blowing stack after not terribly many calls.
>
> I've reduced the problem to a simple test case, summing from 1 to n :
>
> user=> (clojure-version)
> "1.5.1"
> user=> (def gauss-recurse (fn [n] (if (< n 1) 0 (+ n (gauss-recurse (dec
> n))))))
> #'user/gauss-recurse
> user=> (gauss-recurse 3500)
> 6126750
> user=> (def gauss-memoized (memoize (fn [n] (if (< n 1) 0 (+ n
> (gauss-memoized (dec n)))))))
> #'user/gauss-memoized
> user=> (gauss-memoized 160)
>
> StackOverflowError clojure.lang.RT.boundedLength (RT.java:1654)
> user=>
>
>
> Does anyone know why this would happen? Do I just have to give up on
> memoization and find another way to do dynamic programming?
>
> Cheers, John.
>
--
--
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 unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
For more options, visit https://groups.google.com/groups/opt_out.
