2) is false; consider for example a function traversing a binary tree. You need some sort of "breadcrumb" trail to backtrack after visiting left children. This will always be of the form of some sort of stack or queue, whether explicit or implicit (implied by non-tail recursion).
1) is also questionable. Tail recursive functions must write over their own arguments on the stack, which often involves extra move operations just before the tail call, as they may require the original argument values up until the last new argument values are computed. Furthermore, accumulator introduction (the process by which non-TC functions are made to be TC) involves reversing the order of the arguments to the function which is called after the tail call. Concrete example: a tail-recursive map must append results to the right of a list rather than the left. This can have performance implications, as it does in this example (append from the left is O(1), append from the right is O(n)). The Mercury language does what you suggest, and even in cases where argument order is irrelevant (e.g. summing a list) my own tests have shown slight speed *losses* due to the stack shuffling described above. The non-tail recursive version of a function performs fewer memory accesses than the tail-recursive version since it need not write arguments to a temporary place before the recursive call. To sum up, the only benefit of tail recursion is to limit stack growth and memory usage. Hope this helps. - Chris On May 13, 2011 6:51 AM, "OGrandeDiEnne" <[email protected]> wrote: Hello people, considering that 1) tail recursion is faster than non-tail-recursion (because it does not have put a call in the stack for each iteration) 2) it is possible to convert any non-tail-recursive function into a tail-recursive function Is worth it to rewrite functions in tail-recursive ? Is Ocaml compiler already converting my non-tail recursive functions into tail version, when compiling? Since this conversion can be made by a compiler, why bother to rewrite ? Tail-recursive code can be harder to reason about. -- You received this message because you are subscribed to the Google Groups "ocaml-developer" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/ocaml-developer?hl=en For other OCaml forums, see http://caml.inria.fr/resources/forums.en.html -- You received this message because you are subscribed to the Google Groups "ocaml-developer" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/ocaml-developer?hl=en For other OCaml forums, see http://caml.inria.fr/resources/forums.en.html
