java - 如何防止无限递归循环

Question

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

版本

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

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

版本Dto

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

标签： javarecursioninfinite-recursion

Answer 1

希望这可以帮助。

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

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