CODEWITHSUNDEEP
javarecursion
kachilous
kachilous

Reputation: 2529

Recursively compute the value of base to the n power

Here is what I have for my solution:

 public int powerN(int base, int n) {

    if(n == 0)
       return 1;

    else if(n % 2 == 0)
       return base * base;

    else
       return base * powerN(base, n-1); 

 }

However, if n > 3 then this function doesn't work. For instance, powerN(2, 4) yields 4 and powerN(2, 5) yields 8. I know that a much simpler solution exists, but it just bothers me that I can't figure out why this is not working correctly.

Upvotes: 4

Views: 47441

Answers (10)

Andrii Vynnyk
Andrii Vynnyk

Reputation: 69

public static int powerN(int base, int n ){
    if (n==0){
        return 1;
    }else
        return base*powerN(base,n-1);
}

Upvotes: 0

Umair Zia
Umair Zia

Reputation: 15

Here is answer in C++, this is a series of a^b =

int power(int a, int b)
{
   int k = a;
   int c = b;
   if (c == 1)
    {
        return a;
    }
   else if (c == 0)
    {
        return 1;
    }
   else if (c >= 1)
   {
        c--;
        k = k*power(k,c);
   }
   cout << k << endl;
   return k;

}

int main()
{
    cout << "Enter a number " << endl;
    int n;
    cin >> n;
    cout << "Enter power " << endl;
    int c1 = 0;
    cin >> c1;
    cout << endl ;
    cout << "These are all the powers up to " << n << " to the power " << c1 << endl;
    power(n,c1);
    return 0;
}

Upvotes: 0

kingsley peter
kingsley peter

Reputation: 1

class Square{
    int r=1;
     int power(int n, int p) throws Exception
    {
         int s=n;
        if(n<0||p<0)
        {
        throw new Exception("n and p must be positive");
        }

    if(p==2)
    {
        return n*n*r;
    }
    else
    {
        r=r*n;
        return power(n,p-1);
    }

    }
}

Upvotes: 0

Harmanbir Rai
Harmanbir Rai

Reputation: 1

public int powerN(int base, int power) {
    if (power == 1)
        return base;
    else if (power % 2 == 0) {
        int x = powerN(base, power / 2);
        return x * x;
    } else {
        int x = powerN(base, (power - 1) / 2);
        return x * x * base;
    }
}

Upvotes: -1

Kerem Baydoğan
Kerem Baydoğan

Reputation: 10720

Buggy code is:

else if(n % 2 == 0)
   return base * base;

this if will catch every power of 2. So 0,2,4,8 causes wrong calculation.

The only corner case you should worry about is when n <= 0.

Here is corrected code:

public static int powerN(int base, int n) {
    if (n < 0) {
        throw new IllegalArgumentException("Illegal Power Argument");
    }
    if (n == 0) {
        return 1;
    } else {
        return base * powerN(base, n - 1);
    }
}

Here is the test:

public static void main(String args[]) throws NullPointerException {
    for (int i = 0; i < 10; i++) {
        System.out.println(powerN(2, i));
    }
}

and output:

run:
1
2
4
8
16
32
64
128
256
512
BUILD SUCCESSFUL (total time: 1 second)

Upvotes: 2

Pratik Bhatt
Pratik Bhatt

Reputation: 687

Your problem is the code

if (n % 2 == 0) return base * base;

This makes your function return square of the base whenevr the power (n) is even and cube whenever it is odd. The only terminating condition u need is n==0 return 1 and it should work to your specification of base to the power n recursively

Upvotes: -1

Josh Lee
Josh Lee

Reputation: 177895

else if(n % 2 == 0)
   return base * base;

This bit is incorrect — it returns the square for any even power, not just 2. It looks like you’re trying to implement the square and multiply optimization. So if you want to compute powerN(base, n), what recursive call can you make that takes advantage of the fact that n is even? What new values will you pass in for base and n? Use the identity that b2‌n = (b2)n.

Upvotes: 5

Wesley
Wesley

Reputation: 10872

Into pseudocode

Let me translate your code into pseudocode:

public int powerN(int base, int exponent)  {
    if the exponent is 0
        then return 1
    otherwise, if the exponent is even
        then return base * base
    otherwise
        base * powerN(base, exponent - 1)
}

The second branch has a logic error. What your code is saying is this: "As long as the exponent is even, the result should be base * base (that is, base squared)". You've already mentioned that this is the result you get when you run your code.

How to solve it

What you probably want to do is to raise base to half the exponent (base * base * base * ... for exponent / 2 times), and then multiply that number by itself. That way, you get base multiplied by itself exponent times.

In pseudocode:

otherwise, if the exponent is even
    then return powerN(base, exponent / 2) * powerN(base, exponent / 2)

Realistically, this would actually be the following:

otherwise, if the exponent is even
    then {
        let x = powerN(base, exponent / 2)
        return x * x
    }

Done. Mostly.

Translate that back to Java and you'll be set.

Upvotes: 4

GKK
GKK

Reputation: 384

For computing the power you only need to consider the special case of x^0, for all others (n>0) you can use the recursion of x*powerN(x, n-1)

Upvotes: 0

lhf
lhf

Reputation: 72422

In the even case you need base = powerN(base, n/2);before returning.

Upvotes: 1

Related Questions