[erlang-questions] tail recursion question

Richard O'Keefe <>
Wed Apr 28 03:58:52 CEST 2010


The issue is whether a function

	f(...) ->
	    ...
	    all cases have
		f(...)
	    g(...).

is tail recursive.  More generally, it's whether calls to
any function that is known not to terminate can be treated
as tail calls.

The quick answer is 'who cares? almost all functions should
be *able* to terminate'.  This is not to say that almost all
functions should *have* to terminate, just that there should
be some possibly rare situation where they can be shut down.

The longer answer is that if a compiler can prove that a
function call cannot terminate, then it doesn't have to arrange
for anything to happen when that call returns, and it _may_
compile that call as a tail call.  However, it would be far
more useful for the compiler to report a "dead code" warning:
the existence of the call to g(...) is strong evidence that
some programmer at some time in the past thought the calls to
f(...) WOULD return, and if the compiler has proven that they
don't, that's evidence of at least a quality issue.  A human
programmer can remove the call to g(...), or, more plausibly,
figure out what the base case of f should be and ensure that
f *can* return.

An Erlang compiler is not required to check termination or
non-termination, and so is not *required* to compile such
weird code as tail recursive.



More information about the erlang-questions mailing list