CODEWITHSUNDEEP
pythonpython-3.xfunctionrecursion
randomobject123
randomobject123

Reputation: 133

write a function (recursive) that will calculate the sum of even numbers from 1 to n

I have to write a recursive function that will calculate the sum of even numbers from 1 to n. for example for n=input= 6 the expected output would be: 2+4+6 = 12

def sum_of_even(n):
    if not n % 2 == 0:
        return n
    else:
        return n + sum_of_even(n-1)


print(sum_of_even(6))

this gives output 11, but I don't even know if my concept is right

Upvotes: 1

Views: 19403

Answers (6)

Vedant Kashettiwar
Vedant Kashettiwar

Reputation: 1

Calculate sum of first 10 even number using recursion

def even_sum(n):
    if n%2==0:
        if n==2:
            return 2
        else:
            return(n+even_sum(n-2))
n=10
n*=2
print(even_sum(n))

Upvotes: -1

trincot
trincot

Reputation: 350137

There is a closed formula for this, so no iteration is needed: for even 𝑛 you get the doubles of the triangular number sequence, and so the formula is the double of 𝑛/2(𝑛/2+1)/2 which is 𝑛/2(𝑛/2+1). For odd 𝑛 the result is the same as for 𝑛-1.

So the code can be:

def sum_of_even(n):
    return (n // 2) * (n // 2 + 1)

But as the question was about recursion, then define the base case for when 𝑛 is less than 2 (which means the result is 0). Otherwise when the number is odd, solve the problem for 1 less (it has the same result). If the number is even, solve the problem for 2 less and add 𝑛 to that result:

def sum_of_even(n):
    return 0 if n<2 else sum_of_even(n-1) if n%2 else n + sum_of_even(n-2)

Upvotes: 0

pjs
pjs

Reputation: 19853

I would recommend a divide and conquer approach based on the idea that the sum over the whole range can be found by adding the sum of the first half-range to the sum of the second half range. This divides the size of the subproblem in half for each recursive call rather than whittling it down one at a time. The other proposed solutions will blow out the recursion stack for inputs larger than 2000, while this approach works for gigantic numbers.

def sum_of_even(upperlim, lowerlim = 2):
    if upperlim <= lowerlim:
        if upperlim == lowerlim:
            return upperlim
        else:
            return 0
    midpoint = lowerlim + (upperlim - lowerlim) // 2
    if midpoint % 2 == 0:
        return sum_of_even(upperlim, midpoint + 2) + sum_of_even(midpoint, lowerlim)
    else:
        return sum_of_even(upperlim, midpoint + 1) + sum_of_even(midpoint - 1, lowerlim)

def cross_check(n):
    half_n = n // 2
    return half_n * (half_n + 1)

n = 1000000
print(sum_of_even(n))   # => 250000500000
print(cross_check(n))   # => 250000500000

As you can see, I've also provided a cross_check routine to confirm the answer. This is based on the observation that the sum of even values up to n is equal to 2*(1 + 2 + ... + n // 2). (Note that this is true whether n is even or odd.) The sum of the integers up to k is a well known result, k * (k + 1) / 2. Hence, plugging in n // 2 for k, and noticing that the 2's cancel, we get the formula in cross_check — which is what you really ought to be using instead of recursion.

Upvotes: 1

willcrack
willcrack

Reputation: 1852

Making the least amount of modification to your code:

def sum_of_even(n):
    if n==0:
        return 0
    if not n % 2 == 0:
        return sum_of_even(n-1)
    else:
        return n + sum_of_even(n-1)


print(sum_of_even(10))

There were two problems with your code:

  1. you weren't returning the value that you calculated so far when the number was even. Instead you were returning the input value n. By doing this, you were simply summing to the previous n value value n + sum_of_even(n-1). Thus when you did print(sum_of_even(6))it returned 6 + sum_of_even(6-1) that is 11. If you did print(sum_of_even(5)) it would simply return 5.

  2. Since the above stop condition wasn't correct you needed a proper one. You want to add all even numbers until zero(and not to -inf), so:

if n==0:
    return 0

EDIT: Or, has suggested by Stef, you can simply move in 2 by 2 instead of 1 by 1 times when you find your first even number:

def sum_of_even(n):
    if n<=0:
        return 0
    if not n % 2 == 0:
        return sum_of_even(n-1)
    else:
        return n + sum_of_even(n-2)

Upvotes: 4

Gorgine
Gorgine

Reputation: 310

You can try this:

def sum_even_numbers(number):
    if number == 0:
        return 0

    if number % 2 == 0:
        return number + sum_even_numbers(number - 1)  # (number - 2) is also ok
    else:
        return sum_even_numbers(number - 1)

Upvotes: 0

ombk
ombk

Reputation: 2111

def sum_of_even(n):
    sum1 = 0
    if n == 0:
        return sum1

    elif n % 2 == 0:
        sum1 += n
    
    return sum1 + sum_of_even(n - 1)

This should do it. The only thing missing in your code was the condition that when n==0 it should stop.

Upvotes: 0

Related Questions