Thanks so much Alan. Very clear. Mimmo On Tuesday, July 24, 2012 8:19:00 AM UTC+2, Alan Malloy wrote: > > I don't see how the definition of primitive-recursive is relevant to this. > You can transform primitive recursion to tail recursion if you allocate a > "stack" of your own on the heap, and don't mind that it might grow without > bound. Or you can transform to continuation-passing or trampolines > (fundamentally the same, as I understand it); that approach is > tail-recursive but can lead to functions with very large closures. > > For example, here is a definition of the Ackermann function using only > tail calls: > > (defn ack > ([m n] (ack m n identity)) > ([m n cont] > (cond (zero? m) (cont (inc n)) > (zero? n) (ack (dec m) 1 cont) > :else (ack m (dec n) #(ack (dec m) % cont))))) > > And here's the same thing transformed to use only JVM-friendly > self-tail-recursion: > > (defn ack [m n] > (loop [m m, n n, stack ()] > (cond (zero? m) (if (empty? stack) > (inc n) > (recur (peek stack), (inc n), (pop stack))) > (zero? n) (recur (dec m) 1 stack) > :else (recur m (dec n) (conj stack (dec m)))))) > > There is nothing magic about the stack; if you're wiling to manage the > (infinite) memory yourself, you can compute any computable function with > just tail calls. > > On Monday, July 23, 2012 10:18:35 PM UTC-7, Christian Mueller wrote: >> >> No, not any recursion can be expressed as a tail recursion. One example: >> the Ackermann function (http://en.wikipedia.org/wiki/Ackermann_function) >> >> On Saturday, July 21, 2012 11:15:33 AM UTC+2, Mimmo Cosenza wrote: >>> >>> Hi, >>> a very basic question. Any "not tail recursion" code can be reduced to >>> tail recursion code? >>> >>> Thanks >>> >>> Mimmo >>> >>
-- You received this message because you are subscribed to the Google Groups "Clojure" group. To post to this group, send email to clojure@googlegroups.com Note that posts from new members are moderated - please be patient with your first post. To unsubscribe from this group, send email to clojure+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/clojure?hl=en
