What is recursive sum in python?

In this program, you'll learn to find the sum of natural numbers using recursive function.

To understand this example, you should have the knowledge of the following Python programming topics:

• Python if...else Statement
• Python Functions
• Python Recursion

In the program below, we've used a recursive function recur_sum() to compute the sum up to the given number.

Source Code

# Python program to find the sum of natural using recursive function

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

# change this value for a different result
num = 16

if num < 0:
   print("Enter a positive number")
else:
   print("The sum is",recur_sum(num))

Output

The sum is 136

Note: To test the program for another number, change the value of num.

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 ?

Simeon Visser

115k18 gold badges175 silver badges178 bronze badges

asked Nov 13, 2013 at 23:04

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)

answered Nov 13, 2013 at 23:08

Simeon VisserSimeon Visser

115k18 gold badges175 silver badges178 bronze badges

3

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

answered Nov 13, 2013 at 23:05

inspectorG4dgetinspectorG4dget

106k25 gold badges137 silver badges234 bronze badges

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

answered Nov 14, 2013 at 8:16

SzieberthAdamSzieberthAdam

3,7902 gold badges21 silver badges31 bronze badges

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

answered Nov 13, 2013 at 23:45

John La RooyJohn La Rooy

285k50 gold badges358 silver badges498 bronze badges

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

answered Jun 2, 2016 at 17:09

Using Recursion

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

sum_upto(100)

5050

answered May 3, 2019 at 8:13

TheRimalayaTheRimalaya

3,9122 gold badges27 silver badges35 bronze badges

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

Temani Afif

221k18 gold badges253 silver badges353 bronze badges

answered Jan 17, 2021 at 2:01

What is a recursive in Python?

How do you add recursive numbers in Python?

What is an example of a recursive?

How do you find the sum of a list using recursion?