Clever Geek Handbook

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?

+2


source to share


2 answers


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.

+6


source


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.

+4


source






More articles:


All Articles