Lisp递归实现列表分割

Question

(defun split-list (L) 
    (if (endp L)
    '(nil nil)  
     (let ((x (split-list (cdr L)))) 
         (list (cons (car L) (cadr x))(car X))
         )))

这是我拥有的代码，它运行得很好：

(split-list '(1 2 3 4 5 6))
((1 3 5) (2 4 6))

但我需要关于递归部分的解释。

当我们调用函数 (split-list (cdr L)) 时，我确信它从123456到23456。 (car L) 是1，(cadr X) 是3，但是5是怎么来的呢？

当函数执行 (split-list (cdr L)) 时，x 不是变成了3456吗？(cadr x) 应该是4，但这是错的，另一半也是同样的问题。现在 (car x) 应该是3，但也是错误的。

请问有人可以解释一下吗？

- Ash

Answer 1

我会将递归的split-list重写为：

(defun split-list (list) 
  (if (endp list)
      (values nil nil)
    (multiple-value-bind (split1 split2)
        (split-list (rest list))
      (values (cons (first list) split2)
              split1))))

上面使用了多个值。该函数将分割结果作为两个值返回。我们还将 car 替换为 first，将 cdr 替换为 rest。它们只是更好的名称，但具有相同的功能。 multiple-value-bind 将递归调用 split-list 的两个值绑定到变量 split1 和 split2 中。函数 values 将其两个参数作为两个值返回。

在下面的示例中，您可以看到该函数确实返回两个值：

CL-USER 20 > (split-list '(a b c d e f))
(A C E)
(B D F)

您可以跟踪它的执行：

CL-USER 21 > (trace split-list)
(SPLIT-LIST)

CL-USER 22 > (split-list '(a b c d e f))
0 SPLIT-LIST > ((A B C D E F))
  1 SPLIT-LIST > ((B C D E F))
    2 SPLIT-LIST > ((C D E F))
      3 SPLIT-LIST > ((D E F))
        4 SPLIT-LIST > ((E F))
          5 SPLIT-LIST > ((F))
            6 SPLIT-LIST > (NIL)
            6 SPLIT-LIST < (NIL NIL)
          5 SPLIT-LIST < ((F) NIL)
        4 SPLIT-LIST < ((E) (F))
      3 SPLIT-LIST < ((D F) (E))
    2 SPLIT-LIST < ((C E) (D F))
  1 SPLIT-LIST < ((B D F) (C E))
0 SPLIT-LIST < ((A C E) (B D F))
(A C E)
(B D F)

- Rainer Joswig

---

谢谢您！我总是在递归的下半部分遇到麻烦。第一部分，即去除元素很容易，但是下半部分有点困惑。不过您的解释非常好。 - Ash