递归计算链表中的节点数

Question

问题：返回链接列表中的节点数

我最近在学习递归。我知道如何使用迭代来解决这个问题，但我坚持使用递归的方法。下面是我的代码，它总是返回1，而不是链表的实际计数。我想不出这个问题，希望有人能帮我。我怎样才能解决这个问题

def numberOfNodes(head):
   total_node = 0
   return __helper(total_node, head)


def __helper(total_node, head):
   if not head:
      return total_node += 1
   __helper(total_node, head.next)
   return total_node

Answer 1

对于这类事情来说，递归是一个糟糕的选择（增加了开销，并有可能因为没有好的理由而破坏调用堆栈），但是如果您确实出于教育目的使用它，那么最简单的方法是将总数向上传递到调用堆栈，而不是向下传递：

def linked_list_len(head):
   return linked_list_len(head.next) + 1 if head else 0

基本上，在head节点存在的地方，每帧添加1，然后使用下一个节点再次调用该函数。基本情况是head是None

在一些提供tail call optimization的语言中，可以避免子递归调用每帧返回的变量发生+ 1工作。这允许编译器或解释器将递归转换为循环，避免堆栈溢出。代码如下所示（与您的方法类似，不同之处在于+ 1是在递归调用中添加的）：

def linked_list_len(head, total=0):
    return linked_list_len(head.next, total + 1) if head else total

但是Python doesn't support TCO所以您可以用上面所示的更简单的方法编写它