  We construct fast algorithms for evaluating transforms associated with
families of functions which satisfy recurrence relations. These include
algorithms both for computing the coefficients in linear combinations of the
functions, given the values of these linear combinations at certain points,
and, vice versa, for evaluating such linear combinations at those points, given
the coefficients in the linear combinations; such procedures are also known as
analysis and synthesis of series of certain special functions. The algorithms
of the present paper are efficient in the sense that their computational costs
are proportional to n (ln n) (ln(1/epsilon))^3, where n is the amount of input
and output data, and epsilon is the precision of computations. Stated somewhat
more precisely, we find a positive real number C such that, for any positive
integer n > 10, the algorithms require at most C n (ln n) (ln(1/epsilon))^3
floating-point operations and words of memory to evaluate at n appropriately
chosen points any linear combination of n special functions, given the
coefficients in the linear combination, where epsilon is the precision of
computations.
