I've heard often about "tail recursive" functions but never really tried to understand them. However, recently I've been bitten by not knowing what they are. I wrote the following OCaml code:

let rec apply_n_times n f x = 
   if n = 0 then
      x
   else
      f (apply_n_times (n-1) f x);;

Now, that's not tail recursive, as bogklug at TopCoder noted. With this version my program ended with a stack overflow error. The problem magicaly disappears in the tail recursive version:

let rec apply_n_times n f x =
   if n = 0 then
      x
   else
      apply_n_times (n-1) f (f x);;

It may seem like a trivial change but think about how would you transform these functions into loops. For the first one it is not obvious at all. You would probably need a stack if you don't do some VERY smart optimizations. But the second one is simple; in C++:

while (true)
{
   if (n == 0) return x;
   x = f(x);
   n = n-1;
}

It is almost the same code. The structure is: stop condition followed by recursive function arguments (n, x) recomputation. This transformation into a simple loop with no stack is possible for every tail recursive function. A general form for a tail recursive function is:

rec_f(a1, ..., an) = 
   if stop(a1, ..., an) then
      base_case(a1, ..., an)
   else
      rec_f(f1(a1, ..., an), ..., fn(a1, ..., an))

For some functions it is not obvious how you can express them as such. For example the simple implementation of factorial is NOT tail recursive:

let rec fact n =
   if n = 0 then
      1
   else
      n * fact (n-1);;

But it can be transformed by introducing an auxiliary function that looks like the recursive call: fact_aux(m, n) = m * n!, and expressing the factorial as n! = fact_aux(1, n). Here it is:

let rec fact_aux m n = 
   if n = 0 then
      m
   else
      fact_aux (m*n) (n-1);;
let fact n = fact_aux 1 n;;

I'm guessing this technique can be applied to more general situations as well.