За самоприменимость
Народ тут не верит в самоприменимые функции, боится парадокса Рассела и цитирует Витгенштейна:

3.333. Функция не может быть своим собственным аргументом, потому что функциональный знак уже содержит первообраз своего аргумента, а он не может содержать самого себя. Предположим, например, что функция F(fx) могла бы быть своим собственным аргументом; тогда должно иметься предложение: F(F(fx)), и в нем внешняя функция F и внутренняя функция F должны иметь различные значения, потому что внутренняя функция имеет форму Ф (fх), а внешняя - пси (Ф (fх)). Общим у обеих функций является только буква F, которая сама по себе ничего не обозначает. Это сразу же станет ясно, если мы вместо F(F(u)) напишем: ($Ф) : Р(Ф и) • Фи=Fи". Этим самым устраняется парадокс Рассела.

Потому некоторый ликбез:

(тем, кто и так в курсе того, что такое Y-combinator, вряд ли будет интересно)

Итак - что такое рекурссия: это когда мы пишем что-то типа:

TYPE List = RECORD value: INTEGER; next: ^List END;

Или функция:

factorial = λ n. if n = 0 then 1 else n * factorial (n-1)

(обозначение λ x. ... обозначает функцию от x, правило вычисления которой расположено справа от точки
F = λ x. ... - тоже самое, что обычно пишется: F (x) = ... - символика, кстати, восходит как раз к Расселу)

То есть все, что надо - это уметь находить решение уравнения

a = F (a)

где F - формула вроде вышеприведенных, в которую определяемое значение входит параметром. То есть - находить фиксированную точку функции F - такое значение параметра, при котором (назовем его а) - см. выше. Назовем его Y (F)

F (Y (F)) = Y (F)

Тезис о его существовании выглядит несколько странно, но это чуть ниже. А пока пример:

fact0 = λ f  . λ n . if n = 0 then 1 else n * f (n-1)

Пока никакой рекурсии - правда. Теперь определим fact = Y fact0 и посмотрим, что будет, если попробовать посчитать fact (2):

fact (2) = Y fact0 2 = fact0 (Y fact0) 2 = 
      if 2 = 0 then 2 else 2 * Y fact0 (2-1) = 2 * Y fact0 1 =
      2 * if 1 = 0 then 1 else 1 * Y fact0 (1-1) = 2 * 1 * Y fact0 0 =  2 * 1 * fact0 (Y fact0 0)
      2 * 1 * if 0 = 0 then 1 else 0 * Y fact0 (0-1) = 2 * 1 * 1 = 2

Что и требовалось получить. Теперь собственно об обосновании оператора фиксированной точки, кой был обозначен Y: он, как ни странно, не только непротиворечив, но и имеет свойство с завидной назойливостью вылазить в любых околоалгоритмических формализмах. Первый раз он вылез в 30-е годы у Черча в λ-исчислении - формализме, придуманном им до некоторой степени по мотивам расселовской теории типов в предположении, что если в столь примитивном формализме удастся формлизовать значительную часть математики (арифметику, хотя бы) то уж точно никакой гадости не вылезет.

Сам формализм собственно выглядел примерно так, как в примерах выше, только кроме лямбд, применения функций к аргументам и переменных там ничего не было. Как через это выражались числа, условные операторы etc я рассказывать не буду (желающие могут прочитать тут). Важно, что выражались хорошо.

Но в один прекрасный момент обнаружилось, что там есть такая конструкция (а также еще много похожих):

 Y = λf.(λx.f (x x)) (λx.f (x x))

Про нее легко проверить, что для любого f имеет место Y f = f (Y f) (подробности см). И счастье окончилось.

К чему это все - а к тому, что лямбда-выражения являются вполне адекватной формализацией понятия функции (хотя м.б. неисчерпывающей), тривиально непротиворечивы (потому как вводятся прямо через синтаксическую модель) и самоприменимы. Более того - оное ичисление является весьма удобной формальной семантикой для языков программирования - и прием - постулировать существование fixpoint оператора и обосновать его непротиворечивость подкладыванием соотвествующей модели в терминах лямбд - вполне удобная практика.

Собственно самоприменимость точно также вылазит и из теоремы Геделя (из совсем неожиданного места и неожиданным образом). Так что пугаться ее не надо (хотя надо "обращаться с осторожностью") и вообще свойство естественное - так что видимо в начале XX века перепугались не того чего надо и не по делу. А Рассел научил Витгенштейна плохому.