Python递归函数中可变对象（列表）与不可变对象（字符串）的处理策略

def generateString_problematic(N: int):
    def helper(i, n, arr, an):
        # 错误：i用于索引，但arr是动态增长的，i-1可能不准确
        # 错误：未在所有分支中平衡append和pop操作
        if i == n:
            an.append(arr.copy()) # 这里虽然copy了，但arr在递归过程中已经被污染
            return 

        # 假设 arr[i-1] 已经存在，并且代表当前要处理的“前一个”元素
        # 实际上 i-1 指向的是arr的倒数第二个元素，而不是“前一个”逻辑元素
        if arr[i-1] == 1:
            arr.append(0)
            helper(i + 1, n, arr, an)
            # 缺少 arr.pop() 来回溯状态
        elif arr[i-1] == 0: # 使用 elif 更清晰，避免重复判断
            arr.append(0)
            helper(i + 1, n, arr, an)
            arr.pop() # 这里的pop只针对添加0的情况
            arr.append(1)
            helper(i + 1, n, arr, an)
            # 缺少 arr.pop() 来回溯状态

    ans = []
    # 初始化时，i=1，但arr只有一个元素，arr[i-1]即arr[0]
    # 第一次调用：a = [0]，helper(1, N, [0], ans)
    # 第二次调用：a = [1]，helper(1, N, [1], ans)
    # 这种初始化方式本身也增加了复杂性
    a = [0] 
    helper(1, N, a, ans)
    a = [1] # 这里的a重新赋值，但前一个helper调用中的a仍然是之前那个[0,...]
    helper(1, N, a, ans)
    return ans

# print(generateString_problematic(3)) 
# 预期输出：[[0,0,0], [0,0,1], [0,1,0], [1,0,0], [1,0,1]]
# 实际输出：[[0, 0, 0], [0, 0, 1], [0, 0, 1, 0], [0, 0, 1, 1], [1, 0, 0], [1, 0, 1]]
# 列表中出现了长度大于N的情况，且结果不符合预期

def generateString_string(N: int):
    def helper(i, n, arr, an):
        if i == n:
            an.append(arr)
            return

        # arr[i-1] 对应 arr[-1]
        if arr[-1] == "1":
            helper(i + 1, n, arr + "0", an) # 创建新字符串并传递
        elif arr[-1] == "0":
            helper(i + 1, n, arr + "0", an) # 创建新字符串并传递
            helper(i + 1, n, arr + "1", an) # 创建新字符串并传递

    ans = []
    helper(1, N, "0", ans)
    helper(1, N, "1", ans)
    return ans

# print(generateString_string(3))
# Output: ['000', '001', '010', '100', '101']
# 结果正确，因为字符串是不可变的

def generateString_mutable_corrected(N: int):
    def helper(current_arr, result_list):
        # 递归终止条件：当前序列长度达到N
        if len(current_arr) == N:
            result_list.append(current_arr.copy()) # 添加副本
            return

        # 尝试添加 '0'
        current_arr.append(0)
        helper(current_arr, result_list)
        current_arr.pop() # 回溯：移除 '0'

        # 尝试添加 '1'
        # 只有当前序列为空（初始情况）或前一个元素是 '0' 时才能添加 '1'
        if not current_arr or current_arr[-1] == 0:
            current_arr.append(1)
            helper(current_arr, result_list)
            current_arr.pop() # 回溯：移除 '1'

    ans = []
    helper([], ans) # 从空列表开始构建
    return ans

print("方法一 (原地修改与状态恢复):")
print(generateString_mutable_corrected(3))
# Output: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]]

def generateString_immutable_like(N: int):
    def helper(current_arr, result_list):
        # 递归终止条件：当前序列长度达到N
        if len(current_arr) == N:
            result_list.append(current_arr) # 直接添加，因为current_arr已经是新对象
            return

        # 尝试添加 '0'：传递新的列表 current_arr + [0]
        helper(current_arr + [0], result_list)

        # 尝试添加 '1'：只有当前序列为空或前一个元素是 '0' 时才能添加 '1'
        if not current_arr or current_arr[-1] == 0:
            helper(current_arr + [1], result_list) # 传递新的列表 current_arr + [1]

    ans = []
    helper([], ans) # 从空列表开始构建
    return ans

print("\n方法二 (传递新的列表副本):")
print(generateString_immutable_like(3))
# Output: [[0, 0, 0], [0, 0, 1], [0, 1, 0], [1, 0, 0], [1, 0, 1]]