Tail-recursive functions

Are tail-recursive functions supposed to be faster than their
non-tail-recursive counterparts?

e.g. in OCaml

let rec foo1 = function
| [] -> 0
| h::t -> h + (foo1 t)

vs.

let rec foo2 acc = function
| [] -> acc
| h::t -> foo2 (acc+h) t

On Tue, 8 Jul 2003, Shill wrote:

>Are tail-recursive functions supposed to be faster than their
>non-tail-recursive counterparts?
>
>e.g. in OCaml
>
>let rec foo1 = function
> | [] -> 0
> | h::t -> h + (foo1 t)
>
>vs.
>
>let rec foo2 acc = function
> | [] -> acc
> | h::t -> foo2 (acc+h) t

yep, they are. Tail-recursive functions can be optimised (most of the
time) to perform like impertive while-loops, because there is no context
left on the tail-call. Think of it like this. In your second example, the
foo2 function call could be implemented with a simple jmp instruction. In
the case of foo1, there is some book-keeping going on, because you have to
return to the call-site of foo1 to perform the (h + []) operation, and
this for every recursive call.

Regards,

Simon

On Tue, 8 Jul 2003 15:54:24 +0000 (UTC), Shill wrote:
> Are tail-recursive functions supposed to be faster than their
> non-tail-recursive counterparts?
>
> e.g. in OCaml
>
> let rec foo1 = function
> | [] -> 0
> | h::t -> h + (foo1 t)
>
> vs.
>
> let rec foo2 acc = function
> | [] -> acc
> | h::t -> foo2 (acc+h) t

Theoretically yes, especially for large date types that leave a stack
behind. Now the stack for this isn't so large, so it's probably not a
big deal, but when you modify data structures in a log(n) space fashion
in every step (for instance, inserting into a tree), the stack can get
pretty sizeable.

--
Arav bipsum | "The same person. No difference at all. Just a
Bicameral neep-neep | different sex." -Orlando (Orlando, 1992)
--------------------------------------------------------------------------
AIM: Sorrath sfogarty@students.uiuc.edu

In article <beepfg$hj6$1@wolfberry.srv.cs.cmu.edu>, Shill wrote:
> Are tail-recursive functions supposed to be faster than their
> non-tail-recursive counterparts?

Faster isn't the issue -- the real gain is that tail-recursive variants
will use constant stack space. The intuition here is that a tail call
requires no further processing to the returned result, so instead of saving
the current function's stack, you can just jump to the new code.

> let rec foo1 = function
> | [] -> 0
> | h::t -> h + (foo1 t)
>
> vs.
>
> let rec foo2 acc = function
> | [] -> acc
> | h::t -> foo2 (acc+h) t

For example, if `l' contains the numbers from 1 to 100,000, then:

# foo1 l;;
Stack overflow during evaluation (looping recursion?).
# foo2 0 l;;
- : int = 705082704

Ignoring the fact that the answer is wrong, due to integer overflow, the
only way to get a result *at all* was to use a tail-recursive
implementation.

William

On Tue, 8 Jul 2003 15:54:24 +0000 (UTC), Shill <nobody@example.com> wrote:
> Are tail-recursive functions supposed to be faster than their
> non-tail-recursive counterparts?
>
> e.g. in OCaml
>
> let rec foo1 = function
> | [] -> 0
> | h::t -> h + (foo1 t)
>
> vs.
>
> let rec foo2 acc = function
> | [] -> acc
> | h::t -> foo2 (acc+h) t
>

Yes. The reason is that when your recursive function call is in tail
position (informally: The last thing we do before returning), we can
jump instead of call. This essentially converts the recursive function
into a loop which is much faster than recursive calls. This is because
we can get around setup and teardown of function calls, stack push/pop
etc.

It is important to be able to recognize when a call is in tail
position. The most important thing I've seen is that if you have a
exception handler in your code it needs to be removed from the stack
after the function call and thus your function call wont be in tail
position.

--
Jesper

In article <beepfg$hj6$1@wolfberry.srv.cs.cmu.edu>,
Shill <nobody@example.com> wrote:
>Are tail-recursive functions supposed to be faster than their
>non-tail-recursive counterparts?

Formally, they're supposed to use less stack space. But in many
cases (such as the one you provided, I expect), this will result
in a faster computation because it produces more optimized
machine instructions.


--
Jeffrey M. Vinocur * jmv16@cornell.edu
http://www.people.cornell.edu/pages/jmv16/

Hello,

Shill <nobody@example.com> wrote in message news:<beepfg$hj6$1@wolfberry.srv.cs.cmu.edu>...
> Are tail-recursive functions supposed to be faster than their
> non-tail-recursive counterparts?

Tail-recursive functions are faster only if the compiler/interpreter
optimizes them into iteration. They definitely save on space, since
they are not using as much of the stack anymore and no state of the
calling functions is stored on the heap/stack. While the function may
not necessarily become faster, it probably will.

Check out:
http://www.wikipedia.org/wiki/Tail_recursion
http://www.purdue.edu/ITRCS/Short-Co...s/p_00550.html
http://www.owlnet.rice.edu/~comp210/...abs/lab09.html

Regards,

Sachin.