Find the Sum of Natural Numbers With and Without Recursion

The sum of the first N natural numbers is N*(N+1)/2, and most placement tests ask you to prove it with code in at least two different ways.

What the problem is asking

Natural numbers are the positive integers starting at 1: 1, 2, 3, 4, and so on. Zero and negative numbers are excluded by definition. Given N as input, the task is to output the total of every integer from 1 to N, inclusive.

For N=5, the expected output is 15 (since 1+2+3+4+5=15). For N=10, the output is 55. The problem has three standard programming solutions, each with a different time-space profile. Placement screening rounds expect candidates to know at least two of them and to articulate the difference between them.

The legacy article on this topic showed two code snippets with no explanation of why those approaches work or how they compare. This version walks through all three, with step-by-step traces and the trade-off discussion that interviewers actually probe.

This is also one of those problems where knowing the formula is not enough. Interviewers ask for the iterative version to check loop writing fluency, and for the recursive version to check whether candidates can reason about a call stack. Answering with only the formula earns a follow-up, not a pass.

The formula method: O(1) time, O(1) space

The closed-form identity for the sum of the first N natural numbers is described as the triangular number formula:

Sum = N * (N + 1) / 2

A quick way to see why this is correct: pair up integers from opposite ends of the sequence. The pair (1, N) sums to N+1. The pair (2, N-1) also sums to N+1. The pair (3, N-2) also sums to N+1. There are N/2 such pairs in total, giving N/2 * (N+1) = N*(N+1)/2.

Verified from first principles:

• N=5: 5 * 6 / 2 = 15
• N=10: 10 * 11 / 2 = 55
• N=100: 100 * 101 / 2 = 5,050

No loop, no recursion. One arithmetic expression, constant time regardless of N.

Python — formula

def sum_formula(n):
    return n * (n + 1) // 2

n = int(input("Enter n: "))
print("Sum:", sum_formula(n))

Integer division (//) avoids a floating-point result. For any positive integer N, N*(N+1) is always even (one of the two consecutive integers is always divisible by 2), so the exact integer quotient is guaranteed.

C — formula

#include <stdio.h>

long long sum_formula(long long n) {
    return n * (n + 1) / 2;
}

int main() {
    long long n;
    scanf("%lld", &n);
    printf("Sum: %lld\n", sum_formula(n));
    return 0;
}

long long avoids integer overflow. For large N, the product n*(n+1) grows quickly and a 32-bit int can overflow. Using long long handles the full input range typical in placement tests.

Iterative approach: O(n) time, O(1) space

A for-loop accumulates the total by adding each integer from 1 to N. Memory usage is constant: one accumulator variable, regardless of how large N is. This is the safest choice when the input range is unknown or large.

Python — iterative

def sum_iterative(n):
    total = 0
    for i in range(1, n + 1):
        total += i
    return total

n = int(input("Enter n: "))
print("Sum:", sum_iterative(n))

C — iterative

#include <stdio.h>

long long sum_iterative(long long n) {
    long long sum = 0, i;
    for (i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

int main() {
    long long n;
    scanf("%lld", &n);
    printf("Sum: %lld\n", sum_iterative(n));
    return 0;
}

Step-by-step trace for N=5

• Start: total = 0
• i = 1: total = 0 + 1 = 1
• i = 2: total = 1 + 2 = 3
• i = 3: total = 3 + 3 = 6
• i = 4: total = 6 + 4 = 10
• i = 5: total = 10 + 5 = 15
• Return: 15

The loop visits each value exactly once, so time complexity is O(n). No additional memory is allocated beyond the accumulator variable, so space complexity is O(1). There is no call-stack growth.

Recursive approach: O(n) time, O(n) space

Recursion expresses the sum as a self-referencing relationship: sum(n) = n + sum(n-1), with the base case sum(1) = 1. Each function call adds one frame to the call stack, so memory usage grows linearly with N. The recursion unwinds once the base case is reached.

Python — recursive

def sum_recursive(n):
    if n == 1:
        return 1
    return n + sum_recursive(n - 1)

n = int(input("Enter n: "))
print("Sum:", sum_recursive(n))

C — recursive

#include <stdio.h>

long long sum_recursive(long long n) {
    if (n == 1) return 1;
    return n + sum_recursive(n - 1);
}

int main() {
    long long n;
    scanf("%lld", &n);
    printf("Sum: %lld\n", sum_recursive(n));
    return 0;
}

Call trace for N=5

• sum(5) calls sum(4)
• sum(4) calls sum(3)
• sum(3) calls sum(2)
• sum(2) calls sum(1), which returns 1 (base case)
• sum(2) returns 2 + 1 = 3
• sum(3) returns 3 + 3 = 6
• sum(4) returns 4 + 6 = 10
• sum(5) returns 5 + 10 = 15

Each level of the call waits for the level below it to return before it can compute its own result. This is what creates the O(n) stack depth.

Python’s recursion ceiling

According to the Python documentation, the interpreter’s default maximum recursion depth is 1,000 frames. For N above roughly 994, the function call sequence will exhaust the stack and raise RecursionError. The iterative or formula approach is the correct choice for large N in Python.

C does not expose a configurable recursion limit the same way, but the operating system imposes a stack-size ceiling. Very large N values can still cause a stack overflow in C; the iterative approach avoids that risk entirely.

Comparing all three approaches

Approach	Time	Space	Stack risk	Best for
Formula	O(1)	O(1)	None	Any N; fastest, fewest lines
Iterative	O(n)	O(1)	None	Large N; no stack concern
Recursive	O(n)	O(n)	Yes (Python N over 994)	Demonstrating recursion

In production code, the formula is always the right answer: one line, no loop, no stack growth. Placement tests ask for the iterative and recursive versions to check whether candidates understand the relationship between a problem’s structure and the code that solves it, not just whether they know the outcome.

A common interview mistake is answering “both iterative and recursive are O(n), so they’re the same.” They share the same time complexity but differ on space. The recursive approach uses O(n) stack frames; the loop uses O(1). That distinction is what the follow-up question is testing.

The choice also depends on the test environment. Online judges with N up to 10^9 as input will time out an O(n) loop in strict settings; only the formula passes cleanly. For the standard placement test range (N up to a few thousand), all three work within time limits, so the question shifts to space and clarity.

Where this appears in placement tests

Technical screening rounds at service-tier companies commonly include problems at this difficulty level to filter candidates in the first coding stage. The expected answer sequence is: implement the iterative version, implement the recursive version, state the complexity for each, and explain what changes when N is very large.

Candidates who give only one implementation and don’t mention the trade-offs leave points on the table. Knowing the O(1) formula is a bonus that signals mathematical awareness; interviewers notice it even when they don’t explicitly ask.

Practice with related problems builds the instinct for choosing approaches: number-pattern exercises sharpen loop fluency with structured output, dynamic-programming problems push recursive thinking into two-dimensional state spaces, and number-range problems apply the same iteration patterns to search problems with different termination conditions.

Gauss’s formula reduces an O(n) loop to a single arithmetic step by exploiting a structural property of the sequence. Recognising that kind of reduction (finding the insight that collapses a brute-force loop to a constant-time expression) is a thinking pattern that carries across many problem types. If you want to build that instinct through real projects before your placement cycle, TinkerLLM at ₹299 is a low-stakes entry point.