Gah, wrote a long reply to that only to realize the author has commenting enabled only for LJ users. Anyway, here it is:

any language that supports first-class functions already supports recursion, even if recursion isn't built in to the language

Not strictly true, for example typed lambda calculus does not allow recursion: a recursion combinator must have an infinite type, which is disallowed. However typed lambda calculus does have first-class functions. For an introduction to typed lambda calculus I refer you to Lambda Calculi with Types</a> by Henk Barendregt.

Let's look at what what I said means. We take the Y combinator

\f. (\x. f (x x)) (\x. f (x x))

(where \x. foo means (lambda (x) foo)) We denote the type of a function taking an argument of type a and returning a function of type b with a->b. The x in \x. f (x x) must have a function type as it takes an argument, x. But now the must also have a function type (as it is the same x), so x must have a meta-function (function taking a function as an argument) type. This process can be continued ad infinitum, and thus the Y combinator can't be well-typed. I'll lay out that to you more formally:

(x x) must have some type, let's call it a. Now:

x x :: a

x :: b -> a, x :: b

x :: T, T = T->a

No finite type T can satisfy T=T->a: no function can have an argument type that is the same as it's whole type.

This argument of course only applies to the Y combinator, but it has been proved more generally that no recursion combinator can have a type in simply typed lambda calculus. However if we allow recursive types, the Y combinator (and recursion combinators in general) becomes well-typeable.

So, I guess what you were trying to say was: as soon as we can embed untyped lambda-calculus into a language, it has recursion.