  Ordinary orthogonal polynomials are uniquely characterized by the three term
recurrence relations up to an overall multiplicative constant. We show that the
newly discovered M-indexed orthogonal polynomials satisfy 3+2M term recurrence
relations with non-trivial initial data of the lowest M+1 members. These
include the multi-indexed orthogonal polynomials of Laguerre, Jacobi, Wilson
and Askey-Wilson types. The M=0 case is the corresponding classical orthogonal
polynomials.
