python - 使用递归找到大小为 k 的平衡代码

Question

我正在处理的作业有问题，我必须在 python 中编写一个递归函数，该函数返回大小为 k 的平衡代码。 , 定义为长度为 2k 的所有二进制字符串的列表包含相等数量的 0 s 在字符串的每一半。只允许接受一个参数，k .到目前为止，我已经找到了一种方法来返回长度为 2k 的所有可能的二进制字符串的列表。 ，但我无法将列表缩减为仅满足条件的列表。到目前为止，这是我的代码:

def balanced_code(k):  
if k >= 0:        
    if k == 0:
        return ['']
    else:
        L = []
        x = balanced_code(k - 1)
        for i in range(0, len(x)):
            L.append('00' + x[i])                
            L.append('01' + x[i])
            L.append('10' + x[i])
            L.append('11' + x[i])
        return L
else:
    return

我的计划是在 for 循环之后，我会检查 L 中的每个项目对于提到的标准(在字符串的每一半中 0 的数量相等)，但很快意识到这并没有给出正确的结果，因为它会减少 L在每次调用期间，我只想在对函数的所有调用都完成后减少它。有什么方法可以跟踪代码所在的递归级别或类似的东西，以便在完成所有调用后才减少列表？

Answer 1

这必须有多递归？递归需要在哪里？
如果这是我，我会写一个递归函数:

def all_strings_of_length_k_with_n_zeros(k, n):
    ... you should be able to write this easily as recursion

进而

def balanced_code(k):
   result = []
   for zeros in range(0, k + 1):
      temp = all_strings_of_length_k_with_n_zeros(k, zeros)
      for left, right in itertools.product(temp, temp):
         result.append(left + right)
   return result

奇怪的是，您的导师要求您以递归方式编写一些无需递归即可直接编写的代码。 (我留给读者练习的函数可以使用 itertools.combinations 编写)。