# Thread: Is this the most efficient solution for taking the sum?

1. Member
Join Date
Oct 2013
Posts
63
Rep Power
0

## Is this the most efficient solution for taking the sum?

Here are two methods, iterative and recursive, which calculates the sum of all positive integers between 1 and a given integer n (input into the method). We know that as n gets larger, the solution takes longer to solve. Is there you think a much more efficient way of writing these codes?

NOTE: I'VE CROSS POST HERE Is this the most efficient solution for taking the sum? (Beginning Java forum at JavaRanch)
I'll let everyone know whether my answer is resolved from the other forum so I don't waste anybody's time. Thanks!

Iterative Method:
Java Code:
```public static int iterativeSum(int n) {
int sum = 0;
if ((n == 0) || (n == 1)) {
return n;
}

for (int i = 0; i < n ; n--) {
sum = sum + n;
}

return sum;
}```

Recursive Method:
Java Code:
```
public static int recursiveSum(int n) {
int sum = 0;
if ((n == 0) || (n == 1)) {
return n;
} else {
sum = recursiveSum(n-1) + n;
}
return sum;```
Last edited by csanch11; 11-15-2015 at 07:44 PM.

2. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Is this the most efficient solution for taking the sum?

Originally Posted by csanch11
Is there you think a much more efficient way of writing these codes?
Java Code:
`int sum = (n*(n+1))/2;`
Regards,
Jim

3. Member
Join Date
Oct 2013
Posts
63
Rep Power
0

## Re: Is this the most efficient solution for taking the sum?

Hey jim, I would have never thought of that. Is that some sort of formula that you look up, or does it come from experience?

4. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Is this the most efficient solution for taking the sum?

Experience based on math courses. Probably algebra or whenever one learns about summation of infinite and finite series (both arithmetic and geometric series). Here is how it's derived.

S = 1 + 2 + 3 + 4 + 5 + ..... + n
S = n + n-1 + n-2 + n-3 + n-4 + ......+ 1

Add each column of corresponding terms.

2S = 1+n + 1+n + 1+n + 1+n + .....................1+n (and since you have n of these)
2S = n(1+n) now divide by 2

S = n(1+n)/2

And as a bonus, if you square the above formula, you get the sum of consecutive cubes from 1 to n.

Regards,
Jim

5. Member
Join Date
Oct 2013
Posts
63
Rep Power
0

## Re: Is this the most efficient solution for taking the sum?

Why did S = 1 + 2 + 3 turn into n + n -1 + n-2 ???

6. Senior Member
Join Date
Jan 2013
Location
Northern Virginia, United States
Posts
6,226
Rep Power
14

## Re: Is this the most efficient solution for taking the sum?

Originally Posted by csanch11
Why did S = 1 + 2 + 3 turn into n + n -1 + n-2 ???
Because I am rewriting the sum in reverse.

s = 1 + 2 + 3
s = 3 + 2 + 1

2s = 4 + 4 + 4
2s = 3(4)
s = 6

Regards,
Jim

7. Moderator
Join Date
Feb 2009
Location
New Zealand
Posts
4,716
Rep Power
18

## Re: Is this the most efficient solution for taking the sum?

> (Jim) And as a bonus, if you square the above formula, you get the sum of consecutive cubes from 1 to n.

Wikipedia gives a lovely picture proof of this: https://upload.wikimedia.org/wikiped...rem_3D.svg.png

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•