在没有助手的情况下重写递归python函数会导致它停止工作

Question

基本上，a试图在Python中重写递归函数，而不使用helper函数。代码几乎相同，但我得到了很多意想不到的结果。谁能说出我遗漏了什么

以下是工作代码：

class BST:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def reconstructBst(preOrderTraversalValues):
    root_index = [0]
    return reconstructFromRange(float("-inf"), float("inf"), preOrderTraversalValues, root_index)
    
def reconstructFromRange(low, high, values, root_index):
    if root_index[0] == len(values):
        return None
    
    root_value = values[root_index[0]]
    if root_value < low or root_value >= high:
        return None
    
    root_index[0] += 1
    left_subtree = reconstructFromRange(low, root_value, values, root_index)
    right_subtree = reconstructFromRange(root_value, high, values, root_index)
    return BST(root_value, left_subtree, right_subtree)

以下是非工作重写：

class BST:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        self.right = right


def reconstructBst(preOrderTraversalValues, low=float("-inf"), high=float("inf"), root_index=[0]):

    if root_index[0] == len(preOrderTraversalValues):
        return None
    
    root_value = preOrderTraversalValues[root_index[0]]
    if root_value < low or root_value >= high:
        return None
    
    root_index[0] += 1
    left_subtree = reconstructBst(preOrderTraversalValues, low, root_value, root_index)
    right_subtree = reconstructBst(preOrderTraversalValues, root_value, high, root_index)
    return BST(root_value, left_subtree, right_subtree)

以下是大多数测试用例出现的错误：

 list index out of range
 Traceback (most recent call last):
  File "/tester/json_wrapper.py", line 30, in getActual
    result = program.reconstructBst(preOrderTraversalValues)
  File "/tester/program.py", line 13, in reconstructBst
    root_value = preOrderTraversalValues[root_index[0]]
IndexError: list index out of range

Answer 1

在原始代码中，每当reconstructBst运行时，它都会创建一个新的root_index = [0]并将其提供给reconstructFromRange，它会在root_index[0] += 1行中的root_index发生突变

在编辑中，您将创建root_index=[0]移动到了reconstructBst的默认参数。它不是在reconstructBst运行时创建的，而是在其定义时创建的；将其视为属于函数本身的对象。现在每当reconstructBst运行时，它都会更改其root_index值

我敢打赌root_index在第一次运行后不再是[0]，这会导致问题，因为preOrderTraversalValues仅以1值开始，并且只能由preOrderTraversalValues[0]索引

简单的解决方法是使用虚拟不可变值来指定何时创建可变对象：

def reconstructBst(preOrderTraversalValues, low=float("-inf"), high=float("inf"), root_index=None):
     if root_index == None:
         root_index = [0]    
     ...