python-3.x - 使用python递归返回列表列表

Question

我正在复习递归问题，并且当问题陈述要求打印值时没有问题(例如，打印节点值的 BST 遍历)，并且在问题要求返回值列表(返回一个树中 2 个节点之间的路径)但是当有多个答案时遇到问题，涉及要返回的多个列表(或单个 2D 列表)。例如，问题要求我返回一个 child 到达楼梯顶部的方式，假设他一次可以跳 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 中的两个节点返回一条路径，返回 1 个列表是没有问题的

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

但是，我对如何返回列表一无所知。在 child-steps 示例中，我如何返回一个路径列表，而不是返回一个 child 可以爬楼梯的方式的数量，这将是一个 2d 列表，其中每个条目将是一个步骤列表从下到上？理想情况下，我不需要将列表作为参数传递给我的递归函数，因为我被告知将可变对象传递给递归函数是一种不好的做法，与使用静态计数器没有什么不同。

Answer 1

将列表作为参数传递给递归函数而不修改它绝对没有错。事实上，这样做使得解决问题变得相当简单。

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

所有以 [1] 路径开头的解决方案，还有 2 个额外的步骤。

所有以 [2] 路径开头的解决方案，再进行 1 步。

所有以 [3] 路径开头的解决方案, 进行 0 个额外的步骤。

看起来是递归解决方案的良好开端。

让我们只关注这些子问题中的第一个。您的路径是 [1] ，您还有 2 个额外的步骤要做。从这里开始，您可以进行 1 步、2 步或 3 步。您再次有 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] 的路径开始，再走一步”应该返回 [[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]]

当然，你不必通过path ，当前的步骤列表，进入递归调用。相反，您可以只询问从当前步骤到楼梯顶部的所有路径，并在这些路径前面加上刚刚执行的步骤。在这种情况下，我们甚至不需要助手:

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 次，之前存储的结果立即返回，这可以节省大量成本。