The recursion theorem is actually several different theorems about recursion that give several slightly different results, and are used to justify the use of recursion in programming. All of these forms are the work of Stephen Cole Kleene.

One form of the recursion theorem states that every total recursive function σ that maps description numbers to other description numbers has a fixed point n such that φ_{n} = φ_{σ(n)}, where φ_{n} denotes the partial recursive function calculated by the Turing machine corresponding to the DN n. In other words, if we modify all possible Turing machines somehow, there exists some Turing machine M_{n} for which the modified Turing machine M_{σ(n)} still computes the same function! At first, this seems impossible: we might have σ(e) produce the DN of a Turing machine that computes φ_{e}(x) + 1, for instance, and well, φ(x) + 1 is never equal to φ(x). Unless of course φ(x) is everywhere undefined, giving us a fixed point.

This theorem is useful, among other things, for showing the existence of quines, programs that can print themselves, for any Turing complete system. In the world of Turing machines, this means that, there exists a description number q such that φ_{q} is a constant function whose value is q. This may easily be seen by taking the total recursive function ψ(e, x) = e, for all e and x. Using the Smn theorem, there exists a total recursive function f such that φ_{f(e)}(x) = ψ(e, x). From the recursion theorem, f has a fixed point q. Thus, for all x:

φ_{q}(x) = φ_{f(q)}(x) = ψ(q, x) = q

A second form of the recursion theorem, stronger than the first, deals with functionals, or higher-order functions, functions that themselves operate on functions to produce other functions. This form of the theorem deals with functionals of the form F(φ;x_{1}, ..., x_{n}) = ψ(x_{1}, ... x_{n}), that is functionals that take a function φ(x_{1}, ..., x_{n}) and a set of n arguments, producing another function ψ. This form of the recursion theorem states that for every partial recursive functional F of this form, there exists a solution φ for this recursive definition:

F(ξ;x_{1}, ..., x_{n}) = ξ(x_{1}, ..., x_{n})

such that φ is itself a partial recursive function. This solution can also be thought of as being a minimal one in the following sense: If we have two partial recursive functions ψ and φ, we say that ψ extends φ if the set of all ordered pairs {(x, φ(x)} is a subset of {(x, ψ(x)}. The solution φ guaranteed by this second form of the recursion theorem can also be said to be minimal in that any other possible solution ψ extends φ. Thus φ is a least fixed point of the functional F.

A third form of the recursion theorem, in some ways stronger and in some ways weaker than the second, states that if F is a functional of the form F(ξ, z, x_{1}, ..., x_{n}), then there exists a description number e corresponding to the function φ_{e} such that:

φ_{e}(x_{1}, ..., x_{n}) = F(φ_{e}; e, x_{1}, ..., x_{n})

This is a stronger result than the second form because now the functional F is also permitted to depend not only upon a function φ but also on a description number corresponding to φ. It is weaker because nothing in the theorem states that this fixed point φ_{e} is a least fixed point.