Recursive function to calculate sum?

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 use inputs 5, I want to program to calculate the sum of 5+4+3+2+1. What am I doing wrong ?

Solution 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)

Solution 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

Solution 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

Solution 4

Using Recursion

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

sum_upto(100)

5050

Solution 5

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

View more solutions

Comments

[kiasy]

Now how would I print the sum ? @Simeon Visser

[chepner]

print sum(n) - let the return value of sum be the argument to print.

[Simeon Visser]

@kiasy yes, let sum compute the result and then, after it is done, print it.