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

Question

基本上是尝试在 Python 中重写递归函数而不使用辅助函数。代码几乎相同，但我得到了很多意想不到的结果。谁能告诉我我错过了什么？

这是工作代码：

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 运行s 时，它会创建一个新的 root_index = [0] 并将其交给 reconstructFromRange，它会在 root_index 中发生变异root_index[0] += 1.

行

在您的编辑中，您将创建 root_index=[0] 移动到 reconstructBst 的 默认参数 。它不是在 reconstructBst 运行时创建的，而是在它的 DEFINITION 时创建的；将其视为属于函数本身的对象。现在每 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]    
     ...

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

Rewriting recursive python function without helper causes it to stop working

python

algorithm

recursion

binary-search-tree