An incomplete recursive circulant possesses virtually every advantage of a complete recursive circulant, including simple deadlock-free routing, a small diameter, a good support of parallel algorithms, and so on. It is natural to reconfigure a faulty recursive circulant into a maximum incomplete recursive circulant so as to lower potential performance degradation. For k > 2, the maximum incomplete subgraph problem is to identify a subgraph H of a graph G on k vertices having the maximum number of edges among all subgraphs on k vertices and is NP-complete. In this paper we identify maximum incomplete recursive circulants and use them as a tool to compute the exact wirelength of embedding recursive circulants into special classes of trees, such as k-rooted complete binary trees, k-rooted sibling trees, binomial trees, certain caterpillars and path. © 2015 World Scientific Publishing Company.