Sum of N numbers in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int sum(int n){
    if(n==0) return 0;
    return n + sum(n-1);
}
int main(){
    int n=5;
    printf("%d", sum(n));
}

C Output

Input:  
n = 5 

Output:  
15

C++ Program

#include <bits/stdc++.h>
using namespace std;
int sum(int n){
    if(n==0) return 0;
    return n + sum(n-1);
}
int main(){
    int n=7;
    cout << sum(n);
}

C++ Output

Input:  
n = 7 

Output:  
28

JAVA Program

class Main{
    static int sum(int n){
        if(n==0) return 0;
        return n + sum(n-1);
    }
    public static void main(String[] args){
        int n=4;
        System.out.print(sum(n));
    }
}

JAVA Output

Input:  
n = 4 

Output:  
10

Python Program

def sum_n(n):
    if n==0:
        return 0
    return n + sum_n(n-1)

n = 6
print(sum_n(n))

Python Output

Input:  
n = 6  

Output:  
21

Detailed Explanation

Problem Statement

We have to calculate the sum of the first n natural numbers recursively. Mathematically:

Sum(n) = n + (n-1) + (n-2) +. + 1

The recursion stops when n is reduced to zero (base case).

Step-by-Step Dry Run (Example: n = 5 in C)

sum(5) → returns 5 + sum(4)

sum(4) → returns 4 + sum(3)

sum(3) → returns 3 + sum(2)

sum(2) → returns 2 + sum(1)

sum(1) → returns 1 + sum(0)

sum(0) → returns 0 (base case)

Now the stack unwinds:

0 → 1 → 3 → 6 → 10 → 15.

Real-Life Analogy

Suppose we have a ladder that has n steps. If you need to count all steps from the top to the bottom, you start with the top step (n) and then have a friend count the rest (n-1). Eventually, when the friend reaches the bottom (step 0), counting will stop. This delegation of work is precisely the way recursion functions.

Why Recursion Works Here

The addition of numbers from 1 to n naturally decomposes into smaller additions:

Sum(n) = n + Sum(n-1)

This self-similarity makes it an ideal candidate for recursion. The base case (n=0) prevents further calls.

Complexity

Time Complexity: O(n) since we make one call per number.

Space Complexity: O(n) for the recursive call stack.

Common Mistakes

Missing the base case results in infinite recursion.

Known bugs: Using if(n==1) instead of if(n==0) can lead to problems for n=0 input.

Attempting with extremely large n may result in a stack overflow for languages such as C, C++, and Java.

Real Life Applications

It's more than an exercise in school — recursively summing sequences comes in handy when implementing divide-and-conquer algorithms, parallel algorithms, and tree traversal problems. Loops or formulas may be quicker when dealing with simple sums, but recursion makes you think about breaking down problems into smaller instances of the same problem.

Insights to Learn

This problem reinforces the base case concept and the idea that recursion is just a chain of deferred operations waiting to resolve once the smallest problem is solved. It’s a mental model you’ll need for more complex problems like depth-first search or dynamic programming.

SEO-Optimized Closing Paragraph

Computing the sum of N natural numbers recursively is a programming standard exercise for beginners that illustrates how to decompose a problem into smaller ones and solve it in steps. Recursion in C, C++, Java, and Python teaches you about base cases, the way the call stack is unwound, and why recursive thinking translates naturally to mathematical definitions. Mastery of this skill is the gateway to solving complex algorithmic problems, data structures, and coding interview problems where recursion plays a key role.