第一次调用时只需要在递归函数中初始化一次空列表。如果对深度变量的调节不起作用

Question

我尝试了以下代码：

def split(arr,i=0):

    if i==0:
        print("hey")
        splitted=[]
        print('splitted initialized')


    a1=arr[:len(arr)//2]
    a2=arr[len(arr)//2:]
    if len(a1)>2:
        print("splitting "+str(a1))
        i+=1
        split(a1,i)
    else:
        print("not splitting "+str(a1))
        splitted.append(a1)

    if len(a2)>2:
        print("splitting "+str(a2))
        i+=1
        split(a2,i)
    else:
        print("not splitting "+str(a2))
        splitted.append(a2)

    return(splitted)

我在执行时遇到以下错误：

拆分([1,2,3,4,6,7,8,54,76,3,4,5,67,78,8,7,45,2]) 我希望空列表 "splitted" 在第 0 次初始化期间只初始化一次

hey
splitted initialized
splitting [1, 2, 3, 4, 6, 7, 8, 54, 76]
splitting [1, 2, 3, 4]
not splitting [1, 2]
Traceback (most recent call last):
  File "<pyshell#37>", line 1, in <module>
    split([1,2,3,4,6,7,8,54,76,3,4,5,67,78,8,7,45,2])
  File "\Documents\python_projects-20170821\python_projects\sorting_algorithms\merge_sort\merge_sort.py", line 15, in split
    split(a1,i)
  File "\Documents\python_projects-20170821\python_projects\sorting_algorithms\merge_sort\merge_sort.py", line 15, in split
    split(a1,i)
  File "\Documents\python_projects-20170821\python_projects\sorting_algorithms\merge_sort\merge_sort.py", line 18, in split
    splitted.append(a1)
UnboundLocalError: local variable 'splitted' referenced before assignment

我可以通过将 this 函数嵌套在另一个函数中来克服这个问题，如下所示：

下面的代码在调用时工作正常： 分离器（[1,2,3,4,6,7,8,54,76,3,4,5,67,78,8,7,45,2]）

def splitter(arr):
    splitted=[]
    def split(arr):
        a1=arr[:len(arr)//2]
        a2=arr[len(arr)//2:]
        if len(a1)>2:
            print("splitting "+str(a1))

            split(a1)
        else:
            print("not splitting "+str(a1))
            splitted.append(a1)

        if len(a2)>2:
            print("splitting "+str(a2))

            split(a2)
        else:
            print("not splitting "+str(a2))
            splitted.append(a2)

        return(splitted)
    return split(arr)

我只是想了解为什么我的第一个版本的代码不起作用？

Answer 1

那是因为你只在 i 大于零时才定义拆分。你可以试试

def split(arr,splitted=None):

    if splitted is None:
        print("hey")
        splitted=[]
        print('splitted initialized')

然后，当您调用您的函数时，您传递的是拆分后的列表而不是参数 i。

Answer 2

这个版本的 split 可能有用（但我更喜欢你的嵌套函数）

def split(arr, splitted=None):

    if splitted == None:
        print("hey")
        splitted = []
        print('splitted initialized')

    a1=arr[:len(arr)//2]
    a2=arr[len(arr)//2:]
    if len(a1)>2:
        print("splitting "+str(a1))
        split(a1, splitted)

    # the reset elided

注意 splitted 是如何沿着递归链向下传递的。

Answer 3

def split(arr,res,i=0):

    if i==0:
        print("hey")
        print('splitted initialized')


    a1=arr[:len(arr)//2]
    a2=arr[len(arr)//2:]
    if len(a1)>2:
        print("splitting "+str(a1))
        i+=1
        split(a1,res,i)
    else:
        print("not splitting "+str(a1))
        res.append(a1)

    if len(a2)>2:
        print("splitting "+str(a2))
        i+=1
        split(a2,res,i)
    else:
        print("not splitting "+str(a2))
        res.append(a2)

    return

那么输出就变成了

a=list()
split([1,2,3,4,6,7,8,54,76,3,4,5,67,78,8,7,45,2],a)
print(a)

Answer 4

这是解决该问题的另一种方法。我们从一个助手 cut_at_index 开始，它接受一个列表、一个索引 i 和 lambda，它将接收 "cut"[ 的 left 和 right 结果。 =26=]

现在让我们计划如何编写递归 split 函数

• base 情况是 len(ls) < 3: 我们 return 未修改输入的单例列表
• inductive 情况是长度 not 小于 3（即 >= 3），因此我们有一个大数组足以削减。我们称我们的 cut_at_index 为我们的 lambda 提供了新的 left 和 right 片段。然后我们在每个片段上调用 ​​split 并将结果简单地合并 (+)

作为此实施的结果，痛苦和苦难从程序中移除

def cut_at_index (ls, i = 0, k = lambda left, right: (left, right)):
  return k (ls[:i], ls[i:])

def split (ls):
  if len (ls) < 3:
    return [ ls ]
  else:
    return cut_at_index (ls, len (ls) // 2, lambda left, right:
      split (left) + split (right))

print (split ([ 1 ]))
print (split ([ 1, 2 ]))
print (split ([ 1, 2, 4 ]))
print (split ([ 1, 2, 3, 4 ]))
print (split ([ 1, 2, 3, 4, 5 ]))
print (split ([ 1, 2, 3, 4, 5, 6 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8, 9 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8, 9, 10 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8, 9, 10, 11 ]))
print (split ([ 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12 ]))
# [[1]]
# [[1, 2]]
# [[1], [2, 4]]
# [[1, 2], [3, 4]]
# [[1, 2], [3], [4, 5]]
# [[1], [2, 3], [4], [5, 6]]
# [[1], [2, 3], [4, 5], [6, 8]]
# [[1, 2], [3, 4], [5, 6], [8, 9]]
# [[1, 2], [3, 4], [5, 6], [8], [9, 10]]
# [[1, 2], [3], [4, 5], [6, 8], [9], [10, 11]]
# [[1, 2], [3], [4, 5], [6], [8, 9], [10], [11, 12]]

因为cut_at_index的continuation参数k有一个默认值，我们也可以在解构赋值的直接风格中使用它（而不是continuation passing风格）。结果提高了程序的可读性。

def split (ls):
  if len (ls) < 3:
    return [ ls ]
  else:
    (left, right) = cut_at_index (ls, len (ls) // 2)
    return split (left) + split (right)

print (split ([ 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 12 ]))
# [[1, 2], [3], [4, 5], [6], [8, 9], [10], [11, 12]]