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

Sum of Integers from 1 to n

Explore how to implement a recursive function to calculate the sum of integers from 1 up to n. Understand the concept of base and recursive cases, and how breaking down the problem helps in solving numerical recursion challenges.

We'll cover the following...

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

Natural numbers are positive numbers starting from 11. These can be written as:

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 number and sums up all the numbers from 11 up to that number.

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

Mathematical Notation

The sum of all numbers up to a number is equal to the sum of that number and the sum of all the numbers before it. 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

Javascript (babel-node)
function sumTill(targetNumber) {
  // Base case
  if (targetNumber == 1) {
    return targetNumber;
  }
  // Recursive case
  else {
    return targetNumber + sumTill(targetNumber - 1);
  }
}
// Driver Code
var targetNumber = 5;
console.log(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, where the execution halts, will now become our base case and the rest will be mapped to 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 have a look at an illustration:

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