How to prevent infinite recursion loop

Question

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;
}

In a nutshell: you either have to mark already visited nodes, or to keep a record of the nodes you have already visited. In either case you have to check, on encountering a node, whether you have already visited it. — High Performance Mark
– High Performance Mark, Commented Nov 27, 2019 at 13:46
What behavior, specifically, do you want? Your data has a loop, and your code is dutifully following that loop. — Scott Hunter
– Scott Hunter, Commented Nov 27, 2019 at 13:46
You should have a structure of all the visited VersionDto and only add them if they are not on the list. Maybe if you add more information about the data structures I can provide further information. — Cristian Ramon-Cortes
– Cristian Ramon-Cortes, Commented Nov 27, 2019 at 13:46
In all recursive functions, you should have an end condition to avoid stackoverflow. Maybe you could keep a temporary structure that defines which dependencies has already been explored? — D. Lawrence
– D. Lawrence, Commented Nov 27, 2019 at 13:47

Enrico Cortinovis · Accepted Answer · 2019-11-27 13:49:23Z

1

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.

answered Nov 27, 2019 at 13:49

Enrico Cortinovis

8913 gold badges11 silver badges35 bronze badges

Sign up to request clarification or add additional context in comments.

2 Comments

Dean Strydom Over a year ago

I first passed a list through each node that would keep track what has been visited within that path which worked but still had some unnecessary looping. Then I tried a global list which worked much better thanks.

Enrico Cortinovis Over a year ago

Great! Glad to have helped!

Esha · Accepted Answer · 2019-11-27 13:51:33Z

1

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);```

answered Nov 27, 2019 at 13:51

Esha

1518 bronze badges

Comments

Monica Lavale · Accepted Answer · 2019-11-27 13:57:30Z

1

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!

answered Nov 27, 2019 at 13:57

Monica Lavale

807 bronze badges

1 Comment

Dean Strydom Over a year ago

Interesting, will have to look more into this. Thanks

Collectives™ on Stack Overflow

How to prevent infinite recursion loop

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related