Introducing Accumulators

Often, a non tail recursive algorithm can be turned into a tail recursive one by introducing accumulators to accumulate and/or carry along intermediate results. For example:

int factorial (int n)
{ return (n == 0) ? 1 : n * factorial(n - 1); }

is not tail-recursive because the last thing that needs to be done is the multiplication, not the recursive call.

Instead, we can introduce an accumulator to accumulate the partial product:

int factorial_aux (int n,int accu)
{ return (n == 1) ? accu : factorial_aux(n-1,n*accu); }

int factorial (int n)
{ return factorial_aux(n,1); }

A modern compiler will turn this version into machine code equivalent to the iterative version.