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.

Answer 2

this seems to me to be the most direct, least roundabout manner to achieve the desired results every time:

(defun mvp-binary-from-decimal (n r)
    (if (zerop n)
    r
    (multiple-value-bind (a b)
        (floor n 2)
        (mvp-binary-from-decimal a (cons b r)))))

(defun binary-from-decimal (n)
    (if (and (numberp n) (plusp n))
    (mvp-binary-from-decimal n '())
    (if (eql n 0) '(0) nil)))

tested in slime, sbcl, clisp - used as follows:

CL-USER> (binary-from-decimal 100)
(1 1 0 0 1 0 0)
CL-USER> (binary-from-decimal 10)
(1 0 1 0)
CL-USER> (binary-from-decimal 0)
(0)

there are some advanced reasons as to why this might be the most desirable manner in which to implement such functionality, but for now, suffice to say that it is clean, polite, readable and always works.