Recursive function to calculate sum of 1 to n?

Question

This is what I've got and I'm not sure why it's not working:

def sum(n):
    if n > 0:
        print(n)
        return sum(n) + sum(n-1)
    else:
        print("done doodly")

number = int(input(":  "))
sum(number)

For example if the user inputs 5, I want the program to calculate the sum of 5+4+3+2+1. What am I doing wrong?

---

^{For the non-recursive version of this question, see Sum of the integers from 1 to n}

Answer 1

Two things:

• Calling sum(n) when computing sum for n won't do you much good because you'll recurse indefinitely. So the line return sum(n)+sum(n-1) is incorrect; it needs to be n plus the sum of the n - 1 other values. This also makes sense as that's what you want to compute.
• You need to return a value for the base case and for the recursive case.

As such you can simplify your code to:

def sum(n):
    if n == 0:
        return 0
    return n + sum(n - 1)

Answer 2

You forgot to return when n==0 (in your else)

>>> def Sum(n):
...   if not n:
...     return 0
...   else:
...     return n + Sum(n-1)
... 
>>> Sum(5)
15

Answer 3

Recursion is a wrong way to calculate the sum of the first n number, since you make the computer to do n calculations (This runs in O(n) time.) which is a waste.

You could even use the built-in sum() function with range(), but despite this code is looking nice and clean, it still runs in O(n):

>>> def sum_(n):
...     return sum(range(1, n+1))
...
>>> sum_(5)
15

Instead recursion I recommend using the equation of sum of arithmetic series, since It runs in O(1) time:

>>> def sum_(n):
...     return (n + n**2)//2
...
>>> sum_(5)
15

Answer 4

You can complicate your code to:

def my_sum(n, first=0):
    if n == first:
        return 0
    else:
        return n + my_sum(n-1, (n+first)//2) + my_sum((n+first)//2, first)

The advantage is that now you only use log(n) stack instead of nstack

Answer 5

I think you can use the below mathematical function(complexity O(1)) instead of using recursion(complexity O(n))

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

Answer 6

Using Recursion

def sum_upto(n):
  return n + sum_upto(n-1) if n else 0

sum_upto(100)

5050

Answer 7

Please have a look at the below snippet in regards to your request. I certainly hope this helps. Cheers!

def recursive_sum(n):
    return n if n <= 1 else n + recursive_sum(n-1)

# Please change the number to test other scenarios.
num = 100

if num < 0:
   print("Please enter a positive number")
else:
   print("The sum is",recursive_sum(num))