How to add all even numbers in a given range recursively?-CodePudding

I have to find the sum of all even numbers between a given range x and y.

I have tried:

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

If my given range is (5, 11) then my output should be 24.

CodePudding user response：

Try this:

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)

Examples:

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

My code does not include the upper bound y in the sum (see the examples). It might or might not be the desired behavior, but that's depend on your case. If you want to include the upper bound use this code:

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)

Examples:

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

CodePudding user response：

I assume you want to include x and y (if they're even). For instance, sum_even(2,6) would return 2 4 6.

If you want to exclude the upper bound instead, the code snippets below need a small correction.

# 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

CodePudding user response：

You might even solve this problem with a O(1) solution. Indeed, you don't need to actually look at ALL the numbers in your range. All you need is a simple mathematical formula. For example, in order to sum all the numbers from 0 to 10^10, you can either do s = sum(x for x in range(10**10 1)) (i.e., s = sum(range(10**10 1))) or you can use the famous formula s = n * (n 1) // 2 (i.e., s = 10**10 * (10**10 1) // 2). The second approach is much much faster, because you don't need to go through all the numbers in the range.

Similarly in this case you can do this:

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

Examples:

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

So you don't need recursion and you don't need iteration to solve this problem. Just some math :)

CodePudding user response：

This is your solution patched, I think it could be correct:

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)

CodePudding user response：

Here's my attempt:

def sum_even(start, end):
    if start == end:
        return end*((start 1)%2)
    else:
        return start*((start 1)%2)   sum_even(start 1,end)