如何防止无限递归循环

Question

我似乎想不出解决我的递归问题的方法。所以我有这个 Version 对象，它包含对它所依赖的其他版本对象的引用列表。

版本

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

当我检索这个对象时，我还必须检索它的依赖关系以及依赖关系的依赖关系，直到最终结束，这看起来像这样

VersionDto

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

这是我检索版本的递归函数

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

但是我运行遇到了一个可能的无限循环问题，在这种情况下，一个版本可能依赖于其中一个嵌套依赖项，例如 v1 -> v2 -> v4 -> v1 导致无限重复。

知道如何解决和防止这个无限循环吗，这样如果版本全部就绪发生得更早，它应该跳过它吗？

编辑：使用全局列表的解决方案

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

Answer 1

确保递归函数结束的最好方法是设置一个或多个条件。您必须有一个，以确保它不会进入无限循环。

我建议做一个数组或者列表，存储所有已经访问过的节点，这样当运行递归函数你可以知道你已经访问过一个节点，并且可以移动到另一个。

Answer 2

希望这对您有所帮助。

如果 v1 的依赖关系始终相同，那么它就可以工作。

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

Answer 3

使用 Jackson 库可以非常有效地解决无限递归循环问题。 Jackson 库会派上用场，尤其是当您使用 Hibernate/JPA 进行持久化时。即，@JsonManagedReference 和@JsonBackReference 注释将适用于您的案例。

您没有显示您的 JPA 实体代码，所以我无法告诉您应该将这些注释放在何处。但是，

提供了如何使用它们的一个很好的例子

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

希望你觉得有用！

如何防止无限递归循环

How to prevent infinite recursion loop

java

recursion

infinite-recursion