递归算法和 StackOverFlow 错误

Question

我一直在编写递归算法，以便通过不同的节点并分析有向无环图中的所有路径。问题是，在将一些新数据引入算法后，我收到此消息 Exception in thread "AWT-EventQueue-0" java.lang.WhosebugError。我查看了有关此的不同问题，似乎错误是因为内存不足。谁能帮我解决这个问题？

这里我加一张递归算法的图：

public boolean checkduration(Node node, double dur, int freq){
    boolean outcome=true;
    currentPath.add(node);
    if((dur>minduration)&&(node.getRep()<=node.getMaxRep())){
        ArrayList<Node> clone = (ArrayList<Node>) currentPath.clone();
        currentPath2=clone;
        failingPaths.add(new ImmutableTriple<Double,Integer, ArrayList<Node>> (dur,freq,currentPath2)); 
        currentPath.remove(node);
        return false;
    }
    node.setRep(node.getRep()+1);

    for(int i=0;i<node.getEdge().size();i++){
        if(!checkduration(node.getEdge().get(i).previousNode,dur+node.getEdge().get(i).timeRelation, freq+node.getEdge().get(i).frequency)){
            outcome=false;  
        }
    }
    currentPath.remove(node);
    node.setRep(node.getRep()-1);
    return outcome;
 }

错误似乎是在 (if(!checkduration(node.getEdge().get(i).previousNode,dur+node.getEdge().get(i).timeRelation, freq+node.getEdge().get(i).frequency))) 的情况下，但我不明白为什么它适用于某些数据，而且并不总是如此，因为没有太多信息被更改。

任何意见、建议都会很有帮助。感谢大家

Answer 1

发生 WhosebugError 是因为您递归的次数太多。如果递归调用太多，则意味着您的终止条件存在缺陷或不正确的假设。这是您的终止条件：

(dur > minduration) && (node.getRep() <= node.getMaxRep())

由于你的问题没有提供足够的信息让我们进一步分析你的图或节点，我建议你仔细看看这个终止条件，并确保图的每一次遍历最终都能满足这种情况。

调试器的使用还可以帮助您逐步遍历并查看循环发生在何处，以及为什么不满足终止条件。

Answer 2

你的图遍历似乎效率低下，因为你在计算每个节点的重复次数，你访问了多少次，你通过添加一些 maxRep

来限制你的努力

您所需要的只是一组已访问的节点，而不是在您访问每个节点时增加一个计数器。

你的DAG有很多根吗？是保证没有循环，还是需要检测循环？

另请注意，您不需要克隆路径。

递归算法和 StackOverFlow 错误

Recursive algorithms and StackOverFlow Error

java

stack-overflow

recursion