CODEWITHSUNDEEP
javarecursioninfinite-recursion
Dean Strydom
Dean Strydom

Reputation: 295

How to prevent infinite recursion loop

I can't seem to come up with a solution to my recursion problem. So I have this Version object that holds a list of references to other version objects it is dependent on.

Version

{
  "id": "id1",
  "version": "1",
  "dependencies": [
    {
      "id": "id2"
    },
    {
      "id": "id3"
    }
  ]
}

When I retrieve this object I also have to retrieve it's dependencies as well the dependency's dependencies until there is an eventual end, which would look something like this

VersionDto

{
  "id": "id1",
  "version": "1",
  "dependencies": [
    {
      "id": "id2",
      "version": "2",
      "dependencies": [
        {
          "id": "id4",
          "version": "4",
          "dependencies": []
        }
      ]
    },
    {
      "id": "id3",
      "version": "3",
      "dependencies": []
    }
  ]
}

This is my Recursive function to retrieve a version

public VersionDto getVersion(String id)
{
    //Retrieves from database
    Version version = versionDAO.getVersion(id);

    //Convert to Dto (basic fields)
    VersionDto versionDto = new VersionDto(version);

    //Recursivly retrieve dependencies 
    for (Map<String, String> dep : version.getDependencies()) {
        VersionDto dto = new VersionDto();

        //Recursive call
        dto = getVersion(dep.get("id"));
        versionDto.getDependencies().add(dto);
    }

    return versionDto;
}

However I run into the problem of a possible infinite loop in the case where a version could be a dependency to one of the nested dependencies such that v1 -> v2 -> v4 -> v1 causing a infinite repeat.

Any idea how I could solve and prevent this infinite loop, so that if the version all ready occurred earlier it should just skip it?

Edit: Solution using global list

public VersionDto getVersion(String id)
{

    //Check global list contains version
    if (visited.contains(id)) {
        return null;
    }

    visited.add(docId);

    //Retrieves from database
    Version version = versionDAO.getVersion(id);

    //Convert to Dto (basic fields)
    VersionDto versionDto = new VersionDto(version);

    //Recursivly retrieve dependencies 
    for (Map<String, String> dep : version.getDependencies()) {
        VersionDto dto = new VersionDto();

        //Recursive call
        dto = getVersion(dep.get("id"));
        if(dep!= null) {
        versionDto.getDependencies().add(dto);
        }
    }

    return versionDto;
}

Upvotes: 0

Views: 6564

Answers (3)

Monica Lavale
Monica Lavale

Reputation: 80

The infinite recursive loop problem can be very efficiently solved using Jackson libraries. The Jackson libraries comes in handy, particularly, if you are using Hibernate/JPA for persistence. Namely, the @JsonManagedReference and @JsonBackReference annotations would apply to your case.

You have not shown your JPA Entity code, so I can't tell you where exactly you should put these annotations. But, a good example of how to use them is available at

http://springquay.blogspot.com/2016/01/new-approach-to-solve-json-recursive.html

Hope you find it useful!

Upvotes: 1

Esha
Esha

Reputation: 151

hope this helps.

if the dependency of v1 is going to be same always then it works. 

        dto = getVersion(dep.get("id"));
        //check if the versionDto contains the dependecy already then break the loop here
        versionDto.getDependencies().add(dto);```

Upvotes: 1

Enrico Cortinovis
Enrico Cortinovis

Reputation: 861

The best way to be sure that the recursive functions will end, is to put one, or more conditions. You must have one, to make sure that it won't go in an infinite loop.

I would suggest to make an array or a list, where you store all the already visited nodes, so when running the recursive function you can be aware that you have already visited a node, and can move to another one.

Upvotes: 1

Related Questions