如何递归地将给定范围内的所有偶数相加

Question

我必须找到给定范围x和y之间所有偶数的和。

我试过：

def sum_even(x, y):
if x == y:
return x
else:
if x % 2 == 0:
return x + sum_even(x+2, y)

如果我的给定范围是(5，11(，那么我的输出应该是24。

Answer 1

试试这个：

def sum_even(x, y):
if x >= y:
return 0
if x % 2 == 0:
return x + sum_even(x + 1, y)
return sum_even(x + 1, y)

示例：

>>> sum_even(5, 11)
24
>>> sum_even(2, 3)
2
>>> sum_even(2, 4)
2
>>> sum_even(2, 5)
6

我的代码不包括和中的上界y(参见示例(。这可能是也可能不是想要的行为，但这取决于你的情况。如果你想包括上限使用这个代码：

def sum_even(x, y):
if x > y:
return 0
if x % 2 == 0:
return x + sum_even(x + 1, y)
return sum_even(x + 1, y)

示例：

>>> sum_even(5, 11)
24
>>> sum_even(2, 3)
2
>>> sum_even(2, 4)
6
>>> sum_even(2, 5)
6

Answer 2

您甚至可以用O(1(解决方案来解决这个问题。事实上，你不需要实际查看你范围内的所有数字。你只需要一个简单的数学公式。例如，为了对0到10^10的所有数字求和，可以使用s = sum(x for x in range(10**10 + 1))(即s = sum(range(10**10 + 1))(，也可以使用著名的公式s = n * (n + 1) // 2(即s = 10**10 * (10**10 + 1) // 2(。第二种方法要快得多，因为你不需要遍历该范围内的所有数字。

类似地，在这种情况下，你可以这样做：

def sum_even(x, y):
n1 = y // 2
n2 = (x - 1) // 2
return n1 * (n1 + 1) - n2 * (n2 + 1)

示例：

>>> sum_even(5, 11)
24
>>> sum_even(2, 3)
2
>>> sum_even(2, 4)
6
>>> sum_even(2, 5)
6

所以你不需要递归，也不需要迭代来解决这个问题。只是一些数学：(

Answer 3

这是您修补的解决方案，我认为它可能是正确的：

def sum_even(x, y):
if x == y or x == y-1:
return x
else:
if x % 2 == 0:
return x + sum_even(x+2, y)
else:
return sum_even(x+1, y)

Answer 4

我假设您希望包含x和y(如果它们是偶数(。例如，sum_even(2,6)将返回2+4+6。

如果您想排除上限，下面的代码片段需要进行小的更正。

# Using python builtin functions `sum` and `range`:
def f1(x, y):
return sum(range(x+x%2, y+1, 2))
# Using arithmetic:
def f2(x, y):
start, end = (x+1)//2, y//2
return end*(end+1) - start*(start-1)
# Using a `for`-loop:
def f3(x, y):
result = 0
for z in range(x, y+1):
if z % 2 == 0:
result += z
return result
# Using recursion:
def f4(x, y):
if x > y:
return 0
elif x % 2 == 1:
return f4(x+1, y)
else:
return x + f4(x+2, y)

# Testing:
print(' x, y  -->  f1,f2,f3,f4')
for (x, y) in [(5,11), (0,10), (2,6), (12, 17)]:
results = [f(x,y) for f in (f1,f2,f3,f4)]
print('{:2d},{:2d}  -->  {:2d},{:2d},{:2d},{:2d}'.format(x,y,*results))
#  x, y  -->  f1,f2,f3,f4
#  5,11  -->  24,24,24,24
#  0,10  -->  30,30,30,30
#  2, 6  -->  12,12,12,12
# 12,17  -->  42,42,42,42