Convert recursive function to tail recursive

Question

I have the following recursive function to count all the nodes having value 20, in a circular doubly linked list. I need to convert this to tail recursive function to prevent safety issues. Please help me with the same. Thanks

int count(node *start)
{
    return count_helper(start, start);
}
int count_helper(node *current, node *start)
{
    int c;
    c = 0;
    if(current == NULL)
        return 0;
    if((current->roll_no) == 20)
        c = 1;
    if(current->next == start) return c;
    return (c + count_helper(current->next, start));
}

unless this is homework, there's no reason for recursion here. — Pete Wilson, Oct 30 '11 at 14:01
possible duplicate of [Converting a recursive function to tail recursive](http://stackoverflow.com/questions/7945313/converting-a-recursive-function-to-tail-recursive) and [Converting an iterative function to recursive](http://stackoverflow.com/questions/7939493/converting-an-iterative-function-to-recursive). — Raymond Chen, Oct 30 '11 at 14:04

score 2 · Answer 1 · answered Oct 30 '11 at 13:54

2

This looks like C. C implementations don't generally recognize tail-recursion, so translating your function to a tail-recursive form won't actually help you. You need to change it to be iterative.

answered Oct 30 '11 at 13:54

ruakh

175,680
26
273
307

score 2 · Answer 2 · answered Dec 15 '11 at 03:47

The general approach to converting a non-tail-recursive function to a tail-recursive one is to use an extra accumulator parameter that carries the current evaluation with it through recursive calls.

In your case, this is rather straight-forward:

int count(node *start)
{
    return count_helper(start, start, 0);
}
int count_helper(node *current, node *start, int acc)
{
    int c;
    c = 0;
    if(current == NULL)
        return acc;
    if((current->roll_no) == 20)
        c = 1;
    if(current->next == start) return acc + c;
    return count_helper(current->next, start, acc + c);
}

The primary changes I've made here are adding the extra accumulator parameter int acc to your count_helper definition, and making sure all of the return statements include acc (when appropriate). Now the final return statement passes back the result of count_helper directly, without modifying it; this is now tail-recursive.

It is less straight-forward when the results of recursive calls have to be combined in a way that isn't simple arithmetic.

However, as ruakh mentioned, many C compilers don't want to deal with the headache of optimizing tail-recursive calls because that simply isn't C's style. Maybe -O3 will do it?

Also see this: http://stackoverflow.com/questions/34125/which-if-any-c-compilers-do-tail-recursion-optimization — buddhabrot, Dec 15 '11 at 12:20

Convert recursive function to tail recursive

2 Answers2