recursion - 如何从递归 LISP 函数返回？

Question

我是一个新的 lisp 程序员，我正在尝试创建我的第一个递归 lisp 函数来返回两个列表中较大的一个。每次我运行该函数时，它似乎都会崩溃，因为我猜我的基本情况没有得到满足。这是我的代码。

(defun longest (l1 l2)
  (cond ((null l1) (l2))
        ((null l2) (l1))
        (t (rest l1) 
           (rest l2) 
           (longest l1 l2))
  )
)

我知道这不适用于两个列表长度相同的情况，但我只是想先让一些东西起作用。我知道这也可以通过 while 循环来实现，但出于学习的目的，我想使用递归。

为什么这段代码永远不会终止？

Answer 1

此代码永远不会终止，因为您一次又一次地使用相同的输入数据调用 longest。 rest返回列表中除第一个元素之外的所有元素，不修改列表，最初作为参数传递。还有其他错误:

(defun longest (l1 l2)
  (cond ((null l1) (l2)) ;; <= will give error,
        ((null l2) (l1)) ;;  because there is no such function like l2
        (t (rest l1) ;; <=  result ignored
           (rest l2) ;; <=  result ignored
           (longest l1 l2)))) ;; <= called with the same l1 and l2

很明显，它会一直运行到堆栈用完为止。预期行为的正确代码将是:

(defun longest (l1 l2)
  (cond ((null l1) l2)
        ((null l2) l1)
        (t 
         (longest (rest  l1) (rest  l2)))))

请注意，您可能无法通过这种方法获得预期的结果，因为 longest 每次都会获取列表的 CDR，因此它只会返回最长列表的剩余元素，所以如果您调用 (longest '(1 2 3) '(1 2))，您只会得到 '(3)，这可能不是您所期望的。

如果你想让它真正返回所有最长的列表，你必须修改你的代码。