有没有一种方法可以编写一个递归函数，它可以查看列表中的所有整数，并查看其中任何两个是否等于负和？

Question

所以问题是，你有一个整数列表，你必须找到列表中的任何两个和是否为负。

现在我有这个

def negsum(L):
    if len(L) <= 2:
        if L[0] + L[1] >= -1: #Here is my base case
            return False
        else:
            return True
    else: 
        if L[0] + L[1] <= -1:
            return True
        else:
            return negsum(L[1:]) #Recursive portion

我的代码的问题是它只检查列表中的前两个。所以在一个列表中，[-10,15,30，-5]当它应该为真时，你会得到假，因为-5-10是一个负和。我的功能只检查：

-10 15

15 30

30 - 5

我怎样才能得到它，让它使用递归检查-10-30、-10-5和15-5？

编辑，我忘了提一下，只允许使用len（）[]和：运算符。没有循环。如果没有循环，这可能吗？

Answer 1

下面是一个没有循环（隐式或显式）的解决方案：

def negsum(lst, sub=True):
    return len(lst) > 1 \
        and ((lst[0] + lst[1]) < 0
                or negsum([lst[0]]+lst[2:], False)
                or (sub and negsum(lst[1:])))

或者，下面的版本将进程更清晰地分成两个子函数，并且不需要额外的参数“子”：

def negsum(lst):
    def first_with_others(lst): # compare lst[0] with all later values
        if len(lst) > 1:
            #print("summing", lst[0], "and", lst[1])
            return ((lst[0] + lst[1]) < 0) or first_with_others([lst[0]]+lst[2:])
    def drop_first(lst): # successively drop first element
        if lst:
            return first_with_others(lst) or drop_first(lst[1:])
    return drop_first(lst) or False # converts None to False

取消对print函数调用的注释将显示计算的总和：

>>> negsum([1,2,3,4,5])
summing 1 and 2
summing 1 and 3
summing 1 and 4
summing 1 and 5
summing 2 and 3
summing 2 and 4
summing 2 and 5
summing 3 and 4
summing 3 and 5
summing 4 and 5
False
>>> negsum([-1,2,3,4,5])
summing -1 and 2
summing -1 and 3
summing -1 and 4
summing -1 and 5
summing 2 and 3
summing 2 and 4
summing 2 and 5
summing 3 and 4
summing 3 and 5
summing 4 and 5
False
>>> negsum([-1,2,3,-4,5])
summing -1 and 2
summing -1 and 3
summing -1 and -4
True
>>> negsum([-2,1])
summing -2 and 1
True

Answer 2

这个想法是将列表分成两部分：第一个元素L[0]和其余的L[1://code>并将函数递归地应用于L[1://code>部分：

def negsum(L):
    if len(L) == 2:     # base case
        return True if L[0] + L[1] < 0 else False 
    elif negsum(L[1:]): # recursion on the L[1:] part
        return True
    else:               # check L[1:] part pairwise against the first element
        return any(x + L[0]<0 for x in L[1:])

Answer 3

以下是一种方法：

def negsum(L):
    if len(L)<2: return False
    if len(L) == 2:
        if sum(L)<0: return True
        else: return False
    for i,elem in enumerate(L):
        if elem < 0:
            return negsum(L[i+1:]+[elem])

输出：

In [39]: negsum([1,2,3,4,5])
Out[39]: False

In [40]: negsum([-1,2,3,4,5])
Out[40]: False

In [41]: negsum([-1,2,3,-4,5])
Out[41]: True