Lambda calculus
Formulations of recursive function theory from the 1920s and before tended to be based on making explicit definitions like those in the note above. But in the so-called lambda calculus of Alonzo Church from around 1930 what were instead used were pure functions such as s = Function[x, x + 1] and plus = Function[{x, y}, If[x 0, y, s[plus[x - 1, y]]]]—of just the kind now familiar from Mathematica. Note that the explicit names of ("bound") variables in such pure functions are never significant—which is why in Mathematica one can for example use s = (# + 1) &. (See page 907.)
The definitions in the note above involve both symbolic functions and literal integers. In the so-called pure lambda calculus integers are represented by symbolic expressions. The typical way this is done is to say that a function fn corresponds to an integer n if fn[a][b] yields Nest[a, b, n] (see note below).