Here is an example that a forum poster gave, I can't tell if this tail optimized. Also, could someone give a laymans description of how a tail optimized version would trump the normal version.
(defun mylength (s)
(labels ((mylength-inner (s x)
(if (car s) (mylength-inner (cdr s) (+ x 1)) x)))
(mylength-inner s 0)))
A non tail optimized version?
(defun l (s) (if (car s) (+ 1 (l (rest s))) 0))
Tail calls can be optimized to not need extra space on the call stack, and it requires that the last operation in the function be the recursive call, which appears to be the case in your forum-sourced example. The last operation in the non-tail version is an addition, so the recursive call requires its own stack frame.
This follows a simple pattern, define an inner function that takes an accumulator argument in addition to the outer functions arguments, and accumulate your answer as you go. When you get to the end, yield the accumulated value.
There's probably a better explanation here:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1
A function can be tail-call optimized if it returns a straight call to itself or no call to itself. The function mylength-inner will return either x or (mylength-inner (cdr s) (+ x 1)), and so it can be tail-optimized.
This means the compiler can turn it into a loop instead of calling the function recursively. Either return x, or assign (cdr s) to s, increment x, and start again at the top. (The Scheme standard requires that implementations be able to do this optimization, while the Common Lisp standard leaves it up to the implementation. Of course, this optimization is a very useful thing, so most implementations will do it.)
In the non-optimized version, l doesn't just return a call to l, but rather the result of a call to l with one added. This means it can't be directly turned into a loop, so all the function calls will have to be made.
Suppose the compiler wanted to turn l into a loop. There's no problem with the assignment of (rest s) to s, but where does it put the (1 + ...)?
FWIW, CL doesn't guarantee that it will optimize away tail calls; it depends on the implementation. SBCL supports it. This is different from Scheme, where the spec requires that the compiler eliminate tail calls. If you don't do it, you're not Scheme.
Also, tail recursion is rather non-idiomatic in CL. We have a loop macro, so use it :)
Scheme's "textbook" example of list length would be here: http://www.scheme.com/tspl3/start.html#./start:h8 search for "length."