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 [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
