Thread: tail recursion

I recently read in a book about tail recursion and how most good compilers do it. The problem is that it gave a very poor definition of what exactly tail recursion was. Depending on where I've read, its either the ability of recursion to simulate iteration, or the ability of a recursive function to perform on the second half of say a vector even though it wasn't told to! Now you can see why I'm confused! Can anyone help me grasp what this means possibly with a small example?

<programming> When the last thing a function (or procedure) does is to call itself. Such a function is called tail recursive. A function may make several recursive calls but a call is only tail-recursive if the caller returns immediately after it. E.g.

f n = if n < 2 then 1 else f (f (n-2) + 1)

Here the both calls to fib are {recursive} but only the outer one is tail recursive.

See {tail recursion optimisation}, and, if you aren't sick of them already, {recursion}, {tail recursion}.

[{Jargon File}]

(1996-02-22)


Tail Recursion Optimisation
(TRO) When the last thing a function or procedure does is to call itself, it is not necessary to retain the calling environment. This is important when a procedure calls itself {recursive}ly many times for, without tail recursion optimisation, the environments of earlier invocations would fill up the memory only to be discarded when (if) the last call terminated.

Tail recursion optimisation is a special case of {last call optimisation} but it allows the further optimisation that some arguments may be passed in situ, possibly in {register}s. It allows recursive functions to be compiled into {iterative} loops. See also {conversion to iteration}, {tail recursion modulo cons}.

I think it was Steele who said that "tail recursive functions
are like gotos but with parameters". The scheme language
has no loop primatives and requires an implementation to
use tail recursion. For c compilers it's not to much of
a problem since most people don't write code like this
in c

Code:

void f(int n)
{
      if (n != 0) 
             printf("n = %d\n", n);
      f(n - 1);
}

Okay, that makes a lot more sense now. Thanks!