通过递归方法计算图中的顶点，最后返回一个整数

Question

我目前正在做一个赋值，在这个赋值中，我需要使用一个数组中顶点相连的图。我需要计算图中的每个节点，并尝试递归地这样做。

public int getAmountOfNodes(Node node, int countFrom){
        for (Node n : node.children) {
            if (n != null) {
                countFrom++;
                getAmountOfNodes(n, countFrom);
            }
        }
        return countFrom;
    }

到目前为止，我一直在尝试这样做，但结果并不像我所希望的那样。我试图调试代码，似乎计数是按预期的方式工作的（计数每个非空节点）。问题似乎是，当递归堆栈结束时，比如countFrom达到了5，并且该方法返回5，堆栈中的下一个递归调用就不会“记住这一点”，而是返回它之前计算过的数量，比如4。这意味着最终返回的整数仅为第一个递归调用计数的数量，即第一个节点的子节点数量。

我一直在尝试谷歌搜索，但没有找到一个我可以使用的答案。我还在学习递归，所以请原谅我面前可能出现的任何愚蠢的错误。

任何帮助都将不胜感激，并将提供所需的任何信息。谢谢

Answer 1

堆栈中的下一个递归调用不“记住这个”，并返回它以前计算过的数量

因为您没有使用调用返回的值：

getAmountOfNodes(n, countFrom);

每个调用都会创建一个新的递归分支，但返回值不受影响。

还有几个小问题：

• 您不需要第二个参数，只需返回累计值，而不需要维护冗余参数

public int getAmountOfNodes(Node node) {
    int count = 1; // we sould count THIS node
    for (Node child : node.children) {
        if (child == null) continue;
                
        count += getAmountOfNodes(child);
    }
    return count;
}

Answer 2

在你的代码中，你只是简单地将计数从原始int传递到每个调用，而不用费心从最后一个调用更新它的值。这就是为什么你最后一次迭代没有得到最终结果，这也解释了为什么在你的例子中你得到4而不是5。

在设计递归方法时，应始终考虑所有的基本情况和递归情况。在本例中，基本情况（结束递归迭代的场景）可能是n==null，而递归步骤（使您朝着目标前进的操作）是count变量的增量及其在递归调用后的更新。

您的代码应该看起来像这样。

public int getAmountOfNodes(Node n, int countFrom){
    
    //Checking whether n actually represents a node or not; if it's not then the number of nodes stays the same
    if (n == null){
        return countFrom;
    }

    //If n represents a node then the numer of nodes must be incremented
    countFrom++;

    //Aplying the previous logic to each children of n
    for (Node child: n.children) {
        //Doesn't matter whether child is null or not; if child is null then countFrom stays the same 
        //otherwise it's incremented according to the number of nodes met by the recursive call
        countFrom = getAmountOfNodes(child, countFrom);
    }

    return countFrom;
}

Answer 3

您可以使用广度优先搜索，这是在没有递归调用的情况下实现的。如果当前节点的每个子节点n是第一次被访问，则会将其添加到FIFO队列中。检查当前节点的子节点后，将从队列中删除另一个当前节点。