Joe Marshall is a long-time Lisper with an ability to come up with really elegant solutions. Indeed, the second ever Irreal post was about Marshall’s brilliant solution to a problem from SICP. Recently, he recounted a story about a recent phone screen he had in which he was asked to implement a palindrome detector. He wrote both an iterative and a recursive version. He says he gave them the iterative version so they wouldn’t think him an idiot but that he liked the recursive version better because of its simplicity and elegance.
If you think of a palindrome detector as embodying the three rules
- The empty string is a palindrome
- A string with a single character is a palindrome
- If the first and last characters of a string are identical and the substring between them is a palindrome, then the original string is a palindrome
the recursive algorithm writes itself.
Marshall doesn’t show his code so of course I had to try it myself. My initial effort was to bang out an Elisp implementation:
(defun palindromep (string)
(let ((len (length string)))
(cond
((zerop len) t)
((= 1 len) t)
((not (char-equal (aref string 0) (aref string (1- len)))) nil)
(t (palindromep (substring string 1 -1))))))
That’s practically a word-for-word rendition of the three rules and it worked well. But then I started thinking that Marshall said the iterative solution would be faster for most compilers. I don’t know what language he used but it almost certainly wasn’t Lisp so I wondered if the iterative version would be faster in a Lisp language. Of course I had to write an iterative version so I could compare them.
My first inclination was to write the iterative version in Elisp too but Elisp isn’t tail recursive so it would be hard to run the recursive version on large inputs. Therefore I decided to start over with Scheme. The recursive version is the same, mutatis mutandis, as the Elisp version.
(define palindrome-r?
(lambda (string)
(let ((len (string-length string)))
(cond
((zero? len) #t)
((= 1 len) #t)
((not (char=? (string-ref string 0) (string-ref string (1- len)))) #f)
(#t (palindrome-r? (substring string 1 (1- len))))))))
The iterative version is a little more complicated—mostly because of the do loop—but doesn’t seem nearly as elegant as the recursive version.
(define palindrome-i?
(lambda (string)
(do ((h 0 (1+ h))
(t (1- (string-length string)) (1- t))
(palindrome? #t))
((or (not palindrome?) (> h t))
palindrome?)
(set! palindrome? (char=? (string-ref string h) (string-ref string t))))))
The real test, though, is their relative speeds. In Scheme with its tail recursion, loops are generally implemented as recursion and you wouldn’t expect much difference. I ran the comparison in Guile Scheme, which has copy-on-modify string behavior so, again, the two versions seem like they should run in about the same time.
Of course, the results were nothing like that. I ran each version 1000 times on a large palindrome (100,000 x’s) with the following
(define str (make-string 100000 #\x))
(define bench
(lambda (rcnt f)
(do ((i rcnt (1- i)))
((zero? i))
(f str))))
and here are the results
,time (bench 1000 palindrome-r?)
;; 9.204000s real time, 9.370000s run time. 2.330000s spent in GC.
,time (bench 1000 palindrome-i?)
;; 4.582000s real time, 4.660000s run time. 1.350000s spent in GC.
The recursive version runs almost exactly twice as long so Marshall was correct even in the Lisp case.
None of this is very important, of course, but it was an interesting exercise that reinforced the lesson that it’s really hard to predict run times without benchmarking.
