Decimal to Binary in Lisp - make a non-nested list

Question

When reaching my recursion cases, I use list to append the future result with the current one, but I end up with a nested list because of recursion. This causes an error when I have a number that causes recursion for more than five times.

Any ideas how I can get results in a single plain non-nested list, e.g.:

CL-USER 100 : 8 > (BINARY_LIST 4)

(1 0 0)

Code & Example output:

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

You are almost there. All you need to do is to replace list with 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))))))

You can avoid calling both truncate and mod by collecting both values in integer division:

(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)))))

Note that this algorithm is quadratic because nconc has to traverse the result on each iteration. This can be avoided by passing an accumulator:

(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)))))

Now we have a tail-recursive function which can be compiled to iteration by a modern compiler.

One more optimization trick you could use (which, in fact, should be done by the compiler - try disassemble to check!) is using ash and logand instead of the much more general and expensive 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))))

Incidentally, lispers usually use dash instead of underscores in symbols, so your binary_list should be binary-list if you do not want to offend our tender aesthetics.