Factorial

The Factorial of n is the product of all the integers between 1 and n inclusive.

  (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 (DECLARE (TYPE UNSIGNED-BYTE N)) here.
    (check-type n 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)))

This page is linked from: Fibonacci

CLiki pages can be edited by anyone at any time. Imagine a fearsomely comprehensive disclaimer of liability. Now fear, comprehensively