Tail Recursion in C++

C tail call optimization

Statements like "C doesn't perform tail call elimination" make no sense. As you correctly noted yourself, things like this depend entirely on the implementation. And yes, any decent implementation can easily turn tail-recursion into [an equivalent of] a cycle. Of course, C compilers do not normally give any guarantees about what optimizations will and what optimizations will not happen in each particular piece of code. You have to compile it and see for yourself.

Is Tail recursive really powerful on C language?

The C standard does not specify tail recursion as part of the language at all. The only thing the C99 standard says about recursive function calls is:

6.5.2.2 Function Calls
11 Recursive function calls shall be permitted, both directly and indirectly through any chain
of other functions.

If a compiler can detect tail recursion and translate a recursive call as tail recursion, it can but it is not required to do so by the standard.

How do I tell if a function is tail recursive C?

For a function to be tail recursive, the recursive call must be its last action.
In your code, the last thing the function does is adding two values, so list_size_count() is not tail recursive.

int list_size_count(link_t *first, int acc)
{
  if (first != NULL)
  {
    return (acc + list_size_count((first->next), 1));
  }
  return acc;
}

Here is how to make it tail recursive:

int list_size_count(link_t *first, int acc)
{
  if(first != NULL)
  {
    return list_size_count(first->next, acc + 1);
  }

  return acc;
}

Tail recursion in C

When doing tail recursive functions (especially tail recursive functions) it is often helpful to have a helper function in addition to another function which has a more friendly interface. The friendly interface function really just sets up the less friendly function's 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 passing an accumulator value you avoid having to use pointers or do any computations upon returning from called functions, which makes the functions truely tail recursive.

Tail Recursion in C?

You can definitely improve your function's efficiency by implementing fast multiplication algorithm:

int exp(int base, int pow) {
    if (pow == 0) {
        return 1;
    }
    if (pow%2 == 0) {
        int temp = exp(base, pow/2);
        return temp*temp;
    } else {
        int temp = exp(base, (pow-1)/2);
        return temp*temp*base;
    }
}

We use temp value not to count same value twice with recursion.

How exactly does tail recursion work?

The compiler is simply able to transform this

int fac_times (int n, int acc) {
    if (n == 0) return acc;
    else return fac_times(n - 1, acc * n);
}

into something like this:

int fac_times (int n, int acc) {
label:
    if (n == 0) return acc;
    acc *= n--;
    goto label;
}

What is tail recursion?

Consider a simple function that adds the first N natural numbers. (e.g. sum(5) = 0 + 1 + 2 + 3 + 4 + 5 = 15).

Here is a simple JavaScript implementation that uses recursion:

function recsum(x) {
    if (x === 0) {
        return 0;
    } else {
        return x + recsum(x - 1);
    }
}

If you called recsum(5), this is what the JavaScript interpreter would evaluate:

recsum(5)
5 + recsum(4)
5 + (4 + recsum(3))
5 + (4 + (3 + recsum(2)))
5 + (4 + (3 + (2 + recsum(1))))
5 + (4 + (3 + (2 + (1 + recsum(0)))))
5 + (4 + (3 + (2 + (1 + 0))))
5 + (4 + (3 + (2 + 1)))
5 + (4 + (3 + 3))
5 + (4 + 6)
5 + 10
15

Note how every recursive call has to complete before the JavaScript interpreter begins to actually do the work of calculating the sum.

Here's a tail-recursive version of the same function:

function tailrecsum(x, running_total = 0) {
    if (x === 0) {
        return running_total;
    } else {
        return tailrecsum(x - 1, running_total + x);
    }
}

Here's the sequence of events that would occur if you called tailrecsum(5), (which would effectively be tailrecsum(5, 0), because of the default second argument).

tailrecsum(5, 0)
tailrecsum(4, 5)
tailrecsum(3, 9)
tailrecsum(2, 12)
tailrecsum(1, 14)
tailrecsum(0, 15)
15

In the tail-recursive case, with each evaluation of the recursive call, the running_total is updated.

Note: The original answer used examples from Python. These have been changed to JavaScript, since Python interpreters don't support tail call optimization. However, while tail call optimization is part of the ECMAScript 2015 spec, most JavaScript interpreters don't support it.

Tail recursion in C++

A simple tail recursive function:

unsigned int f( unsigned int a ) {
   if ( a == 0 ) {
      return a;
   }
   return f( a - 1 );   // tail recursion
}

Tail recursion is basically when:

there is only a single recursive call
that call is the last statement in the function

And it's not "better", except in the sense that a good compiler can remove the recursion, transforming it into a loop. This may be faster and will certainly save on stack usage. The GCC compiler can do this optimisation.