;;; Let's jump right in. The first form may look a little murky at
;;; first because of the extra lambda.  Try to trace what happens when
;;; you evaluate ((fact1 fact1) 10); you should get 
;;; (* 10 ((fact1 fact1) 9)) and so on.  As you think of this, note
;;; the crucial (h h) at the end.  Why is it necessary?

(define fact1
  (lambda (h)
    (lambda (n)
      (if (= n 1) 
	  1
	  (* n ((h h) (- n 1)))))))

;;; So that works and could certainly serve as the answer to, "How do you do
;;; recursion with just lambdas?" But what if we really want to take this,

(define F
  (lambda (h)
    (lambda (n)
      (if (= n 1) 
	  1
	  (* n (h (- n 1)))))))

;;; and turn it into a recursive function. Observe that if we already had
;;; a working factorial function 'fact' then,  
;;;          (F fact)  ---> fact.   
;;; So F is waiting for the right function to bootstrap itself! 
;;; The Y combinator is the magic that takes us there. 
;;;          (Y F)     ---> fact    
;;; In other words Y provides a fixed point of F because,
;;;          (F (Y F)) ---> (Y F) 

;;; To frustrate the novice, we should say here, "The rest is just
;;; currying!" First go  back to fact1 again and remove the troublesome 
;;; (h h) by adding another lambda. 

(define fact2
  (lambda (g)
    ((lambda (h)
       (lambda (n)
	 (if (= n 1) 
	     1
	     (* n (h (- n 1))))))
     (lambda (m) ((g g) m)))))

;;; This is by no means the only natural way to proceed, but
;;; unfortunately here all roads don't lead to Rome. Next we look
;;; for the correct argument to fact2. We want,
;;;           ((fact2 A) 10) =    10!
;;; or        ((fact2 A) 10) ---> (* 10 ((A A) 9))
;;; So the right A is... fact2! Indeed ((fact2 fact2) n) works.
;;; Cleaning up a little,

(define fact3
  (lambda (g)
      (F (lambda (m) ((g g) m)))))

;;; and finally,

(define fact
  ((lambda (g)
      (F (lambda (m) ((g g) m))))
   (lambda (g)
       (F (lambda (m) ((g g) m))))))

;;; is the factorial function. Now it is clear that the Y combinator should be,

(define Y
  (lambda (f)
    ((lambda (u)
       (f (lambda (x) ((u u) x))))
     (lambda (v)
       (f (lambda (x) ((v v) x)))))))

;;; This is also called the Turing fixed point combinator. How
;;; pleasing and symmetric it looks! For greater obscurity, we could
;;; also compress it as,  

(define Yobs
   (lambda (f)
     ((lambda (f)
	(f f))
      (lambda (u)
	(f (lambda (x) ((u u) x)))))))

;;; which has the effect of inducing a powerful headache.