CODEWITHSUNDEEP
javamethodsrecursion
Kailua Bum
Kailua Bum

Reputation: 1368

Java recursive method for summing the powers of 2, from 0 to N

so im trying to learn recursion (i know in this case recursion is not necessary)

i have already written this method, which works

public static int method(int number) {
    if(number == 0) {
        return 1;
    }
    else {
        return (int)Math.pow(2,number) + method(number-1);
    }
}

this works perfectly for summing the powers of 2 from 0 to number, but i was wondering if there was a way to replace the Math.pow() with another recursive method call

Upvotes: 1

Views: 11132

Answers (8)

Olaitan Adeboye
Olaitan Adeboye

Reputation: 172

My assumption from this question is that you want to add for example,

2 + 4 + 8 = 14 by calling func(3)
2 + 4 + 8 + 16 = 30 by calling func(4)

If so, you can try,

public static int SumPowerOf2(int number) {
if (number == 1) {
    return 2;
} else {
    return 2 + (2 * powerOf2(number - 1));
}

Going through each stack's frame, we should have below analysis for SumPowerOf2(3)

SumPowerOf2(3) => 2 + (2 * SumPowerOf2(2)) = 2 + 2(6) => 2 + 12 => 14
SumPowerOf2(2) => 2 + (2 * SumPowerOf2(1)) => 2 + 2(2) => 2 + 4 => 6
SumPowerOf2(1) => 2

Upvotes: 0

Ted Lam
Ted Lam

Reputation: 1

public static void main (String[] args){
    Integer output = 0;
    output = sumOfThePower(end, 1, 1); //input the number you like at 'end' to get the sum
    System.out.println(output);
}
public static Integer sumOfThePower (int end, int start, int mul){
if (start <= end){
    mul =2 * mul;
    return mul + sumOfThePower(end, start + 1, mul);
}
else{
    return 1;
}
}

Upvotes: 0

Sachin Nikam
Sachin Nikam

Reputation: 41

public class ComputePowerUsingRecursion {

    public static void main(String[] args) {    
        System.out.println(computePower(2,5));  // Passing 2 for power of 2
        System.out.println(computePower(2,-5)); // Number would be +ve or -ve
    }

    /**
     * <p>Compute power</p>
     * 
     *  p(x,n)  =  1              if(x=0)
     *          =  x*p(x,n-1)     if(n>0)
     *          =  (1/x)*p(x,n+1) if(n<0)  
     * @param x
     * @param n
     * @return
     */
    public static double computePower(double x, double n){
        //base case
        if(n==0){
            return 1;
        }else if(n>0){   //recursive condition for postive power
            return x*computePower(x, n-1);
        }else if(n<0){  //recursive condition for negative power
            return (1/x)*computePower(x, n+1);
        }else{ 
            return -1;
        }
    }
}

Upvotes: 1

Michał Kupisiński
Michał Kupisiński

Reputation: 3863

Maybe a little far from strict question your problem is to calculate sum of geometric series which is a series with a constant ratio between successive terms.

Your first element is equal to 1 (as 2 pow 0) and your ratio is equal to 2. So instead of using any recursion you can use it with common, well-know, equatation:

public long computGemetricSeries(int n) {
  long firstElem = 1;
  long ratio = 2;

  return (firstElem * (1 - Math.pow(ration,n)) / (1 - ratio));
}

Or for general term (not only power o 2):

public long computGeometricSeries(int n, double ration, double firstElem) {
   return (firstElem * (1 - Math.pow(ration,n)) / (1 - ration));
}

If you realy want recursion here you can change Math.pow(ration,n) to some recursion function proposed by other answers.

I think it won't help much as resolution to your question but will be a nice good-to-know answer.

Upvotes: 1

None
None

Reputation: 229

A more general solution:

public static int pow (int base, int ex) {
    if (ex == 0) {
        return 1;
    } else if (ex == 1) {
        return base;
    } else if(ex > 1) {
        return (pow(base, ex - 1) * base);
    } else {
        return pow(base, ex + 1) / base;
    }
}

This handle all possible cases where the passed values are integers..

Upvotes: 1

user2023812
user2023812

Reputation:

If you want to learn Recursion take a well known example of Fabonacci series.

public int getNthFibonacci( int n )
    {
        if ( n == 1 || n == 2 ) 
            return 1;

      else
        return getNthFibonacci( n-1 ) + getNthFibonacci( n-2 );
    }

public static void main(String[] args){

        Recursion myRecursor = new Recursion();
        System.out.println( myRecursor.getNthFibonacci(5) );

    }

But in your case it can be done by for loop also easily.

public static void main(String[] args) {

       int sum = 0;     
        for (int number = 20; number>0; number--)
        {
            sum += Math.pow(2,number);
        }

        System.out.println(sum);

}

Upvotes: 1

Saurabh
Saurabh

Reputation: 7964

You should define another recursive method to calculate Math.pow(2,n) recursively probably. However I would suggest to do bit shift operation of 2 to calculate Math.pow(2,n) quickly. For example shifting 2 << (n-1) will do hob here.

Upvotes: 2

Ted Hopp
Ted Hopp

Reputation: 234797

You can use this as a recursive power function:

public static int powerOf2(int number) {
    if (number == 0) {
        return 1;
    } else {
        return 2 * powerOf2(number - 1);
    }
}

Or, as a one-line body:

return number > 0 ? 2 * powerOf2(number - 1) : 1;

Upvotes: 6

Related Questions