python - 递归计算链表中的节点数

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所以你不妨用上面所示的更简单的方式来编写它。