CODEWITHSUNDEEP
javarecursionarraylist
terbubbs
terbubbs

Reputation: 1512

Java - Using recursion to fill ArrayList

What I am trying to do:

  1. take all User from user.getFriends() and add it to temp
  2. then from user.getFriends(), check those User objects and their user.getFriends() and add those to temp
  3. temp cannot contain duplicates
  4. lastly.. it must be done through recursion

Here is the code:

public ArrayList<User> getRecommendations(User user, ArrayList<User> temp, int n)
{
    if (n<user.getFriends().size()){
        if (!temp.contains(user.getFriends().get(n))){
            temp.add(user.getFriends().get(n));
        }
        getRecommendations(user, temp, ++n);
    } return temp;
}

The gist of my problem is that I need to pass in a User object, add that objects friends (using getFriends()), and then get those object's friends (using the same method) all into a single ArrayList<User> using recursion...

From this method, I've been able to getFriends() of the initial User object being passed in. The recursion works fine in this case, but I cannot seem to figure out how I should design this code to get friends' of friends User objects.

Upvotes: 2

Views: 5611

Answers (1)

Markus Weninger
Markus Weninger

Reputation: 12638

So, you want every user just once, so a Set is the better choice.

A collection that contains no duplicate elements. More formally, sets contain no pair of elements e1 and e2 such that e1.equals(e2), and at most one null element.

What is done here is:

  1. Add every friend of the current user to the own set.
  2. Then for each friend, call the same method, and add the whole set returned from this.

You can sit down and draw a calling tree if this hard to understand. This often lights things up.

public Set<FacebookUser> getRecommendations(FacebookUser user, ArrayList<FacebookUser> alreadyVisited)
{
  Set<FacebookUser> friends = new HashSet<FacebookUser>();
  alreadyVisited.add(user);
  if (user.getFriends().size() > 0) {
      friends.addAll(user.getFriends());
      for(FacebookUser fbu : user.getFriends())
        if(!alreadyVisited.contains(fbu))
          friends.addAll(getRecommendations(fbu, alreadyVisited);
  }
  return friends;
}

If you really have to use an ArrayList, you can use something like the following, see the changes on the recursive getRecommendations call.

This now:

  1. Adds all friends of the current user to the list.
  2. Calls recursivly all friends of the current user, but adding only those which are not already in the list.

If you are new to Java, you may wonder what this ... .stream(). ... is. For this you may have a look at Oracle's Stream-documentation.

public ArrayList<FacebookUser> getRecommendations(FacebookUser user, ArrayList<FacebookUser> alreadyVisited)
{
  ArrayList<FacebookUser> friends = new ArrayList<FacebookUser>();
  alreadyVisited.add(user);
  if (user.getFriends().size() > 0) {
    friends.addAll(user.getFriends());
    for(FacebookUser fbu : user.getFriends())
      if(!alreadyVisited.contains(fbu))
        getRecommendations(fbu, alreadyVisited).stream().filter(x -> !friends.contains(x)).forEach(x -> friends.add(x));
  }
  return friends;
}

Upvotes: 1

Related Questions