Abstract: In this paper we present a new approach to the inductive inference of recursive theories. A separate-and-parallel-conquer search strategy is adopted to interleave the learning of clauses of mutually recursive predicate definitions. Problems caused by the non-monotonicity of the consistency property are solved by reformulating the currently learned theory before adding a new clause. The proposedapproach is implemented in a new system, named ATRE, which is characterized by an object-centered representation of training examples and by the use of seed objects.