如何用递归函数结合itertools返回保序唯一元素元组并避免递归深度错误？

问题描述 #

我在其他帖子里找过但没找到解决方案。我需要一个通过itertools表达式递归调用的函数，返回元素唯一且保持原有顺序的元组。比如：

def function(lst):
    return lst and (lst[0],) + function(some_itertools_expression)

示例输入：function([1, 7, 7, 9, 0, 1]) 应返回 (1, 7, 9, 0)。

我尝试了以下代码：

return lst and (lst[0],) + function(tuple([itertools.groupby(lst)][:len(lst)]))

但遇到了 RecursionError: maximum recursion depth exceeded 错误。请问怎么解决？

解决方案 #

你的问题出在递归参数的处理上：之前用itertools.groupby的方式没有正确缩小递归的输入规模，导致递归无法终止，最终触发深度超限错误。

正确的思路是：每次递归保留当前列表的第一个元素，然后用itertools.filterfalse过滤掉剩余列表中所有和第一个元素相同的项，将过滤后的列表作为下一次递归的输入，直到列表为空时终止递归。

代码实现：

import itertools

def unique_preserve_order(lst):
    if not lst:
        return ()
    first_element = lst[0]
    # 过滤剩余列表中所有与第一个元素相同的项
    remaining_elements = list(itertools.filterfalse(lambda x: x == first_element, lst[1:]))
    return (first_element,) + unique_preserve_order(remaining_elements)

测试验证：

print(unique_preserve_order([1, 7, 7, 9, 0, 1]))  # 输出 (1, 7, 9, 0)

错误原因分析 #

你之前的代码中，tuple([itertools.groupby(lst)][:len(lst)])并没有生成去掉当前元素后的剩余列表——itertools.groupby返回的是分组迭代器，转成tuple后本质上还是包含原列表分组信息的迭代器包装，每次递归传入的参数并没有真正减少问题的复杂度，导致递归无限循环，最终触发RecursionError。

另外注意：不要用list作为函数参数名，这会覆盖Python内置的list类型，可能引发其他问题。

内容的提问来源于stack exchange，提问作者D-Money