Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Sum of Powers using recursion

1. ## Sum of Powers using recursion

i got a little bit of problem with my coding for finding the total sum..

the formula given to me is 1^k+2^k+...+n^k.
my coding as follows:
public int sumPowTo (int n, int k)
{

if ( k == 0)
{
return 1;
}
else if ( k == 1)
{
return n;
}

else
{
return  (n * sumPowTo(n,--k)) + (sumPowTo(n--,--k)) ;
}
}
it just doesnt add up to the right amout.

for example int sumPowTo(4,2) = 30
but i get 28

2. ## Re: Sum of Powers using recursion

Do not use the "--" operator when calling methods like that. The results will not be what you expect.
Instead you should just use "n - 1" or "k - 1". The problem with the "--" operator is that it matters whether you write it infront of a variable or behind the variable and for beginner this can be extremely confusing.

If your calculation does not return the right value, do your algorithm by hand on a piece of paper. Do it just the same way your computer would do it, perhaps you will find your mistake.

3. ## Re: Sum of Powers using recursion

i did try using n-1 and k-1 but the outcome still the same. i trace my program on the paper before i wrote the program the outcome is 30..

4. ## Re: Sum of Powers using recursion

Originally Posted by Red
i got a little bit of problem with my coding for finding the total sum..

the formula given to me is 1^k+2^k+...+n^k.
my coding as follows:
public int sumPowTo (int n, int k)
{

if ( k == 0)
{
return 1;
}
else if ( k == 1)
{
return n;
}

else
{
return  (n * sumPowTo(n,--k)) + (sumPowTo(n--,--k)) ;
}
}
it just doesnt add up to the right amout.

for example int sumPowTo(4,2) = 30
but i get 28
Can you please explain, why do you expect your code to have 30? Also, I checked this recursive method in java and it gives a result of 17, which is quite understandable if carefully counting code:

#1 n=4 and k=2, therefore first two conditions are taken off, and third else applies which is recursive
#2 as n=4 - it stays in first bracket and as --k is 1 now recursive method returns n - which is 4 again; altogether first brackets is given result of 16
#3 second bracket recursive, but values sent to it are 4 (as n still to be 4) and 0 (as k was after --k - 1 and another --k becomes 0)

Therefore I can't understand why do you get 28, and why do you expect it to be 30?

5. ## The Following User Says Thank You to skuch89 For This Useful Post:

Red (September 17th, 2014)

6. ## Re: Sum of Powers using recursion

Originally Posted by skuch89
Can you please explain, why do you expect your code to have 30? Also, I checked this recursive method in java and it gives a result of 17, which is quite understandable if carefully counting code:

#1 n=4 and k=2, therefore first two conditions are taken off, and third else applies which is recursive
#2 as n=4 - it stays in first bracket and as --k is 1 now recursive method returns n - which is 4 again; altogether first brackets is given result of 16
#3 second bracket recursive, but values sent to it are 4 (as n still to be 4) and 0 (as k was after --k - 1 and another --k becomes 0)

Therefore I can't understand why do you get 28, and why do you expect it to be 30?

from the tracing that i have made is 1^2+2^2+3^2+4^2 = 30 [int (4,2)}
or in other example 1^3+2^3+3^3+4^3+5^3 = 225 [int (5,3)]

that i need help in detecting the hole in my program and the reason why i cant get 30 as the answer.

7. ## Re: Sum of Powers using recursion

In future posts:

1. Post code that can be run,
2. Comment your code to describe what is (or should be) happening, and
3. Post sample runs that show or instructions to duplicate the undesired behavior.

I suggest adding some debug code to reveal what your recursive method is doing. For example, you might add a first line to the method like:

System.out.printf( "In sumPowTo() with n = %d and k = %d.\n", n, k );

You might also ask yourself how n^k is being calculated and included as a term of the series.

8. ## Re: Sum of Powers using recursion

Originally Posted by Red
from the tracing that i have made is 1^2+2^2+3^2+4^2 = 30 [int (4,2)}
or in other example 1^3+2^3+3^3+4^3+5^3 = 225 [int (5,3)]

that i need help in detecting the hole in my program and the reason why i cant get 30 as the answer.
Well, then your logic with recursive method is incorrect, think of this: you have a number 4 and 2 which are sent as parameters. Every time recursion happens first number (which is four) is changing. You started from 1^2, I suggest try to start from 4 instead and every time recursion happens go for -1, so next will be 3, then 2 and so on. Also if n (variable) reaches 0 - is return only from recursion, or if you decide go for 1 then return only k option. Hope this will give you some ideas how to work out algorithm

9. ## The Following User Says Thank You to skuch89 For This Useful Post:

Red (September 17th, 2014)

10. ## Re: Sum of Powers using recursion

@Red: Any progress?

In addition to the above suggestions, I noted that your assumptions for k == 0 and k == 1 are incorrect. Think about what happens for those cases. Pick small values for n and k and work through the solutions by hand for both cases. And then if those assumptions are wrong, what should the real base case be? A good starting point for defining the base case is to include the variable that is changed with each pass.

11. ## The Following User Says Thank You to GregBrannon For This Useful Post:

Red (September 17th, 2014)

12. ## Re: Sum of Powers using recursion

Originally Posted by GregBrannon
@Red: Any progress?

In addition to the above suggestions, I noted that your assumptions for k == 0 and k == 1 are incorrect. Think about what happens for those cases. Pick small values for n and k and work through the solutions by hand for both cases. And then if those assumptions are wrong, what should the real base case be? A good starting point for defining the base case is to include the variable that is changed with each pass.
yeap got it solved...

public int sumPowTo (int n, int k)
// Method for calculating sum of powers, which using the power method above
{
if ( n == 0) // Base case, if n equals to 0 the outcome will be 0
{
return 0;
}
else
{
int pow = (n* pow(n,k-1));
// Defining the power that being called from the above method
return  pow + (sumPowTo(n-1,k)) ;
}
}

made a mistake in declaring the base case.

now time for me to get back on the chess.. fyi this code is suppose to be not to run like other code it can only interact with the dev.. i was asked to not used any static or any system.out...

13. ## Re: Sum of Powers using recursion

import java.io.*;
class Power
{
public static void main(String args[]) throws IOException
{
Power call = new Power();
System.out.print("Enter number : ");
System.out.print("Enter power : ");