带有助手函数的Python递归函数

Question

我正在编写一个函数来确定二进制搜索树的大小。我尝试了一种递归的方式：

def size(self) -> int: #self representing the whole bst
        """Return number of nodes contained in the tree."""

        if self._root is None:
            return 0
        else:
            return self._size(self, 0, self._root)

def _size(self, current_size, current_node):

        if current_node != None:
            current_size += 1
        if current_node.left != None:
                current_size += self._size(current_size, current_node.left)
        if current_node.right != None:
                current_size += self._size(current_size, current_node.right)

        return current_size

但是，这会为行抛出一个TypeError：

return self._size(self, 0, self._root)
TypeError: 'int' object is not callable

我对递归函数很陌生，不知何故我无法真正了解助手函数和原始函数应该如何协同工作，以及我的方法是否正确。因此，任何帮助都是非常感谢的。

以下是这些类的代码：

from typing import Any


class TreeNode:

    def __init__(self, key: int, value: Any, right: 'TreeNode' = None,
                 left: 'TreeNode' = None, parent: 'TreeNode' = None):
        """Initialize TreeNode.

        Args:
            key (int): Key used for sorting the node into a BST.
            value (Any): Whatever data the node shall carry.
            right (TreeNode, optional): Node to the right, with a larger key. Defaults to None.
            left (TreeNode, optional): Node to the left, with a lesser key. Defaults to None.
            parent (TreeNode, optional): Parent node. Defaults to None.
        """
        self.key = key
        self.value = value
        self.right = right
        self.left = left
        self.parent = parent


from tree_node import TreeNode


class BinarySearchTree:
    """Binary-Search-Tree implemented for didactic reasons."""

    def __init__(self, root: TreeNode = None):
        """Initialize BinarySearchTree.

        Args:
            root (TreeNode, optional): Root of the BST. Defaults to None.
        
        """
        self._root = root
        self._size = 0 if root is None else 1

Answer 1

有以下问题：

• _size是在__init__函数中设置的实例属性。这意味着self._size将引用该属性，而不是引用同名的类方法。这就是您所得到的错误的原因。对于这两件事，您应该使用不同的名称:一个用于整数大小，另一个用于递归计算大小的助手函数。我建议使用_sizerecur作为助手方法的名称--并将在下一点：

中以这种方式引用它。

• self._sizerecur(self, 0, self._root)不应将self作为参数传递，因为该参数已经通过这种方法调用语法获得self的值(点表示法中的前缀用作该参数)。

• if current_node != None应该在其块中包含其余的代码，否则当current_node为None时，仍将对current_node.left进行计算，从而导致错误。

• 大小没有正确计算。本质上有两种实现此递归的方法，您的代码似乎将这两种方法混合在一起，这使其不正确:当您将当前大小作为参数传递给递归调用，并且该调用返回更新后的值时，您不应该将添加到您已经传递给它的原始大小中。通过这样做，你就可以重复计算。应该将其赋值回变量(不添加变量)、或(更好)，不要将当前计数作为参数传递，而是让每个递归调用从0.

开始计数。

下面是保持现有current_size参数的更正：

    def size(self) -> int:
        if self._root is None:
            return 0
        else:
            return self._sizerecur(0, self._root) # don't pass self as arg

    # A distinct name for this method
    def _sizerecur(self, current_size, current_node):
        if current_node:
            current_size += 1
        if current_node.left:
            # don't ADD again to current size
            current_size = self._sizerecur(current_size, current_node.left)
        if current_node.right:
            current_size = self._sizerecur(current_size, current_node.right)

        return current_size

但是，如前所述，更好的实践是在没有current_size参数的情况下实现这个递归函数。不要在更深的时间更新计数器，而是在退出递归的同时更新它：

    def size(self) -> int:
        if self._root is None:
            return 0
        else:
            return self._sizerecur(self._root)

    def _sizerecur(self, current_node):
        current_size = 0
        if current_node:
            current_size = 1
            if current_node.left:
                current_size += self._sizerecur(current_node.left)
            if current_node.right:
                current_size += self._sizerecur(current_node.right)
        return current_size

Answer 2

在调用self ()时，不需要显式传递self.function_name()

return self._size(0, self._root)