[ Recursive method for recommending friends ]

I am trying to write a recursive method to recommend friends as written here

We’ll take the approach of recommending all of our friends’ friends and our friends’ friends’ friends, and so on. This is a perfect opportunity to use recursion – we can create a getRecommendations method that takes a FacebookUser as an argument. The method should return an ArrayList that contains all of the friends of the FacebookUser that is passed into it plus the result of calling the same getRecommendations method on all of that FacebookUser’s friends. Be careful not to add anyone to the list of recommendations if they are already on it – that could lead to an infinite loop.

My code so far is:

ArrayList<FacebookUser> getRecommendations(FacebookUser example) {
    for (FacebookUser u : example.getFriends()) {
        if (recommendations.contains(u)) {
            return recommendations;
        } else {
            recommendations.add(u);
            for (FacebookUser a : recommendations) {
                getRecommendations(a);
            }
        }
    }
    return recommendations;
}

recommendations is an ArrayList:

ArrayList<FacebookUser> recommendations = new ArrayList<>();

And my getFriends() method is here:

ArrayList<FacebookUser> getFriends() {
    @SuppressWarnings("unchecked")
    ArrayList<FacebookUser> clone = (ArrayList<FacebookUser>) friends
            .clone();
    return clone;
}

Can someone give me a correct getRecommendations() method to use or point out what is wrong with my method?

Answer 1

In the else branch you don't need to call the recursive function again and again for all users in recommendations. Instead just call it for the newly found user that you just added to the recommendation list, like this:

else {
    recommendations.add(u);
    getRecommendations(u);
}

otherwise you will end up with an infinite loop as the text you included explains.