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