Search⌘ K
AI Features
Home
Courses
Recursion for Coding Interviews in Python

Sum of Integers from 1 to n

Explore how to use recursion to find the sum of integers from 1 to n. This lesson breaks down the problem into base and recursive cases, helping you understand how recursion operates with numeric sequences.

We'll cover the following...

What does the sum of integers from 1 to nn mean?

Natural numbers are all positive numbers starting with 11. These can be written as follows:

1,2,3,4,5,6,7,8,9,10......1,2,3,4,5,6,7,8,9,10......

We want to write a program that takes a specific number and adds all the numbers from 11 until that number.

For example, if n=5n = 5, the sum of numbers from 11 to 55 is: 1+2+3+4+5=151 + 2 + 3 + 4 + 5 = 15.

Mathematical Notation

Let’s write it down mathematically:

∑i=15i\sum_{i=1} ^{5} i

== 55 ++ ∑i=14i\sum_{i=1} ^{4} i

== 55 ++ 44 ++ ∑i=13\sum_{i=1} ^{3}

== 55 ++ 44 ++ 33 ++ ∑i=12\sum_{i=1} ^{2}

.

.

.

=5+4+3+2+1=5+4+3+2+1

Generic Mathematical Notation

∑i=1ni\sum_{i=1} ^{n} i

== nn ++ ∑i=1n−1i\sum_{i=1} ^{n-1} i

== nn ++ (n−1)(n-1) ++ ∑i=1n−2\sum_{i=1} ^{n-2}

.

.

.

== nn ++ (n−1)(n-1) +(n−2)+(n-2) $ … +2+1$

Implementation

Python 3.5
def sumTill(targetNumber) :
  # Base Case
  if targetNumber == 1 :
    return targetNumber
  # Recursive Case
  else :
    return targetNumber + sumTill(targetNumber - 1)
# Driver Code
targetNumber = 5
print(sumTill(targetNumber))

Explanation

Let’s begin by breaking down the solution into subtasks:

sum of numbers from 1 to 5=5+sum of numbers from 1 to 4sum \: of \: numbers \: from \: 1 \: to \: 5 = 5 + sum \: of \: numbers \: from \: 1 \: to \: 4 sum of numbers from 1 to 4=4+sum of numbers from 1 to 3sum \: of \: numbers \: from \: 1 \: to \: 4 = 4 + sum \: of \: numbers \: from \: 1 \: to \: 3

.

.

sum of numbers from 1 to 1=1sum \: of \: numbers \: from \: 1 \: to \: 1 = 1

The last statement is where execution halts, therefore it will become the base case. The rest will be mapped to the recursive case: sum of numbers from 1 to n=n+sum of numbers from 1 to n−1sum \: of \: numbers \: from \: 1 \: to \: n = n + sum \: of \: numbers \: from \: 1 \: to \: n - 1

Let’s take a look at another example in the next lesson.