電導率和遞歸性

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所列出併合並them.But出於某種原因，現在看來似乎卻拒絕這樣做遞歸part.What這裏我錯過？（我知道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因爲另一個bug（代碼 - 我的格式）：

((< (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你扔掉的結果，並解開返回堆棧後後，你最終返回第一個值你setfl3到這恰好是(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)))))