Tail/Non tail recursion

Richard A. O'Keefe ok@REDACTED
Mon Sep 1 04:28:58 CEST 2003


"Peter Lund" <peter@REDACTED> wrote:

	> Yes, this is what I meant even if I failed to write that into plain
	> language. I have a faint memory from several years ago, that there
	> was a compiler optimization for exactly this type of non-recursive
	> calls, that in fact made it behave like a tail-recursive function.
	> Maybe someone that KNOWS can tell us if anything like this exist.

To so that we're all signing off the same song-sheet,
the question is whether the function

    f([H|T]) -> [X+1 | f(X)];
    f([])    -> [].

can be tail recursive.

The answer of course is that it could be, quite easily.
The Prolog equivalent

    f([H1|T1], [H2|T2]) :-
        H2 is H1 + 1,
        f(T1, T2).
    f([], []).

is certainly tail recursive.  A couple of years ago I proposed to Kostas
Sagonis that HiPE should also do this, but given the need for HiPE to work
with BEAM, I don't know if that was ever found to be practical.  Basically,
you have to pass an additional argument to every function, the address
where the result should be stored.  This ties up a register that you might
have something better to do with, especially on an x86.




More information about the erlang-questions mailing list