Thread: 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

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.

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..

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?

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.

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.

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

@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.

import java.io.*;
class Power
{
public static void main(String args[]) throws IOException
{
BufferedReader br = new BufferedReader(new
InputStreamReader(System.in));
Power call = new Power();
System.out.print("Enter number : ");
int x = Integer.parseInt(br.readLine());
System.out.print("Enter power : ");
int y = Integer.parseInt(br.readLine());
System.out.println("\n" +x +"^" +y +" = "+call.findPower(x,y));
}
int findPower(int x, int y)
{
if(y==0)
return 1;
else if(y==1)
return x;
else
return x*findPower(x,y-1);
}
}