在递归的基本情况下返回None的目的只是用作填充符，然后自然地执行调用堆栈中的顶级递归调用吗？

Question

我正在解决一个递归问题，在这个问题中，我被赋予一个整数数组，并被要求返回它的幂集。

e、 g.[1,2,3]的功率集为[[]，[1]，[2]，[3]，[1,2]，[1,3]，[2,3]，[1,2,3]]

这是执行此操作的递归代码：

def powerset(array, idx = None): 
    if idx is None: 
        idx = len(array) - 1
    if idx <0: 
        return [[]]
    ele = array[idx]
    subset = powerset(array,idx-1) 
    for i in range(len(subset)): 
        currentSubset = subset[i]
        subset.append(currentSubset + [ele])
    return subset

虽然我很清楚发生了什么，但我的问题是：

>

当我们到达基本情况idx时

这可能是一个过高的顺序，但有人能解释一下递归调用是如何运行的吗？这是我的理解；

>

我们从指针idx指向3开始，因此ele=3，然后初始化一个称为子集的子集，该子集包含[1,2]的幂集

这就是我感到困惑的地方，并且很难看到代码是如何成功的...我们现在是转到下一批代码，即for循环？还是计算[1,2]的功率集？

根据切普纳的建议：

def powerset(array):
    return _powerset(array,len(array)-1)

def _powerset(array,index):
    if index <0:
        return [[]]
    ele = array[index]
    subset = _powerset(array,index-1)
    for i in range(len(subset)):
        subset.append(subset[i] + [ele])
    return subset

Answer 1

如前所述，如果传递了显式索引，该函数将返回数组[：idx 1]的幂集。

测试<代码>idx

我的印象是，您试图将递归函数视为以令人困惑的方式编写的循环。相反，您应该将其视为一个计算某物的函数，在本例中是一个幂集，并且碰巧将其自身用作库函数（以一种总是终止的方式）。

给定一个包含元素x的非空集S，以及一种计算较小集S \{x}的幂集的方法，如何得到S的幂集？回答：对于S \{x}的幂集中的每个集，返回两个集：该集和添加了x的集。这就是代码的作用。

Answer 2

将打印添加到递归调用的开始和结束是可视化其工作方式的有用方法。

def powerset(array, idx=None, indent=0):
    trace = f"{'  '*indent}powerset({array}, {idx})"
    print(f"{trace}...")
    if idx is None:
        idx = len(array)-1
    if idx < 0:
        print(f"{trace} -> [[]]")
        return [[]]
    ele = array[idx]
    subset = powerset(array, idx-1, indent+1)
    for i in range(len(subset)):
        subset.append(subset[i] + [ele])
    print(f"{trace} -> {subset}")
    return subset

打印：

powerset([1, 2, 3], None)...
  powerset([1, 2, 3], 1)...
    powerset([1, 2, 3], 0)...
      powerset([1, 2, 3], -1)...
      powerset([1, 2, 3], -1) -> [[]]
    powerset([1, 2, 3], 0) -> [[], [1]]
  powerset([1, 2, 3], 1) -> [[], [1], [2], [1, 2]]
powerset([1, 2, 3], None) -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

请注意，需要以不同的方式处理0和None，这就是为什么需要使用idx is None，而不是not idx！

（编辑）根据注释中的注释，避免idx=None混淆的一种方法（除了将其包装在另一个函数层中）是稍微修改递归，以便它首先不需要idx变量。与其传递完整的数组和指示要迭代哪个部分的变量，不如传递要为其计算功率集的数组子集。这使得每个递归调用（包括第一个递归调用）都按照完全相同的“约定”进行操作——计算此列表的幂集。

def powerset(array, indent=0):
    trace = f"{'  '*indent}powerset({array})"
    print(f"{trace}...")
    if array:
        p = powerset(array[:-1], indent+1)
        p.extend([s + [array[-1]] for s in p])
    else:
        p = [[]]
    print(f"{trace} -> {p}")
    return p

powerset([1, 2, 3])...
  powerset([1, 2])...
    powerset([1])...
      powerset([])...
      powerset([]) -> [[]]
    powerset([1]) -> [[], [1]]
  powerset([1, 2]) -> [[], [1], [2], [1, 2]]
powerset([1, 2, 3]) -> [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]

请注意，递归调用的序列在每一步都计算完全相同的结果，但输入更简单——而不是看着idx从无到1到0到-1并且必须推理这意味着什么，我们看到arr稳步向基本情况收缩，然后堆栈的每一层将arr的最后一个元素添加到之前调用的每个子集。