list - Lisp 中的十进制到二进制 - 制作一个非嵌套列表

Question

当到达我的递归案例时，我使用 list 将 future 结果附加到当前结果，但由于递归，我最终得到了一个嵌套列表。当我有一个导致递归超过五次的数字时，这会导致错误。

关于如何在单个普通非嵌套列表中获得结果的任何想法，例如:

CL-USER 100 : 8 > (BINARY_LIST 4)

(1 0 0)

代码和示例输出:

CL-USER 99 : 8 > (defun binary_list (i)
(COND 
    ((= i 0) 0)
    ((= i 1) 1)
    ((= (mod i 2) 0) (list (binary_list (truncate i 2)) 0))
    (t (list (binary_list (truncate i 2)) 1))
    )
)
BINARY_LIST

CL-USER 100 : 8 > (BINARY_LIST 4)
((1 0) 0)

CL-USER 101 : 8 > (BINARY_LIST 104)
((((# 1) 0) 0) 0)

Answer 1

你快到了。您需要做的就是替换 list与 nconc :

(defun binary-list (n)
  (cond ((= n 0) (list 0))
        ((= n 1) (list 1))
        (t (nconc (binary-list (truncate n 2)) (list (mod n 2))))))

您可以避免同时调用 truncate和 mod通过在整数除法中收集两个值:

(defun binary-list (n)
  (assert (>= n 0))
  (multiple-value-bind (q r) (floor n 2)
    (if (zerop q)
        (list r)
        (nconc (binary-list q) (list r)))))

注意这个算法是二次因为nconc必须遍历每次迭代的结果。这可以通过传递一个累加器来避免:

(defun binary-list (n &optional acc)
  (assert (>= n 0))
  (multiple-value-bind (q r) (floor n 2)
    (if (zerop q)
        (cons r acc)
        (binary-list q (cons r acc)))))

现在我们有了一个尾递归函数，它可以被现代编译器编译为迭代。

您可以使用的另一个优化技巧(实际上，应该由编译器完成 - 尝试使用 disassemble 来检查!)正在使用 ash和 logand而不是更通用和昂贵的floor :

(defun binary-list (n &optional acc)
  (cond ((zerop n) (or acc (list 0)))
        ((plusp n)
         (binary-list (ash n -1) (cons (logand 1 n) acc)))
        (t (error "~S: non-negative argument required, got ~s" 'binary-list n))))

顺便说一句，lispers 通常在符号中使用破折号而不是下划线，所以如果你不想冒犯我们温柔的审美，你的 binary_list 应该是 binary-list。