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