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?

I'd say "that tail recursion is recursion where nothing but a return value is necessary to finish the operation". — Will Ness
– Will Ness, Commented Nov 13, 2013 at 16:15

Will Ness · Accepted Answer · 2013-11-13 16:30:17Z

2

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.

edited Nov 13, 2013 at 16:30

Will Ness

71.6k10 gold badges105 silver badges192 bronze badges

answered Nov 13, 2013 at 12:07

Baggers

3,24125 silver badges33 bronze badges

Sign up to request clarification or add additional context in comments.

7 Comments

johnbakers Over a year ago

I am using sbcl but I am not using declare yet the function works as expected. Are you saying the implementation is not required to optimize the tail recursion, however the implementation should be required by spec to allow the programmer to write a tail recursive function, like the above.

Baggers Over a year ago

The spec allows for recursive functions but does not mandate that they be tail call optimized even if the code is written in that fashion.... Looking at the sbcl manual I may be wrong about whether sbcl needs the declare. I will change the wording in my answer a bit

Rainer Joswig Over a year ago

@Baggers: if the global optimization declaration values already trigger TCO, then the local declare is not necessary.

Rainer Joswig Over a year ago

Btw.: "that you want to optimize for speed" ... that's one way to see it. But it also is: "you want to trade in less debugging capabilities for better space efficiency or better speed". TCO means typically: no call frames for the debugger, no tracing for the tail call, ...

Joshua Taylor Over a year ago

Just a nitpick: a function call is either in tail position or it isn't. Every implementation of Common Lisp allows you to make calls, recursive or not, in tail position. What they don't all do is tail call optimization which reuses the existing stack frame for the function being called in tail position.

|

Rainer Joswig · Accepted Answer · 2013-11-13 14:58:55Z

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))

Collectives™ on Stack Overflow

Is this lisp example featuring tail recursion?

2 Answers 2

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related