# Recursion problem

• 10-06-2010, 01:17 AM
luke
Recursion problem
I want to practice want I learned/didn't learn about recursion. I think I didn't learn much but I don't give up.
Here I want to calculate n*n + (n-1)*(n-1) + (n-2)*(n-2) + ... etc. using recursion.
Code:

static long sum( int n ) {

if( n == 0 )
return 0; //base case

else {

return (n*n) + sum(n-1)*(n-1);

}

I thought the above code was correct in order to give me the desired result but it is not. When I input for example 5 result is 317.
I tracked variable n. It does go 5-4-3-2-1-0-1-2-3-4-5 but the result is not 55.
Any ideas would be greatly appreciated.
• 10-06-2010, 01:50 AM
pbrockway2
Quote:

return (n*n) + sum(n-1)*(n-1);

That line doesn't look right. It's saying "figure out n squared, then add that to the sum of the squares up to (n-1) multiplied by (n-1)". Why that last bit?
• 10-06-2010, 01:59 AM
luke
Quote:

Originally Posted by pbrockway2
That line doesn't look right. It's saying "figure out n squared, then add that to the sum of the squares up to (n-1) multiplied by (n-1)". Why that last bit?

I thought it was supposed to be "n squared + (n-1) squared + (n-2) squared etc."
Thanks, pbrockway2. I thought n*n is calculated once and doesn't go into the recursion. The recursion is little confusing to me but I'll keep practicing.
• 10-06-2010, 02:32 AM
pbrockway2
I'm not sure if you've got this problem solved or not. (And I am deliberately loathe to provide code as this would defeat the whole purpose of the question.)

Here is your method rewritten with a more descriptive method name:

Code:

static long sumOfSquaresUpTo(int n) {
if(n == 0)
return 0; //base case

else {

return (n*n) + sumOfSquaresUpTo(n-1)  *(n-1);

}

And I'm wondering if you can see why that last multiplication is wrong.

After all the-sum-of-squares-up-to n is just n squared plus the-sum-of-squares-up-to (n-1).
• 10-06-2010, 04:02 AM
luke
Quote:

Originally Posted by pbrockway2
I'm not sure if you've got this problem solved or not. (And I am deliberately loathe to provide code as this would defeat the whole purpose of the question.)

Here is your method rewritten with a more descriptive method name:

Code:

static long sumOfSquaresUpTo(int n) {
if(n == 0)
return 0; //base case

else {

return (n*n) + sumOfSquaresUpTo(n-1)  *(n-1);

}

And I'm wondering if you can see why that last multiplication is wrong.

After all the-sum-of-squares-up-to n is just n squared plus the-sum-of-squares-up-to (n-1).

My code is working with no problems now (thanks to your help). I understand why *(n-1) shouldn't be there. To me recursion is little tricky and that's why I need more practicing.
• 10-06-2010, 07:14 AM
pbrockway2