Tail recursion optimization improvement

Harvey J. Stein hjstein@bfr.co.il
Sun Jan 24 12:28:00 GMT 1999


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



More information about the Gcc mailing list