In this section we review the semantics of functional recursive programs which were the initial subject matter of denotational semantics. (These functional recursive programs are a special case of procedural recursive programs in languages like Java and C# in that nothing ever changes.)

The problem is as follows. We need to give a semantics to programs such as the definition of the factorial program as

function fact(X)

Y:=1;

while (X>0) do (Y:=X*Y; X:=X-1);

return Y;

end function

The meaning of this factorial program should be a function on the natural numbers. To give a compositional

In the semantics of recursion, a domain is typically a partial order, which can be understood as an order of definedness. For instance, the set of partial functions on the natural numbers can be given an order as follows:

given partial functions f and g, let "f≤g" mean that "f agrees with g on all values for which f is defined".

It is usual to assume some properties of the domain, such as the existence of limits of chains (see cpo) and a bottom element. The partial order of partial functions has a bottom element, the totally undefined function. It also has least upper bounds of chains. Various additional properties are often reasonable and helpful: the article on domain theory has more details.

We are particularly interested in the continuous functions between domains. These are functions that preserve the order structure, and that preserve least upper bounds.

In this setting, types are denoted by domains, and the elements of the domains roughly capturing the elements of the types. A denotational semantics is given to a program phrase with free variables in terms of a continuous function from the denotation of its environment type to the denotation of its type. For example, the phrase n*g(n-1) has type Nat, and it has two free variables: n, of type Nat, and g of type Nat -> Nat. Thus its denotation will be a continuous function

${\displaystyle \mathbb {N} \times (\mathbb {N} \rightharpoonup \mathbb {N} )\to \mathbb {N} }$.

Under this order on the partial functions, the denotation of the factorial program can be given as follows. First, we must develop denotations for the basic constructions such as if-then-else, ==, and multiplication. One must also develop a denotational semantics for function abstraction and application. The program phrase

λ n:N. if (n==0)then 1 else n*g(n-1)

can then be given a denotation as a continuous function between the domains of partial functions

${\displaystyle F:(\mathbb {N} \rightharpoonup \mathbb {N} )\to (\mathbb {N} \rightharpoonup \mathbb {N} )}$.

The denotation of the factorial program is defined to be the least fixed point of this function F. It is thus an element of the domain ${\displaystyle (\mathbb {N} \rightharpoonup \mathbb {N} )}$.

The reason that such a fixed point exists is because F is a continuous function. A version of Tarski's fixed point theorem says that continuous functions on domains have least fixed points.