Ein Palindrom ist ein Wort, das von vorne und von hinten gelesen die gleiche Reihenfolge von Buchstaben hat. Mittels Rekursion lässt sich ein Test dafür so ausdrücken:

- Wörter mit weniger als zwei Buchstaben sind Palindrome.
- Ein Wort mit zwei oder mehr Buchstaben ist ein Palindrom, wenn der erste und der letzte Buchstabe übereinstimmen und die restlichen Buchstaben in der Mitte des Worts ein Palindrom sind.

Diese natürlichsprachige Formulierung lässt sich einfach in Lisp übersetzen:

(defproc palindrom? (word)
  (or
    (< (length word) 2)
    (and
      (= (first-char word) (last-char word))
      (palindrom? (middle word)))))

(defproc first-char (word)
  (substring word 1 1))

(defproc last-char (word)
  (substring word (length word) 1))

(defproc middle (word)
  (substring word 2 (- (length word) 2)))

Für die Zeichenketten "" und "a" ergibt sich wegen (< (length word) 2) der Wert t, ohne dass weitere Bedingungen geprüft werden. Es liegt ein Palindrom vor.

Die Zeichenkette "ab" wird in first-char "a", last-char "b" und middle "" zerlegt. Der Ausdruck (and (= first-char last-char) ...) hat auf jeden Fall den Wert nil, weil first-char und last-char nicht gleich sind. Die Zeichenkette "ab" ist also kein Palindrom.

Für die Zeichenkette "aba" sind first-char und last-char gleich, deswegen wird das Prädikat palindrom? rekursiv für die Zeichenkette "b" aufgerufen. Das ergibt den Wert t. "aba" ist ein Palindrom.

Link
https://de.wikipedia.org/wiki/Palindrom