Sum of Numbers Using Recursion in Java
beginner· Recursion · Recursion
Problem
The sum of the first n numbers is just n added to the sum of the first n minus one numbers, which is exactly the kind of self-referencing definition recursion expresses directly.
Given a number n, find the sum of every integer from 1 to n using recursion.
Input
n = 10
Output
Sum: 55
Java Program
Java
public class SumOfNumbersRecursion {
static int sum(int n) {
if (n == 0) return 0; // sum of no numbers is zero
return n + sum(n - 1); // deferred until the smaller call returns
}
public static void main(String[] args) {
int n = 10;
System.out.println("Sum: " + sum(n));
}
}Output
Sum: 55
Core Logic
Adding the current number to whatever the smaller call returns builds the total from the bottom up as the recursion unwinds.
How It Works
- 1The base case
if (n == 0) return 0;stops the recursion, since the sum of no numbers at all is zero. - 2Every other call returns
n + sum(n - 1), deferring its own addition until the smaller call finishes. - 3The calls descend
sum(10) → sum(9) → ... → sum(0), then unwind back up, adding one number at each step. - 4The very last addition to complete is
10 + sum(9), which is also the first call made.
For
n = 10, the recursion unwinds as 0, 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ending at the total 55.💡
Key Point: Just like the recursive factorial, this call still owes an addition once the smaller call returns — the sum only becomes final once every pending addition has unwound back to the top.
Complexity
Time Complexity: O(n)Space Complexity: O(n)
Why: One recursive call adds each number into the total, and the call stack grows to depth n before any addition can actually happen.
Key Concepts
recursionbase casedeferred addition