AlgoMaster Logo

Sum of First N Natural Numbers (Recursive)

Last Updated: June 7, 2026

easy
3 min read

Understanding the Problem

The sum of the first n natural numbers is 1 + 2 + 3 + ... + n. For n = 5 that is 15, and for n = 1 it is just 1. A loop can build this total, but the same total can be expressed without any loop.

The sum up to 5 is 5 + (1 + 2 + 3 + 4), and the part in parentheses is the sum up to 4. The sum up to 4 is 4 + (1 + 2 + 3), the sum up to 3. Each total is one number plus the total just below it. That recursive definition translates directly into a function that calls itself on a smaller input.

Key Constraints:

  • n is at least 1, so there is always at least one number to add. The recursion still descends to 0, where the sum of no numbers is 0.
  • The result fits in a signed 32-bit integer. For n = 1000 the sum is 500500, well within range, so no wider type is needed.
  • The depth of the recursion grows with n. Each call waits on the one below it, so the call stack holds up to n frames at once.

Approach 1: Recursion

Intuition

The recursive definition sum(n) = n + sum(n - 1) is the whole algorithm, since a function can compute sum(n - 1) by calling itself with n - 1.

Any function that calls itself needs a stopping point, the base case. Here it is sum(0) = 0, since the sum of zero numbers is 0. Each call reduces n by one, so the chain moves toward 0 and is guaranteed to reach it. Once a call sees n = 0, it returns 0 without recursing, and the pending additions complete on the way back up.

Algorithm

  1. If n is 0, return 0. This is the base case that stops the recursion.
  2. Otherwise, return n plus the result of calling the function with n - 1.

Example Walkthrough

Input:

5
n

The first call is sum(5), which returns 5 + sum(4). To finish, it waits on sum(4), which returns 4 + sum(3), and so on down to sum(0), which returns 0 from the base case. Now the calls unwind: sum(1) returns 1 + 0 = 1, sum(2) returns 2 + 1 = 3, sum(3) returns 3 + 3 = 6, sum(4) returns 4 + 6 = 10, and sum(5) returns 5 + 10 = 15. The descent peeled off one number at a time, and each pending addition completed as the calls returned.

15
result

Code

Approach 2: Iterative Accumulator

Intuition

The same total can be built with a loop. Start an accumulator at 0, then add each integer from 1 up to n. This version keeps the work in a single stack frame instead of one frame per number, so it does not grow the call stack.

Algorithm

  1. Set an accumulator total to 0.
  2. For each integer i from 1 up to n, add i to total.
  3. Return total.

Example Walkthrough

Input:

5
n

The accumulator starts at 0. Adding 1 gives 1, adding 2 gives 3, adding 3 gives 6, adding 4 gives 10, and adding 5 gives 15. The loop has reached n, so it stops and returns 15. This matches the recursive result, since both approaches add the same five numbers, only in opposite directions.

15
total

Code