Is this lisp example featuring tail recursion?

Question

My understanding is that tail recursion is recursion where a return value is not necessary to finish the operation; that is, the recursion is the last step in the function, and the rest of the function is done once it makes the recursive call.

To that, I ask if this example (from Mr. Norvig) is tail recursion:

(defparameter *titles*
  '(Mr Mrs Miss Ms Sir Madam Dr Admiral Major General)
  "A list of titles that can appear at the start of a name.")

(defun first-name (name)
  "Select the first name from a name represented as a list." 
  (if (member (first name) *titles*)
     (first-name (rest name))
     (first name)))

Once the final first-name is called as a branch of the if statement, there is nothing else that function does; therefore, it is tail recursion?

Answer 1

Yup, that is an example.

Tail recursion optimization is available in many implementations of Common Lisp but it is not required by the spec. This means you can have a Common Lisp without tail recursion optimization.

You may also find that the version you are using needs to be poked a bit to perform this optimization.

So in some implementation you may need to use 'declare' to inform your compiler that you want to optimize for speed.

(defun first-name (name)
  "Select the first name from a name represented as a list." 
  (declare (optimize (speed 3) (compilation-speed 0) (debug 0) (safety 1)))
  (if (member (first name) *titles*)
      (first-name (rest name)) 
      (first name)))

Edit: This site is a few years old now but may provide some info.

Also be sure to read the comments as Joshua and Rainer massively improve the detail here.

Answer 2

Yes and no. Usually yes. It will also be optimized if the compiler supports TCO and the right optimization settings are active. But sometimes the compiler will not be able to optimize it.

If name would have been declared special, then possibly not.

If there would be something like

(defvar name '(susanne mustermann))

then the parameter name of the function would be declared special (it would use dynamic binding). Then a compiler might not use tail call optimization in the first-name function.

This means that you also need to know whether variable symbols are declared special or not.

That's one of the reasons, global special variables should be written like *name* to prevent special declaration of those local variables which should be lexical variables. In this case a special declaration would also prevent TCO.

We better write:

(defvar *name* '(susanne mustermann))