On Mon, Jul 23, 2012 at 3:14 PM, Mimmo Cosenza <mimmo.cose...@gmail.com> wrote: > hi Merek and thanks for the link. But it does not answer my question. > I was looking for a demonstration of the reducibility of (not tail) > recursion to tail recursion. Or there is a demonstration of that, or nobody > could say that a (not tail) recursion definition is always reducible to a > tail recursion definition.
Longer explanation: Two versions of the proof. - Every program can be translated to a Turing machine. A turing machine interpreter can easily be written with a while loop. Any while loop is a tail recursion. - A more interesting proof requires to understand Continuation Passing Style (CPS) transformation: http://en.wikipedia.org/wiki/Continuation-passing_style In a CPS program, every call is a tail call. You can systematically transform any program to a CPS one. In practice, it is often sufficient to mimic the data stack, by adding an argument containing the stack. -- 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
