java - 使用递归计算从“cur”节点到列表末尾的值字段在min和max之间的节点数

Question

我对解决方案的尝试，我知道这是不对的，因为程序的输出不正确。我究竟做错了什么？

我有一个内部节点类，每个都有值字段。此方法应返回具有 ints min 和 max 之间的值字段的节点数。

//---------------- countInRange( Node, int, int ) ------------------
private int countInRange( Node cur, int min, int max )
{
    if(cur == null)
        return 0;
    else {
        if(cur.value >= min && cur.value <= max)
            return (1+ countInRange(cur.next, min, max));
    }
    return 1;
}

Answer 1

问题是只有在值在范围内时才进行递归调用，否则就假装列表的其余部分在范围内只有一个元素。

无论值是否在范围内，您都需要进行递归调用。唯一的区别是在返回结果之前是否将结果加 1。

Answer 2

您的递归方法有三种路径：

1. 该节点为空，因此它不能在范围内，也不能有任何子节点。返回 0 似乎是合理的。
2. 该节点不为空，并且在范围内。在子节点上返回 1 + 递归看起来不错。
3. 该节点不为空，并且不在范围内。我不会返回 1，而是在子节点上返回 0 + 递归。

如果您重写并稍微注释一下代码，问题就会变得清晰（此代码在功能上与您的代码相同，但突出了问题）：

//---------------- countInRange( Node, int, int ) ------------------
private int countInRange( Node cur, int min, int max )
{

    if(cur == null) {
    // Node is null, end recursion
        return 0;
    }
    if(cur.value >= min && cur.value <= max) {
    // Node is in range, recurse and add 1
            return (1+ countInRange(cur.next, min, max));
        }
    } else { 
    // Node is not in range, recurse
        return 1; // ?!
    }
}