将生成汉明距离为n的二进制字符串代码改写为递归实现

我来帮你把嵌套循环的逻辑转成更灵活的递归形式！其实递归的核心就是把「要翻转n个位置」的大问题拆成一个个小决策：每次处理当前字符，决定翻或者不翻，然后把剩下的任务交给递归调用，完全不用管n的大小，逻辑统一。

递归思路拆解 #

1. 基准情况：
   • 如果剩余需要翻转的次数n为0，说明当前构建的字符串已经符合要求，直接加入结果列表。
   • 如果已经处理完所有字符但n还大于0，说明这种情况不可能满足条件，直接终止这条递归路径。
2. 递归分支：
   • 不翻转当前字符：保留当前字符，递归处理剩下的子字符串，剩余翻转次数不变。
   • 翻转当前字符：把当前的0变1、1变0，递归处理剩下的子字符串，剩余翻转次数减1。

代码示例（Python） #

def generate_hamming_strings(original_str, n):
    result = []
    
    def recursive_helper(current_str, remaining_chars, remaining_flips):
        # 基准情况1：没有需要翻转的次数了，记录结果
        if remaining_flips == 0:
            result.append(current_str + remaining_chars)
            return
        # 基准情况2：字符处理完了但还有翻转次数，直接返回
        if not remaining_chars:
            return
        
        # 分支1：不翻转当前字符
        recursive_helper(current_str + remaining_chars[0], remaining_chars[1:], remaining_flips)
        
        # 分支2：翻转当前字符
        flipped_char = '1' if remaining_chars[0] == '0' else '0'
        recursive_helper(current_str + flipped_char, remaining_chars[1:], remaining_flips - 1)
    
    recursive_helper("", original_str, n)
    # 若原字符串存在重复字符，可能生成重复结果，可根据需求开启去重
    # result = list(set(result))
    return result

用法示例 #

比如输入原字符串'001'，汉明距离n=1：

print(generate_hamming_strings('001', 1))
# 输出：['000', '011', '101']

为什么比嵌套循环好？ #

原来的嵌套循环层数完全绑定n的大小——如果n是3就要写3层循环，n是5就要写5层，扩展性极差。而递归版本不管n是1还是100，逻辑都是一样的，只需要传入参数即可，代码简洁且易维护。

另外如果需要处理n大于原字符串长度的情况，函数会自动返回空列表，因为不可能有这样的字符串，也不用额外加判断逻辑。

内容的提问来源于stack exchange，提问作者knuckles