Recommender systems employ machine learning models to learn from historical data to predict the preferences of users. Deep neural network (DNN) models such as neural collaborative filtering (NCF) are increasingly popular. However, the tangibility and trustworthiness of the recommendations are questionable due to the complexity and lack of explainability of the models. To enable explainability, recent techniques such as ACCENT and FIA are looking for counterfactual explanations that are specific historical actions of a user, the removal of which leads to a change to the recommendation result. In this work, we present a general framework for both DNN and non-DNN models so that the counterfactual explainers all belong to it with specific choices of components. This framework first estimates the influence of a certain historical action after its removal and then uses search algorithms to find the minimal set of such actions for the counterfactual explanation. With this framework, we are able to investigate the relationship between the explainers and recommenders. We empirically study two recommender models (NCF and Factorization Machine) and two datasets (MovieLens and Yelp). We analyze the relationship between the performance of the recommender and the quality of the explainer. We observe that with standard evaluation metrics, the explainers deliver worse performance when the recommendations are more accurate. This indicates that having good explanations to correct predictions is harder than having them to wrong predictions. The community needs more fine-grained evaluation metrics to measure the quality of counterfactual explanations to recommender systems.