Grokking the Art of Recursion for Coding Interviews
Ask Author
Back to course home

0% completed

Solution: Basic Sum
Table of Contents

Problem Statement

Solution

Code

Time and Space Complexity

Problem Statement

Calculate the Sum of the First N Natural Numbers Using a Recursive Approach.

The sum of first N natural numbers is equal to N + (N-1) + (N-2) + ... + (3) + (2) + (1). The following table shows a sample input/output description table:

Input (s)Output (s)Explanation
N = 5Sum = 15The first 5 natural numbers are 1, 2, 3, 4, and 5. The sum of these numbers is 1 + 2 + 3 + 4 + 5 = 15.
N = 10Sum = 55The first 10 natural numbers are 1, 2, 3, 4, 5, 6, 7, 8, 9, and 10. The sum of these numbers is 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55.
N = 1Sum = 1The first natural number is 1. The sum of this number is 1.

Solution

The algorithm to calculate the sum of the first N natural numbers using recursion can be defined as follows:

  1. If N is equal to 0 or less, return 0 (base case).
  2. Otherwise, return the sum of number N and the recursive call to calculate the sum of N-1.

The recursive approach works by breaking down the problem into smaller subproblems. We calculate the sum of N by adding N to the sum of the numbers from 1 to N-1. This process continues until the base case is reached, where N is 0 or less.

The base case stops the recursion and returns 0. By summing the numbers in a decreasing order, we ensure that each number is added to the previous sum, eventually giving us the total sum of the first N natural numbers.

Example dry run to calculate Sum of first 5 Natural numbers
Example dry run to calculate Sum of first 5 Natural numbers

Code

Here is the code for this algorithm:

Python3
Python3
. . . .

Time and Space Complexity

The time complexity of the algorithm is O(N) since we make N recursive calls, where N is the input natural number.

The space complexity of the algorithm is also O(N) because the maximum depth of the recursion is N. Each recursive call adds a new stack frame, consuming additional space on the call stack.

Mark as Completed

Table of Contents

Problem Statement

Solution

Code

Time and Space Complexity