递归函数 - 比较 2 个列表，返回两个列表中不存在的元素

Question

我必须做一个递归函数，比较两个列表并返回它们没有共同点的元素。

这是我到目前为止所拥有的：

def compare(list1, list2):
    if list2[0] in list1:
        list1.remove(list2[0])
        return compare(list1[1:], list2[1:])
    return list1  
#Example 
 >>>>compare([2, 3, 4, 5], [2, 3])
 [4, 5]

我可以比较列表的第一个元素（list[0]）是否相同，但是如果元素不在第一个位置，我就无法比较它们......我已经尝试了很多选择，但我是编程方面的乞丐，真的不知道该怎么做。它必须是一个递归函数，我不能使用 FOR 或 WHILE。有什么方法可以在不使用 remove（） 的情况下做到这一点？非常感谢

Answer 1

这是一个替代答案。它以保持练习规则的肮脏伎俩为代价，减少了重复：

def compare(a, b):
    if isinstance(b, list):
        # Let's cheat and change the meaning of the parameters.
        return compare(a, set(b)) + compare(b, set(a))
    else:
        result = []
        if a:
            if a[0] not in b:
                result.append(a[0])
            result.extend(compare(a[1:], b))
        return result

在代码中，在再次调用同一函数之前，您从列表中删除了第一个元素。当你使用递归时，这不是必需的，它以不同的方式处理它。在递归中，您通常不会就地修改序列，而是将小节传递给内部调用。对于该内部调用，该小节是整个序列。

Answer 2

这个怎么样：

def compare(a, b, original_a = None, original_b = None):
    result = []
    if original_a is None:
        original_a = a
    if original_b is None:
        original_b = b
    if a and a[0] not in original_b:
        result.append(a[0])
    if b and b[0] not in original_a:
        result.append(b[0])
    if a or b:
        result += compare(a[1:], b[1:], original_a, original_b)
    return result

Answer 3

从 for 循环开始（更容易思考）：

def disjunctive_union(a, b):
    a_filt = [x for x in a if x not in b]
    b_filt = [x for x in b if x not in a]
    return a_filt + b_filt

让我们做这个"递归"。一个想法是删除我们已经检查过的元素，并在较小的列表中调用我们的函数。

def disjunctive_union(a, b):
    if len(a) == 0:
        return b
    first = a[0]
    if first not in b:
        return [first] + disjunctive_union(a[1:], b)
    # These filters can individually be made recursive too
    # (and often are in functional languages!)
    a = [x for x in a if x != first]
    b = [x for x in b if x != first]
    return disjunctive_union(a, b)

---

编辑：要演示过滤器的递归变体：

 a = [x for x in a if x != first]

可以替换为：

def recursive_filter(pred, xs):
    x = next(xs)
    if pred(x):
        yield x
    yield from recursive_filter(pred, xs)
a = list(recursive_filter(lambda x: x != first, iter(a)))

---

编辑2：我想了很多，这是一个更简单的解决方案：

def disjunctive_union(a, b):
    a_filt = list(recursive_filter(lambda x: x not in b, iter(a)))
    b_filt = list(recursive_filter(lambda x: x not in a, iter(b)))
    return a_filt + b_filt

。使用我上面定义的recursive_filter。

（FWIW，我认为这整件事是使非递归函数递归的毫无意义的练习......

Answer 4

嗨，

这是另一个解决方案。

def diff(l1,l2):
    result=[]
    if len(l1)==0:
    #return l2, finally it will only contain unique elements (if any)
            return l2
    if l1[0] in l2:
        copy=l1[0]
    #remove all occurances of the common element from both lists
        l1=list(filter(lambda a: a != l1[0], l1))
        l2=list(filter(lambda a: a != copy, l2))
    else:
    #if list1's first element is not in list2 add it to result and pop it
        result.append(l1[0])
        l1.pop(0)
    result+=diff(l1,l2)
    return result
list1=[1,3,2,4,4,5]
list2=[1,2,7]
print(diff(list1,list2))

输出：

[3， 4， 4， 5， 7]