DZone Snippets is a public source code repository. Easily build up your personal collection of code snippets, categorize them with tags / keywords, and share them with the world

Snippets has posted 5883 posts at DZone. View Full User Profile

Factorials In Many Incarnations

09.25.2006
| 4372 views |
  • submit to reddit
        // http://www.cs.indiana.edu/~sganz/publications/icfp99/paper.pdf

;; simple definition of factorial:
;; this will run into trouble due to precision

(define (factorial-1  num)
  (if (= num 0)
      1
      (* num (factorial-1 (- num 1)))))

;; factorial using imported GMP package:
;; it works better but runs into trouble with too deep call stack

(load "gmp.lsp")

(define (factorial-gmp num)
  (if (= num 0)
      "1"
      (GMP:* (string num) (factorial-gmp (- num 1)))))

;; Finally, a trampoline style recursive definition of
;; factorial which simulates tail recursive implementation
;; avoiding call stack overflow

(define (factorial-acc num acc)
  (if (= num 0)
      (land (string acc))
      (bounce factorial-acc (- num 1) (GMP:* (string num) (string acc)))))

(define (factorial-trampoline num)
  (trampoline factorial-acc num 1))

(define (trampoline func num acc)
  (set 'bouncer (bounce func num acc))
  (catch (while 1
		(set 'bouncer (bouncer))
		(if (not (lambda? bouncer))
		    (throw bouncer)))))

(define (bounce)
  (letex (func (args 0) num (args 1) acc (args 2))
	(lambda() (func num acc))))

(define (land val)  val)