This page gives a collection of simple Lisp programs that have traditionally been used for benchmarking Lisp systems. Most of them are recursive, and some of them have no other obvious practical use beyond acting as a benchmark.
A classic benchmark for comparing implementations of Lisp is this variant of the Takeuchi function, originally used by Ikuo Takeuchi of Japan:
(defun tak (x y z) (if (not (< y x)) z (tak (tak (1- x) y z) (tak (1- y) z x) (tak (1- z) x y))))
A good set of parameters, giving execution times in the range 30 to 90 secs for typical uLisp platforms, is:
(tak 18 12 6)
On an Arduino Mega 2560 (tak 18 12 6) takes 54 secs to return the answer 7.
The Fibonacci sequence is:
1, 1, 2, 3, 5, 8, 13, 21 ...
where the first two terms are 1, and each subsequent term is the sum of the two previous terms. The following recursive function finds the nth term, counting from 0:
(defun fib (n) (if (< n 3) 1 (+ (fib (- n 1)) (fib (- n 2)))))
On an Arduino Mega 2560 (fib 23) takes 30 secs to return the answer 28657.
Hofstadter Q sequence
This is one of several recursive sequences described in Douglas Hofstadter's book "Gödel, Escher, Bach: an Eternal Golden Braid". It is defined as follows:
(defun q (n) (if (<= n 2) 1 (+ (q (- n (q (- n 1)))) (q (- n (q (- n 2)))))))
It is related to the Fibonacci sequence, except that in this case the two preceding terms specify how far to go back in the sequence to find the two terms to be summed.
On an Arduino Mega 2560 (q 21) takes 56 secs to return the answer 12.