In the 5G environment, the edge computing paradigm enables service providers to deploy their service instances on distributed edge servers to serve nearby end users with extremely low latency. This boosts the emergence of modern applications, like AR/VR, online gaming, and autonomous vehicles. Existing approaches find service provision strategies under the assumption that all the user requirements are known. However, this assumption may not be true in practice and thus the effectiveness of existing approaches could be undermined. Inspired by the great success of recommender systems in various fields, we can mine users’ interests in new services based on their similarities in terms of current service usage. Then, new service instances can be provisioned accordingly to better fulfil users’ requirements. We formulate the problem studied in this paper as a Cost-aware Recommendation-oriented Edge Service Provision (CRESP) problem. Then, we formally model the CRESP problem as a Constrained Optimization Problem (COP). Next, we propose CRESP-O to find optimal solutions to small-scale CRESP problems. Besides, to solve large-scale CRESP problems efficiently, we propose an approximation approach named CRESP-A, which has a theoretical performance guarantee. Finally, we experimentally evaluate the performance of both CRESP-O and CRESP-A against several state-of-the-art approaches on a public testbed.