Описание тега y-combinator

Комбинатор Y - это функция высшего порядка, которая позволяет функции, не знающей собственного имени, вызывать саму себя. Это фундаментальная основа рекурсии.

В синтаксисе схемы:

  (define Y
    (lambda (f)
      (f (lambda (x) ((Y f) x)))))

Чтобы рекурсивно реализовать Фибоначчи с помощью Y:

(define fibonacci 
  (Y
    (lambda (f)
      (lambda (n)
        (if (= n 0)
            1
            (* n (f (- n 1))))))) ))

Хорошая статья по этой теме: http://mvanier.livejournal.com/2897.html