recursion - 条件和递归

Question

(defun mergl(l1 l2 l3)
    (cond
        ((and (null l1) (not(null l2))) l2)
        ((and (null l2) (not(null l1))) l1)
        ((and (null l1) (null l2)) l3)
        ((< (car l1) (car l2)) (setf l3 (cons (car l1) l3)) (mergl (cdr l1) l2 l3) l3)
        (t  (setf l3 (cons (car l2) l3)) (mergl l1 (cdr l2) l3) l3)
    )
)

上面的代码应该采用 2 个列表并将它们合并。但出于某种原因，它似乎拒绝执行递归部分。我在这里缺少什么？(我知道 append 会这样做但我不能使用它)

(mergl '(1 3 5 7) '(2 4 6 8) '()) 结果是 (1)

Answer 1

它有助于简单地添加 (format t "~a ~a ~a~%"l1 l2 l3) 作为您的过程的第一种形式；结果将是:

(1 3 5 7) (2 4 6 8) NIL
(3 5 7) (2 4 6 8) (1)   <-- this will be interesting later
(3 5 7) (4 6 8) (2 1)
(5 7) (4 6 8) (3 2 1)
(5 7) (6 8) (4 3 2 1)
(7) (6 8) (5 4 3 2 1)
(7) (8) (6 5 4 3 2 1)
NIL (8) (7 6 5 4 3 2 1)
(1)                     <-- oops what happened?

错误发生在最后； l1 是 null 所以您只需返回 l2 - 或者您认为的那样。但是由于另一个错误(您的代码 - 我的格式)，您返回的结果既不是 l1、l2 也不是 l3:

   ((< (car l1) (car l2)) 
    (setf l3 (cons (car l1) l3))
    (mergl (cdr l1) l2 l3) 
    l3)
   (t  
    (setf l3 (cons (car l2) l3)) 
    (mergl l1 (cdr l2) l3) 
    l3)))

在对 mergl 的递归调用之后，您丢弃了结果，在展开返回堆栈之后，您最终返回了 setf 的第一个值>l3 到 在这种情况下恰好是 (1)。它是 l3 的第一个值，因为每次递归调用都会在进入过程时分配一个新的 l3，所以第一个 l3 没有被修改稍后调用 setf。

我想这应该是一个带有累加器的尾递归过程，应该这样写:

(defun mergl (l1 l2 l3)
  (cond
   ((and (null l1) (null l2))
    (reverse l3))
   ((null l1) 
    (mergl l1 (cdr l2) (cons (car l2) l3)))
   ((null l2) 
    (mergl (cdr l1) l2 (cons (car l1) l3)))
   ((< (car l1) (car l2)) 
    (mergl (cdr l1) l2 (cons (car l1) l3)))
   (t
    (mergl l1 (cdr l2) (cons (car l2) l3)))))

然后

(mergl '(1 3 5 7) '(2 4 6 8) '())
=> (1 2 3 4 5 6 7 8)

功能代码重复，可以简化为:

(defun mergl (l1 l2 l3)
  (cond
   ((and (null l1) (null l2))
    (reverse l3))
   ((or (null l2) (and (not (null l1)) (< (car l1) (car l2))))
    (mergl (cdr l1) l2 (cons (car l1) l3)))
   (t 
    (mergl l1 (cdr l2) (cons (car l2) l3)))))