使用Python递归返回一个列表嵌套的列表

Question

我正在提高递归问题的能力。当问题陈述要求打印值时（例如，BST遍历，其中打印节点值），我没有任何问题；当问题要求返回值列表（例如，在树中返回两个节点之间的路径）时，我也没有太多问题。但是，如果有多个答案涉及到多个列表（或一个2D列表）需要返回时，我就会遇到问题。例如，问题要求我返回孩子可以达到楼梯顶部的方式数量，假设它可以一次跳1、2或3步。这不是问题，并且以下问题已经解决：

def step_helper(steps):
    if(steps == 0):
        return 1
    elif(steps < 0):
        return 0
    else:
        return step_helper(steps-1) +
             step_helper(steps-2) + 
             step_helper(steps-3)

def find_num_ways(steps):
    count = step_helper(steps)
    print(count)

find_num_ways(10)

如果我需要从BST中返回两个节点之间的路径，那么返回一个列表就没有问题了。

def another_path_helper(self, n1, n2):
    if(n1 == None):
        return [None]
    elif(n1 == n2):
        return [n1.data]
    elif(n1.data > n2.data):
        return [n1.data] + self.another_path_helper(n1.left, n2)
    elif(n1.data < n2.data):
        return [n1.data] + self.another_path_helper(n1.right, n2)
    else:
        return None

def another_path(self, n1, n2):
    path = self.another_path_helper(n1, n2)
    if(None in path):
        return None
    else:
        return path

然而，我不知道如何返回一个列表的列表。在子步骤示例中，如果我要返回孩子攀爬楼梯的方式数量，在不需要传递列表作为递归函数参数的情况下，如何返回路径列表（即二维列表），其中每个条目都是从底部到顶部所采取的步骤列表？理想情况下，我不需要将一个可变对象作为参数传递给我的递归函数，因为我被告知将可变对象传递给递归函数是一个不好的做法，与使用静态计数器没有什么区别。

- danep

Answer 1

将列表作为参数传递给递归函数并且不修改它是完全没有问题的。事实上，这样做可以很容易地解决问题。

考虑问题的一个小版本：只有3步。你在楼梯底部。你可以迈一步、两步或三步。然后你有三个子问题需要解决：

• 所有以路径[1]开始，再走2步的解决方案。
• 所有以路径[2]开始，再走1步的解决方案。
• 所有以路径[3]开始，再走0步的解决方案。

看起来像是解决递归问题的好开端。

让我们只关注这些子问题中的第一个。你的路径是[1]，你还要走2步。从这里开始，你可以迈一步、两步或三步。然后你又有了3个子子问题：

• 所有以路径[1,1]开始，再走1步的解决方案。
• 所有以路径[1,2]开始，再走0步的解决方案。
• 所有以路径[1,3]开始，再走-1步的解决方案。

第一个子子问题需要更多的工作...另一个递归调用，应该返回[[1,1,1]]。第二个子子问题应该只返回我们到这里所走过的路径：[[1,2]]。最后一个子子问题不应有解决方案：[]。我们将这些解决方案相加[[1,1,1]] + [[1,2]] + []得到[[1,1,1],[1,2]]，然后返回它。

回溯，第二个子问题，"以路径[2]开始，再走1步"应该返回[[2,1]]作为解决方案集。第三个子问题，"以路径[3]开始，再走0步"应该返回[[3]]。将这些解决方案与[[1,1,1],[1,2]]相加得到完整的解决方案集：[[1,1,1],[1,2],[2,1],[3]]

代码如下：

def find_paths(total):

   def helper(path, remaining):
      paths = []
      if remaining == 0:
         paths.append(path)
      elif remaining > 0:
         for step in range(1,3+1):
            paths.extend( helper(path + [step], remaining - step))
      return paths

   return helper([], total)

print(find_paths(3))

预期的输出为：

[[1, 1, 1], [1, 2], [2, 1], [3]]

当然，你不需要在递归调用中传递路径和当前步骤的列表。你可以要求从当前步骤到楼梯顶部的所有路径，并在前面加上刚刚走过的步骤。在这种情况下，我们甚至不需要使用辅助函数。

def find_paths(remaining):

   paths = []
   if remaining == 0:
      paths.append([])
   for step in range(1,3+1):
       if step <= remaining:
          subpaths = find_paths(remaining - step)
          for subpath in subpaths:
             paths.append([step] + subpath)

   return paths

print(find_paths(4))

输出结果如下：

[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [1, 3], [2, 1, 1], [2, 2], [3, 1]]

需要注意的是，调用find_paths(2)将在上升前两步后被调用，并返回相同子路径[[1,1],[2]]，可以使用路径[1,1]或路径[2]进行单个跳跃。由于它返回相同的值，因此我们可以缓存结果，并在随后的步骤中重复使用该值，而不必重新计算所有子路径。

from functools import lru_cache

@lru_cache()
def find_paths(remaining):

   paths = []
   if remaining == 0:
      paths.append([])
   for step in range(1,3+1):
       if step <= remaining:
          subpaths = find_paths(remaining - step)
          for subpath in subpaths:
             paths.append([step] + subpath)

   return paths

paths = find_paths(10)
print(len(paths))
print(find_paths.cache_info())

274
CacheInfo(hits=17, misses=11, maxsize=128, currsize=11)

如果您将缓存大小设置为零@lru_cache(maxsize=0)，则可以看到在解决问题的过程中find_paths()函数被调用了600次：CacheInfo(hits=0, misses=600, maxsize=0, currsize=0)。启用缓存后，它仅被调用28次，并且仅执行11次； 17次，先前存储的结果立即返回，这可能是相当大的节省。

- AJNeufeld