  This paper provides a general account of the notion of recursive program
schemes, studying both uninterpreted and interpreted solutions. It can be
regarded as the category-theoretic version of the classical area of algebraic
semantics. The overall assumptions needed are small indeed: working only in
categories with "enough final coalgebras" we show how to formulate, solve, and
study recursive program schemes. Our general theory is algebraic and so avoids
using ordered, or metric structures. Our work generalizes the previous
approaches which do use this extra structure by isolating the key concepts
needed to study substitution in infinite trees, including second-order
substitution. As special cases of our interpreted solutions we obtain the usual
denotational semantics using complete partial orders, and the one using
complete metric spaces. Our theory also encompasses implicitly defined objects
which are not usually taken to be related to recursive program schemes. For
example, the classical Cantor two-thirds set falls out as an interpreted
solution (in our sense) of a recursive program scheme.
