Python Program to Find Sum of Natural Numbers Using Recursion

You can find the sum of natural numbers using recursion in Python by defining a function like def sum_natural(n): return n if n == 1 else n + sum_natural(n-1) which calls itself until it reaches 1.

Examples

Input1

Output1

Input5

Output15

Input10

Output55

How to Think About It

To find the sum of natural numbers using recursion, think of the problem as adding the current number to the sum of all smaller numbers. Use a function that calls itself with the number one less than the current until it reaches 1, which is the base case.

Algorithm

1

Get the input number n.

2

Check if n is 1; if yes, return 1 as the sum.

3

Otherwise, return n plus the result of the function called with n-1.

4

Repeat until the base case is reached.

5

Return the final sum.

Code

python

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

number = 10
print("Sum of natural numbers up to", number, "is", sum_natural(number))

Output

Sum of natural numbers up to 10 is 55

Dry Run

Let's trace sum_natural(5) through the code

1

Call sum_natural(5)

Since 5 != 1, return 5 + sum_natural(4)

2

Call sum_natural(4)

Since 4 != 1, return 4 + sum_natural(3)

3

Call sum_natural(3)

Since 3 != 1, return 3 + sum_natural(2)

4

Call sum_natural(2)

Since 2 != 1, return 2 + sum_natural(1)

5

Call sum_natural(1)

Since 1 == 1, return 1

6

Calculate returns

sum_natural(2) = 2 + 1 = 3 sum_natural(3) = 3 + 3 = 6 sum_natural(4) = 4 + 6 = 10 sum_natural(5) = 5 + 10 = 15

Call	Return Value
sum_natural(1)	1
sum_natural(2)	3
sum_natural(3)	6
sum_natural(4)	10
sum_natural(5)	15

Why This Works

Step 1: Base Case

The function stops calling itself when n == 1, returning 1 to avoid infinite recursion.

Step 2: Recursive Call

For any number greater than 1, the function calls itself with n-1 to break down the problem.

Step 3: Summation

Each call adds the current number n to the sum returned by the smaller problem, building the total sum.

Alternative Approaches

Using a loop

python

def sum_natural_loop(n):
    total = 0
    for i in range(1, n+1):
        total += i
    return total

print("Sum using loop:", sum_natural_loop(10))

This method uses iteration instead of recursion and is often more efficient for large numbers.

Using formula

python

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

print("Sum using formula:", sum_natural_formula(10))

This uses the mathematical formula for sum of natural numbers and is the fastest method.

Complexity: O(n) time, O(n) space

Time Complexity

The function calls itself n times, so the time grows linearly with n.

Space Complexity

Each recursive call adds a new layer to the call stack, so space also grows linearly with n.

Which Approach is Fastest?

The formula method is fastest with O(1) time and space, while recursion and loop are O(n).

Approach	Time	Space	Best For
Recursion	O(n)	O(n)	Learning recursion and small inputs
Loop	O(n)	O(1)	Simple iterative calculation
Formula	O(1)	O(1)	Fastest for any input size