Python:最有效的递归输出方法是什么？

Question

我想创建一个函数，以递归方式返回所有可能的 n 位二进制数的列表。由于我是一名计算机科学专业的学生，​​因此我获得了多种解决方案，但我的问题是哪种方法最有效(最好是为什么)。另外，如果有人可以想出另一种更有效的方法(它必须是递归的，而不是迭代的)，请随时将其添加为答案!

这些方法(不按任何顺序)是给我的:

Build-up

def rec_output2(n, s = ""):
    if n == 0:
        return [s]
    else:
        sol_zero = rec_output2(n-1, s + "0")
        sol_one = rec_output2(n-1, s + "1")
        return sol_zero + sol_one

Expand

def rec_output3(n):
    if n == 0:
        return [""]
    else:
        l = rec_output3(n-1)
        new_l = []
        # we pull iteration inside
        for s in l:
            new_l += [s + "0"]
            new_l += [s + "1"]
        return new_l

Expand and build-up

def rec_output4(n, sols = None):
    if sols == None:
        sols = [""]
    if n == 0:
        return sols
    else:
        new_sols = []
        # we pull iteration inside
        for s in sols:
            new_sols += [s + "0"]
            new_sols += [s + "1"]
        return rec_output4(n-1, new_sols)

因为这是我参加该类(class)的第一年，所以我的老师还不想用表现问题来打扰我，但由于我对这个问题非常感兴趣，我想得到一些澄清。提前致谢!

请原谅我英语不好，我的母语是荷兰语。

Answer 1

您必须分析代码，但一般来说，生成器的性能优于手动迭代。

def gen(bits):
  if bit == 1:
     return ["0", "1"]

  smaller = gen(bits - 1)

  return ["0" + b for b in smaller] + ["1" + b for b in smaller]

无可否认，这同时使用了迭代和递归。