英文:
How to break from multiple instances calls of a recursive function?
问题
我正在创建一个递归函数，用于在图中查找两个节点之间的路径。只有在节点没有重复时才会找到路径。如果一个节点连接到两个其他节点，会创建两个递归函数的实例。如果从它们中都有正确的路径，最后找到的路径将替换第一个路径（如 this.nodePath = clonedNodePath;）。当找到路径时，如何从所有递归调用中退出，而不仅仅是退出当前递归调用实例？（我不想抛出异常）
private void process(String currentNodeId, List<String> currentNodePath) {
FlowNode currentFlowNode = modelInstance.getModelElementById(currentNodeId);
List<String> clonedNodePath = new ArrayList<>(currentNodePath);
if (currentFlowNode == null || clonedNodePath.contains(currentNodeId)) return;
clonedNodePath.add(currentNodeId);
if (currentNodeId.equals(finishNodeId)) {
this.nodePath = clonedNodePath;
return;
}
currentFlowNode.getOutgoing()
.stream()
.forEach(sequenceFlow -> process(sequenceFlow.getTarget().getId(), clonedNodePath));
}
英文:
I am creating a recursive function that will find the path between two nodes in a graph. The path will only be found if a node is not duplicated. If a node is connected to two other nodes two instances of the recursive function will be created. If there is a correct path from both of them the last found path will be set instead of the first one (line this.nodePath = clonedNodePath;). How can I break from all recursive calls when a path is found and not only break from the current recursive call instance? (I don't want to throw an exception)
private void process(String currentNodeId, List<String> currentNodePath) {
FlowNode currentFlowNode = modelInstance.getModelElementById(currentNodeId);
List<String> clonedNodePath = new ArrayList<>(currentNodePath);
if (currentFlowNode == null || clonedNodePath.contains(currentNodeId)) return;
clonedNodePath.add(currentNodeId);
if (currentNodeId.equals(finishNodeId)) {
this.nodePath = clonedNodePath;
return;
}
currentFlowNode.getOutgoing()
.stream()
.forEach(sequenceFlow -> process(sequenceFlow.getTarget().getId(), clonedNodePath));
}
答案1
得分: 1
主要问题在于对出边进行迭代。
你选择使用Java8的流（stream）来处理，但这样做不允许你提前终止迭代（吹毛求疵地说，你可以绕过那个“限制”，但那样很繁琐）。
将其改为经典的for循环，你的问题就大部分会消失。让你的process()方法返回一个布尔值表示成功与否，在循环内部，如果返回true，在这个process()递归调用外部也返回true。
甚至更优雅的做法是：让process()方法返回一个Optional<List<String>>，在失败的情况下为空，在成功的情况下填充路径。这样你还可以摆脱通过this.nodePath进行通信。并且process()方法的名称最好改为findPath()。
附注：我知道使用流（stream）现在很流行，但在有些情况下它们并不是合适的工具。
英文:
The main problem lies in the iteration over the outgoing egdes.
You chose to do it with a Java8 stream, and this doesn't allow you to do an early abort (nitpicking: you can work around that "limitation", but that's clumsy).
Change that to a classical for loop, and your problem mostly disappears. Have your process() method return a boolean success indication, and inside the loop, if it gives true, return true out of this process() recursive call.
Or even more elegant: have the process() method return an Optional<List<String>>, either empty in case of failure, or filled with the path if successful. Then you also get rid of communicating via this.nodePath. And the process() method would better be named findPath().
P.S. I know it's en vogue to use streams, but there are situations where they're simply not the appropriate tool.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论