February 01, 2004
Tackling C++ Tail Calls
February 04:
Listing 1: An implementation of Newton's square root algorithm.
/* 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);
}
Previous Page |
1
|
2
|
3
|
4
|
5
|
6
|
7
