递归地返回链表中的元素数

Question

我在一个名为ImageNode的类中有以下递归方法，该方法是从一个称为Image的类传递头（this-链表的开头）。我想我的代码会递归地遍历每个节点，增加计数，然后当它在最后返回计数时，不幸的是没有。我哪里错了？

private int countRec() {
    int count = 1;
    ImageNode node = this;
    if (node.next != null ){
        node = node.next;
        count++;
        countRec();
    }
    return count;
}

Answer 1

您忽略了countRec()的结果，并且在递归调用中迭代，从而破坏了目的。（你也在对同一个对象进行递归调用，没有参数，状态也没有变化……所以这不会有任何好处。）我的递归方法基于以下设计：

• 如果下一个节点为null，则列表的大小为1
• 否则，大小为1+从下一个节点开始的大小

因此：

private int countRec() {
    return next == null ? 1 : 1 + next.countRec();
}

当然，这不允许长度为0的列表。。。您可能希望将列表的概念与节点分离，在这种情况下，列表类将具有以下内容：

public int count() {
    return head == null ? 0 : head.countRec();
}

其中head的值是对头部节点的引用（如果存在），或者null的值是针对头部节点的参考（否则）。

当然，这将是时间和空间中的O（n）。你可以使用迭代而不是递归来获得O（1）空间，只需将列表的大小作为列表中的一个实例变量，并在需要时进行更新，就可以获得O（2）时间。不过，我希望这个问题是基于教育需求，而不是实际代码-在生产代码中，你只需要使用已经提供的集合。

Answer 2

递归函数的定义是，它是根据自身定义的：即，如果列表为空，则列表中的元素数等于0；否则它等于1+列表的其余元素的计数。

上面定义的斜体部分是进行函数调用的地方。

private int countRec(ImageNode node) {
    if (node == null) {
        return 0;
    } else {
        return 1 + countRec(node);
    }
}

Answer 3

递归函数在使用进一步调用的结果来解决问题时很有用（就像数学上的归纳步骤）。您的函数没有使用countRec()调用的返回进行任何操作，并且您仍在尝试在没有递归帮助的情况下解决问题。你可以通过使用它来解决它，如：

if(node.next != null)
{
    node = node.next;
    count = countRec()+1;
}
return count;

当然，既然我们说的是让你的代码变得更好，你甚至不需要使用这个nodevar，只需要做：

private int countRec() {
    if (this.next != null )
        return (this.next.countRec())+1;
    return 1;
}

希望能有所帮助。