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

调用 self.function_name()

时不需要显式传递 self

return self._size(0, self._root)

Answer 2

存在以下问题：

_size是在__init__函数中设置的实例属性。这意味着 self._size 将引用该属性，而不是具有相同名称的 class 方法。这是您收到错误的原因。您应该为这两件事使用不同的名称：一个名称用于整数大小，另一个名称用于递归计算大小的辅助函数。我建议使用 _sizerecur 作为辅助方法的名称——并将在下一点中以这种方式引用它：
self._sizerecur(self, 0, self._root) 不应将 self 作为参数传递，因为该参数已经通过这种类型的 method-call 语法获得了 self 的值（点符号中的前缀用作该参数）。
if current_node != None 应该在其块中包含该代码的所有其余部分，否则当 current_node 为 None 时 current_node.left 仍将被计算，导致错误。
大小计算不正确。本质上有两种方法可以实现这种递归，而您的代码似乎混合了这两种方法，使其不正确：当您将当前大小作为参数传递给递归调用，并调用 returns 更新值时，您不应该添加到你已经传递给它的原始大小。通过这样做，你有重复计算。你应该只是 assign 它回到你的变量（而不是添加到它），或（更好），而不是将当前计数作为参数传递，但让每个递归调用从 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 参数的情况下实现此递归函数。不要在 recur 更深入时更新计数器，而是在获得 out 递归时更新它：

    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

Python 带辅助函数的递归函数

Python recursive function with helper function

python

recursion

binary-search-tree