Java - 递归 - 线程 "main"java.lang.StackOverflowError 中的异常

Question

我在尝试打印文件依赖项列表时遇到了问题。

关于该计划:

1. 扫描给定的 *.c 文件以查找依赖项，更具体地查找“#include “%”
2. 找到这些文件并递归扫描它们的依赖关系
3. 所有信息都存储在一个 ConcurrentHashMap(key:String value:Linked List of Strings) 表中，其中 Linked List of Strings 包含依赖项列表。
4. 处理完某个文件后，我得到了以下哈希表:

Answer 1

如果我理解 map 输出的意思，那么您的头文件中有一个循环(#include 循环)。

i_50.h=[i_35.h, i_28.h, i_45.h, i_44.h, i_46.h],
....
i_35.h=[i_50.h, i_51.h]

这意味着您的依赖关系是一个图形而不是 DAG。这反过来意味着简单的递归遍历将行不通。

从表面上看，您正在尝试进行图形遍历，但由于某种原因，您的循环检测/避免不起作用，并且您的算法进入“无限”递归。

---

看完代码，我想我能看出问题出在哪里了。在第一种方法中，您检查依赖项是否已打印，然后在 alreadyPrinted 映射中设置条目以说明它已打印。但是您随后不考虑 继续打印它。然后在第二种方法中，每次递归到第一种方法时，您都会(莫名其妙地)创建一个新的 alreadyPrinted 映射。换句话说，你避免循环的逻辑被打破了。

---

我建议您阅读您最喜欢的“数据结构和算法”教科书，并在索引中查找“图遍历”，而不是为您修复代码。或者，这是我在一些在线讲义中找到的页面:

• > http://underpop.online.fr/j/java/algorithims-in-java-1-4/ch05lev1sec8.htm

维基百科和其他地方也有关于图遍历的资料。 Google 搜索“java 递归图遍历”，并尝试找到对您有意义的内容。

一般的算法是这样的:

    traverse(Node node):
        traverse_0(node, new Set<Node>())

    traverse_0(Node node, Set<Node> visited):
        if (visited.contains(node)) 
            return
        visited.add(node)
        for (Node child: node.children) 
            traverse_o(child, visited)