Tail recursion in C
I was trying to write a recursion function to find the factorial of a number.
int factorial(int input,int *answer)
{
if ( input ==0 )
{
return 0;
}
*answer = *answer * input;
factorial(input -1, answer);
}
What can you say about this feature? Is it tail recursive?
When doing tail-recursive functions (especially tail-recursive functions), it is often useful to have a helper function in addition to another function that has a friendlier interface. A friendly interface function does set less friendly function arguments.
static unsigned factorial_helper(unsigned input, unsigned acc) {
if (intput == 0) {
return acc;
}
return factorial_helper(input-1, acc * input);
}
unsigned factorial(int input) {
if (input < 0) {
do_something_bad();
}
return factorial_helper(input, 1);
}
By skipping the accumulator value, you avoid using pointers or any computation when returning from called functions, which makes the functions truly tail-recursive.
Here's a link with the definition: http://phoenix.goucher.edu/~kelliher/cs23/feb21.html
"A function is recursive with a tail if the last thing it does is call it recursively."
In the code you posted, the last thing the function does is make a recursive call to itself, so by this definition it is tail-recursive.