☕ DSA Java Articles

Topics › Basics › Learn Basic Recursion

Sum of First N Numbers

Easy TUF ID 386 A2Z

Java source ↗ Edit this article ↗

Problem

Given an integer N, return the sum 1 + 2 + 3 + ... + N. For N ≤ 0 the sum is empty and the answer is 0.

The arithmetic is trivial; the problem is on the recursion sheet because it is the cleanest place to learn the difference between parameterised recursion (carry the partial answer down in a parameter) and functional recursion (let each call return its answer and combine on the way up). Every recursive algorithm you write later will use one of these two styles, and often both.

Constraints: 0 ≤ N ≤ 10^5 in the usual statement. Note that the answer for N = 10^5 is about 5 × 10^9, which does not fit in a 32-bit int, so the methods return long.

Example 1

N = 5
answer = 15               // 1 + 2 + 3 + 4 + 5

Example 2

N = 1
answer = 1                // the sum of just one number

Example 3

N = 0
answer = 0                // empty sum

Approach 1: Loop

Intuition. Keep a running total and add each number from 1 to N. This is the baseline every other approach must match.

Algorithm.

  1. Set sum = 0.
  2. For i from 1 to N, do sum += i.
  3. Return sum.
static long iterative(int n) {
    long sum = 0;
    for (int i = 1; i <= n; i++) sum += i;
    return sum;
}

Complexity. Time O(n), one addition per number. Space O(1).

Approach 2: Parameterised recursion

Intuition. Replace the loop variable and the accumulator by two parameters: i, the number we are about to add, and runningSum, the total so far. Each call adds i into the running sum and hands the rest of the job to the call for i - 1. When i drops below 1, there is nothing left to add, and the base case simply returns the accumulator. No work is done after the recursive call, so the answer is already complete at the bottom of the recursion and is passed back up unchanged.

Algorithm.

  1. Start with sumDown(n, 0).
  2. In sumDown(i, runningSum): if i < 1, return runningSum.
  3. Otherwise return sumDown(i - 1, runningSum + i).
static long parameterised(int n) {
    return sumDown(n, 0);
}

private static long sumDown(int i, long runningSum) {
    if (i < 1) return runningSum;           // base case: nothing left to add
    return sumDown(i - 1, runningSum + i);  // add i now, let the smaller problem finish the job
}

Complexity. Time O(n): n + 1 calls. Space O(n) for the call stack. (The recursive call is in tail position; some languages reuse the frame, but the JVM does not, so the stack still grows.)

Approach 3: Functional recursion

Intuition. Define the answer recursively instead of simulating the loop: the sum of the first n numbers is n plus the sum of the first n - 1 numbers, and the sum of the first 0 numbers is 0. Translate that sentence directly: the function returns a value, and the combination (n + ...) happens after the recursive call returns. This is the style you use when the problem is naturally defined in terms of a smaller instance of itself, which is most of the time.

Algorithm.

  1. If n < 1, return 0 (base case).
  2. Otherwise return n + functional(n - 1).
static long functional(int n) {
    if (n < 1) return 0;                    // base case: the empty sum is 0
    return n + functional(n - 1);
}

Dry run on N = 3. Calls go down the first column; results come back up the last column.

call returns
functional(3) 3 + functional(2) = 3 + 3 = 6
functional(2) 2 + functional(1) = 2 + 1 = 3
functional(1) 1 + functional(0) = 1 + 0 = 1
functional(0) 0 (base case)

Complexity. Time O(n): n + 1 calls. Space O(n) for the call stack; here the frames genuinely must stay alive because each one has an addition left to do after its callee returns.

Approach 4: Closed-form formula

Intuition. Pair the first and last term, the second and second-to-last, and so on: 1 + N, 2 + (N - 1), … Every pair sums to N + 1 and there are N / 2 pairs, giving N(N + 1) / 2. (When N is odd the middle element is (N + 1) / 2, and the formula still works out.) This is the right answer in production code; the recursive versions exist to teach recursion.

One of N and N + 1 is even, so the product is always divisible by 2 and integer division is exact.

Algorithm.

  1. If n < 1, return 0.
  2. Return n * (n + 1) / 2, computed in long.
static long formula(int n) {
    if (n < 1) return 0;
    return (long) n * (n + 1L) / 2;
}

Complexity. Time O(1), space O(1).

Edge cases and pitfalls