t3x.org / sketchy / prog / fact.html
SketchyLISP Stuff Copyright (C) 2006 Nils M Holm

fact

Conformance: R5RS

Purpose: Compute x! using the "recursive product" algorithm. X must be a positive integer.
 
The algorithm (in Java) was found under "factorial functions" at http://www.luschny.de/math/.

Arguments:
N - number

Model:

(define (fact n) 
  (cond ((zero? n) 1)
    (#t (* n (fact (- n 1))))))

Implementation:

(define (fact n)
  (letrec
    ((r* (lambda (n k)
      (cond ((< k 2) n)
        (#t (let ((l (quotient k 2)))
              (* (r* n l)
                 (r* (+ n l) (- k l)))))))))
    (cond ((negative? n)
        (bottom (list 'fact n)))
      (#t (r* 1 n)))))

Example:

(fact 5) 
=> 120