This is the mail archive of the
gcc@gcc.gnu.org
mailing list for the GCC project.
Re: Tail recursion optimization improvement
- To: law at cygnus dot com
- Subject: Re: Tail recursion optimization improvement
- From: hjstein at bfr dot co dot il (Harvey J. Stein)
- Date: 24 Jan 1999 22:28:03 +0200
- CC: egcs at cygnus dot com
- CC: hjstein at bfr dot co dot il
- References: <24282.917193985@chunks.cygnus.com>
Jeffrey A Law <law@cygnus.com> writes:
> The fundamental problem with the existing tail recursion
> optimizations is that it only works when the tail recursion appears
> in a return statement.
>
> ie
>
> foo (a)
> {
> if (a == 1)
> return 1;
> else
> return (a * foo (a-1));
> }
>
> Will be recognized as tail recursion.
How is this a tail recursion? It has to call foo & then multiply the
return value by a before it can return a value. This is the standard
example of a factorial fcn which isn't tail recursive, and can be
converted to a tail recursive version as follows:
foo(a)
{
foo_helper(a, 1);
}
foo_helper(a, p)
{
if (a == 1)
return p;
else
return (foo_helper(a-1, a*p));
}
--
Harvey J. Stein
BFM Financial Research
hjstein@bfr.co.il