Tackling C++ Tail Calls
by Andreas Bauer and Markus Pizka


Example 1:

(a)
void foo (int x)           
{                          
  ...                      
  if (x == 0) bar1 ()      
  else        bar2 ();     
}                          
                             

(b)
float foo (float a, float b)          
{                                     
  ...                                 
  return bar (a/2);                   
}                                     
                                              

Example 1:

(a)
void foo (int x)
{
  ... 
  if (x == 0) bar1 ()
  else        bar2 ();
}

(b)
float foo (float a, float b)
{
    ...
    return bar (a/2);
}


Listing 1:

/* An implementation of Newton's square root algorithm.  */
/* Try compiling it with -foptimize-sibling-calls and take
   the square root of (say) 101, then try the same again,
   without the compiler optimization in place.  */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define ACCURACY 0.0000001

float newton       (int);
float find_root    (float, float);
int   close_enough (float, float);
int   calls;
int main (void)
{
  int input = 0;
  calls = 1;
  printf ("Enter a number: ");
  scanf  ("%d", &input);
  printf ("The square root of %d is approx. %f.\n", input, newton (input));
  printf ("Function calls required: %d\n", calls);
  return 0;
}
float newton (int input)
{
  calls++;
  /* This tail call cannot be optimized, because
     find_root requires a larger argument space
     than its caller:  */
  return find_root ((float) input, 1);
}
float find_root (float input, float guess)
{
  if (close_enough (input / guess, guess))
    return guess;
  else
    {
      calls++;
      /* This tail call can and will be optimized:  */
      return find_root (input, (guess + input / guess) / 2);
    }
}
int close_enough (float a, float b)
{
  return (fabs (a - b) < ACCURACY);
}





1