1

我的理解是尾递归是不需要返回值来完成操作的递归；也就是说，递归是函数的最后一步，一旦进行递归调用，函数的其余部分就完成了。

对此，我问这个例子（来自 Norvig 先生）是否是尾递归：

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

一旦 finalfirst-name作为语句的一个分支被调用，if该函数就不再做任何其他事情了；因此，它是尾递归吗？

4

2 回答 2

2

是的，这就是一个例子。

尾递归优化在 Common Lisp 的许多实现中都可用，但规范并不要求它。这意味着您可以拥有一个没有尾递归优化的 Common Lisp。

您可能还会发现您正在使用的版本需要稍微戳一下才能执行此优化。

因此，在某些实现中，您可能需要使用“声明”来通知您的编译器您想要优化速度。

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

编辑： 这个网站现在已有几年历史，但可能会提供一些信息。

还请务必阅读评论，因为 Joshua 和 Rainer 在这里大幅改进了细节。

于 2013-11-13T12:07:48.853 回答
2

是和不是。通常是的。如果编译器支持 TCO 并且正确的优化设置处于活动状态，它也会被优化。但有时编译器将无法对其进行优化。

如果name会被宣布为特殊的，那么可能不会。

如果会有类似的东西

(defvar name '(susanne mustermann))

那么name函数的参数将被声明为特殊的（它将使用动态绑定）。那么编译器可能不会在first-name函数中使用尾调用优化。

这意味着您还需要知道变量符号是否被声明为特殊的。

这就是原因之一，全局特殊变量应该写成这样*name*，以防止那些应该是词法变量的局部变量的特殊声明。在这种情况下，特殊声明也会阻止 TCO。

我们最好写：

(defvar *name* '(susanne mustermann))
于 2013-11-13T14:58:55.163 回答