Calculate sum of arithmetic with recursion-CodePudding

I wonder how i would count the sum of a arithmetic sequence. The user should be able to choose where the sequence starts and ends, example: start at 2 and end at 5, (2 3 4 5) The user should also be able to choose what the difference between the numbers should be, example, Difference 2 would be: 2 4 6 8....

    I also have to use recursion for this, (It's for school). 
    I've read a lot of different solutions but I just dont seem to understand them :(

My code atm is this:

def artimetisk_summa_rekursion(a1,an,n):
    sum = 0 
    if n == 0: 
        return 0 
    while n >0:
        sum  = artimetisk_summa_rekursion(a1, an, n - 1) 
    return sum

Just ignore the name of the function xd, they are in swedish. a1 is the first number, n is the last number and an is the difference. I've found out that it works as long as the first number is 1 and the difference is 1. Though as soon as i change those, it doesn't work anymore :(

CodePudding user response：

I'll note first that the easy way to generate a sequence like this is range, and the easy way to find the sum of a sequence is sum:

>>> sum(range(2, 6))  # sum of all numbers from 2 to 5
14
>>> sum(range(2, 9, 2))  # sum of all even numbers from 2 to 8
20

For a recursive solution, though, you want to approach it by breaking it down into a combination of the simplest case (a sequence with 0 elements) and a way to reduce a complex case to a simpler case (incrementing a bound of the range to reduce the sequence by one element, which is added to the total).

Hence:

>>> def sum_inclusive_range(start: int, end: int, step: int = 1) -> int:
...     if start > end:
...         return 0
...     return start   sum_inclusive_range(start   step, end, step)
...
>>> sum_inclusive_range(2, 5)
14
>>> sum_inclusive_range(2, 8, 2)
20

The last line of the function:

    return start   sum_inclusive_range(start   step, end, step)

is the part that makes it "recursive" -- we're defining our sum_inclusive_range function in terms of that same function. This isn't a purely circular definition as long as we have a "base case" that yields a non-recursive answer, which all of our recursive calls get us closer to.

sum_inclusive_range(2, 5) == 2 sum_inclusive_range(3, 5)
sum_inclusive_range(3, 5) == 3 sum_inclusive_range(4, 5)
sum_inclusive_range(4, 5) == 4 sum_inclusive_range(5, 5)
sum_inclusive_range(5, 5) == 5 sum_inclusive_range(6, 5)
sum_inclusive_range(6, 5) == 0

CodePudding user response：

A bit of advice:

If you're implementing this in python, I recommend using the same conventions used in python's range objects and slice objects;
There is a closed formula to sum arithmetic sequences; using this formula will be much more efficient than using a loop to add the elements one by one.

Python's convention for range(start, stop, step) is that start is included, but stop is excluded. Using the same conventions will avoid users being confused and not knowing which functions use which conventions.

You can find the formula for the sum of an arithmetic sequence, along with a proof and how to arrive at that formula, in any high school math course. Also on Wikipedia.

An easy way to remember the formula is to remember that the average of the sequence is always equal to the sum divided by the number of elements; but for an arithmetic sequence, the average is also equal to (first element last element) / 2.

Thus formula is:

sum = (number of elements) * (first element   last element) / 2

Note that if the first element and the step are both integers, then the sum is mathematically guaranteed to be an integer too, so you can use integer division // instead of floating-point division /.

Now all we have to do is to find a way to calculate the value of the last element, and the number of elements, and this gives us the following python code:

def arithmetic_sum(start, stop, step=1):
    if (stop - start) * step <= 0:  # if step > 0 and stop <= start, or step < 0 and stop >= start
        return 0
    extra = (stop - start) % step
    if extra == 0:
        extra = step
    last_element = stop - extra
    number_of_elements = (last_element - start) // step   1
    return (number_of_elements * (start   last_element)) // 2

We can use pyton's builtin functions sum and range to test our function:

import random

for _ in range(10000):
    start = random.randrange(-1000, 1000)
    stop = random.randrange(-1000, 1000)
    step = random.randrange(-20, 20)
    if step == 0:
        step = 1
    if not (arithmetic_sum(start, stop, step) == sum(range(start, stop, step))):
        print('error on ', start, stop, step)
        print(arithmetic_sum(start, stop, step), sum(range(start, stop, step)))