以递归方式返回链表中的元素数

我在名为ImageNode的类中有一个名为Image的类，该类传递了头（，这个 - 链表的起点）。我以为我的代码会递归地遍历每个节点，增加计数，然后当它在最后返回计数，不幸的是不。我哪里错了？以递归方式返回链表中的元素数

private int countRec() { 
    int count = 1; 
    ImageNode node = this; 

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

    return count; 
}

来源

2014-09-19 Dan_ENZ

'int count = 1;'你总是将计数设置为1，递增并返回它。 – TheLostMind 2014-09-19 06:16:29

计数不应该是您的方法的局部变量 – zerocool 2014-09-19 06:16:49

您正在通过方法调用重置计数，并且每个countRec（）方法都会将计数设置为'1'，将节点设置为'this'每次都会产生相同的结果 – 2014-09-19 06:18:27

你忽略的countRec()的结果 - 而你迭代递归调用中，击败目的。（你也在同一个对象上进行递归调用，没有参数，也没有状态变化......所以不能做任何好事。）我的递归方法将基于以下设计：

如果下一个节点为空，那么列表的大小为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（1）空间，并在需要时更新它。我希望这个问题是基于教育需求而不是真正的代码 - 在生产代码中，您只需使用已提供的集合。

来源

2014-09-19 06:19:03

谢谢！那完美的作品，从来没有用过？之前，有点困惑至于什么？和：正在做 – 2014-09-19 06:24:15

@Dan_ENZ：它是条件运算符 - 它在'？'之前检查条件，然后计算第二个参数或第三个参数。会链接到一些文件，但现在必须下车... – 2014-09-19 06:26:00

不用担心会有一个看看它。谢谢您的帮助。 – 2014-09-19 06:27:55

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

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

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

来源

2014-09-19 06:24:27

递归函数在使用进一步调用的结果来解决他的问题（如数学上的归纳步骤）时非常有用。您的函数没有使用countRec()调用的任何回报，并且您仍然试图在没有递归帮助的情况下解决问题。您可以使用它解决它，如：

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

当然，因为我们讲述让你的代码更好，你甚至不会需要使用这个node变种，只是在做：

private int countRec() { 

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

希望有帮助。

来源

2014-09-19 06:32:11

以递归方式返回链表中的元素数

回答

相关问题