Factorial
The Factorial of n is the product of all the integers between 1 and n inclusive. Outside of mathematics, it is a common example to explain recursion.

(defun fact (n) (if (zerop n) 1 (* n (fact (1- n)))))
Of course, the code here only works for non-negative integers.

Here's an iterative implementation:

(defun fact (n) (check-type n unsigned-byte) (loop for i from 0 to n for fact = 1 then (* fact i) finally (return fact)))

CPS:

(defun fact (x) (labels ((fact-aux (n k) (cond ((zerop n) (funcall k 1)) (t (fact-aux (1- n) (lambda (m) (funcall k (* m n)))))))) (check-type x (integer 0 *)) (fact-aux x #'identity)))

There's less wrong with the above than there used to be. It is now the case that these functions simply behave in odd ways when given negative or non-integers; and of course the recursive (first) definition can still overflow the stack.

I still prefer my take, of course...:

(defun fact (n) ;; in a _(declarations-are-assertions) compiler like _(CMUCL) or _(SBCL), ;; I might write (_H(DECLARE) (TYPE UNSIGNED-BYTE N)) here. (_H(check-type) n _H(unsigned-byte)) (let ((result 1)) (declare (type unsigned-byte result)) (do ((i n (1- i))) ((= i 0) result) (setf result (* result i)))))
-- Christophe

Are the HyperSpec references intentional here? -- Roland Kaufmann

Well, I put them in because people might be interested in the difference between CHECK-TYPE and DECLARE, and might want to look them up. -- (Christophe)

;; A tail-recursive version, w/o an auxiliary function, inspired by Winston's fibonacci function in Lisp, 3rd edition (defun fact (n &optional (so-far 1)) (if (<= n 1) so-far (fact (- n 1) (* n so-far))))

--Above function overflows stack on Lispworks. --I also use Lispworks (LWM 4.4.5). I don't have any issues with this function, once compiled, for values up to 10000. It seems to hog the machine for (fact 100000), no doubt understandably. Olivier --If the result is not diaplayed, (fact 10000) takes 0.5 sec. and (fact 100000) takes 69 sec. on 1.8 MHz G5

;; Factorial using anonymous recursive function (funcall ((lambda (f) #'(lambda (n) (funcall f f n))) #'(lambda (f n) (if (= n 0) 1 (* n (funcall f f (- n 1)))))) x)

Here's another iterative implementation:

(defun factorial(x) (reduce '* (loop for a from x downto 1 collect a)))