如何编写递归分隔函数，解决Python奇偶数值分割时的列表重置问题

问题原因 #

• 你的内部函数版本中，main.append(evenList)和main.append(oddList)的逻辑放在了递归调用的后面，每次处理完一个元素递归返回时都会执行一次，列表长度有多少就会重复添加多少次奇偶列表，才会出现大量重复结果
• 拼接最终结果的逻辑不需要放在递归内部，只需要所有元素都处理完成之后再拼接奇偶列表返回即可

修复后的代码 #

def separateNumbers(L):
    evenList = []
    oddList = []
    def inner(L):
        if len(L) == 0:
            return
        if L[0] % 2 == 0:
            evenList.append(L[0])
        else:
            oddList.append(L[0])
        # 递归处理剩余元素
        inner(L[1:])
    inner(L)
    # 所有元素处理完后再拼接结果，仅拼接一次
    return [oddList, evenList]

测试验证 #

输入测试：

inputList = [1,2,3,4,5,6]
print(separateNumbers(inputList))

输出结果：

[[1, 3, 5], [2, 4, 6]]

可选参考：无内部函数的纯递归实现 #

如果不想借助外部变量存储结果，可以用纯递归返回值拼接的方式实现，代码更简洁：

def separateNumbers(L):
    if not L:
        return [[], []]
    # 先获取剩余元素的拆分结果
    odd, even = separateNumbers(L[1:])
    # 把当前元素加到对应列表头部
    if L[0] % 2 == 0:
        even.insert(0, L[0])
    else:
        odd.insert(0, L[0])
    return [odd, even]

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