(Common Lisp) Palindrome-p

Question

3.23 Palindromes. A palindrome is a number that reads the same forwards and backwards, like 12321. Write a program that tests input integers for the palindrome property. Hint.This should not be done with the numbers in their input (character) format.

For the task above, I have written the following program. Rather than converting the number to a string, I recursively divide the number to create a list of individual digits and then compare the digits from outside to in to determine if it's a palindrome. What do you think of my strategy and of my code in general? I understand that tail recursion is not guaranteed to work in Common Lisp - should I rewrite this code to use loop instead?

(defun collect-digits (candidate &OPTIONAL (digit-list ()))
  ; make a list out of the digits of the number
  ; example: (= (collect-digits 12321) (1 2 3 2 1)) is true
  (if (< candidate 10) 
    (cons candidate digit-list)
    (multiple-value-call 
      (lambda (sub-candidate onesdigit) 
        (collect-digits sub-candidate (cons onesdigit digit-list)))
      (floor candidate 10))))

(defun reflection-p (candidate-list &OPTIONAL (len (length candidate-list)))
  ; if c-l[first] = c-l[last]
  (and (= (car candidate-list) (car (last candidate-list 1))) 
       ; and the list is 3 or smaller ex. (3 1 3), it is a reflection 
       (if (<= len 3) t 
     ; if longer, keep looking
     (reflection-p (subseq candidate-list 1 (1- len)) (- len 2)))))

(defun palindrome-p (candidate)
    (reflection-p (collect-digits candidate)))

(format t "12321: ~a ~%3456789 ~a ~%" (palindrome-p 12321) (palindrome-p 3456789))

Good point about reverse-digits. In that case, this program simplifies to:

(defun reverse-digits (n)
  (labels ((next (n v)
             (if (zerop n) v
                 (multiple-value-bind (q r)
                     (truncate n 10)
                   (next q (+ (* v 10) r))))))
    (next n 0)))

(defun palindrome-p (candidate) (= candidate (reverse-digits candidate)))

(format t "12321: ~a ~%3456789 ~a ~%" (palindrome-p 12321) (palindrome-p 3456789))

(credit to Chris Jester-Young for the reverse-digits implementation) Do you have any suggestions regarding my coding style (referring to the first solution?)

Answer 1

This one is easy! Remember the reverse-digits function? If a number is the same as its reverse, then it's a palindrome.

Answer 2

Regarding your use of recursion: Generally when you consider whether to use recursion (and you don't specifically write for a platform which guarantees tail-call optimization to be performed), you need to consider the recursion depth that is likely to be reached. If it is too deep your program will use up lots of stack space and might even cause a stack overflow. However if the recursion won't be very deep, there won't be a problem.

In this the recursion depth will equal the number of digits in the number. Since your function will be unlikely to be called with numbers which have more than 100 digits, using recursion here is perfectly fine.

---

Regarding your reflection-p function. You're determining whether a list is a palindrome in the same way one would do so with an array, basically iterating from both sides. However linked lists and arrays have different performance characteristics and what works well for arrays, can be very slow for linked lists (or vice versa of course).

In this case, you're making heavy use of last and some use of length, both of which are O(n) operations. This makes your reflection-p function quite inefficient. The easiest way to check efficiently whether a list is palindromic, is just to reverse the list and check whether the original list is equal to its reverse.

---

Also a note regarding comments: The commenting convention in lisp (which is also enforced/heavily encouraged by e.g. emacs's indentation behavior) is as follows:

1. A comment describing a single line of code should use a single semicolon and be written on the same line as the code. I.e:

   (format t "hello world") ; Print hello world
   

   and not

   ; Print hello world
   (format t "hello world")
   

2. A comment describing multiple lines of code should be written before those lines using two semicolons and indented at the same level as the lines it describes.
3. A comment documenting a function should be written with three semicolons.