0

I am very new to programming, and Java is my first real language. At this point in class we are touching on recursion, and have been asked to make a method that fits certain parameters:

The method is as such: public void power(int p) where we cannot change the formal parameters of the method. I've looked into this elsewhere and it seems that a lot of solutions involve adding the int n (for the number to have the power performed upon) as a parameter.

When writing similar methods we were encouraged to use "this" as our representation of what we are trying to change. Normally "this" is used in instance methods i.e.: this.increment().

When I write pseudocode for it I find I want to do the following: 

public void power(int p) {
    assert p >= 0 : "Violation of: p >= 0";
    int x = 0;

    if (p == 0) {
        return 0;
    }
    if (p % 2 == 0) {
        x = this.power(p / 2);
        return x * x;
    } else {
        return this * this.power(p - 1);
    }

I just don't know how to write it so that it can actually run with eclipse and java. Any insight would be appreciated!

Tori
  • 1
  • 4
  • `return this * this.power(p - 1);` looks weird – Benj Jun 29 '15 at 01:43
  • This is not pseudo-code, this code compiles (almost). What is the use of a power method returning void ? You should return a result. And as Benj pointed... the last line is weird. What is the class you are working on, give us some context – Dici Jun 29 '15 at 01:43
  • And you need to provide the value that is being raised to the power. Is it meant to work as an operator? – winwaed Jun 29 '15 at 01:45
  • well, this **is** java-code (though it won't compile. apart from that you'll encounter some problems: `x ^ y` is a binary operator (always 2 arguments). you should clarify what you actually want to achieve before asking a question. –  Jun 29 '15 at 01:45
  • Sorry for the confusion! I am given a java program to actually call my method and test it with given inputs for n ( or as I called it x) and p. That is what I have to go off of to see if my code actually works. So it will return a value once I run it in my other code. The class I'm in is the first in a series for computer science engineering where we are learning the basics as far as constructors, methods, objects, recursion, and the like. I am really having a difficult time with being able to execute what I "see" should work. – Tori Jun 29 '15 at 01:49
  • yes, but what does your code have to achieve in order to 'work' ? what are you trying to compute? what is `power(p)`? – Benj Jun 29 '15 at 01:50

4 Answers4

2

The following stop condition is wrong, it should return 1.

if (p == 0) {
  return 0; // should return 1
}

If you use this, you cannot use multiplication operator * in Java. You can have a multiplyBy function that should not mutate the callee:

public int multiplyBy(int x) {
    return this.value * x;
}

And as you can see in the above method, you need to have an instance property for storing your integer value. So your code would now look like: 

public void power(int p) {
  assert p >= 0 : "Violation of: p >= 0";
  int x = 0;

  if (p == 0) {
    return 1;
  }
  if (p % 2 == 0) {
    x = this.power(p / 2);
    return x * x;
  } else {
    return this.multiplyBy(this.power(p - 1));
  }
}
mostruash
  • 4,169
  • 1
  • 23
  • 40
  • There's the correlation I was missing! I did not realize that when I use "this" I cannot use *. In what way would this mutate the callee? Also thinking of instance properties as a way of storing my integers is a great way of thinking about it. – Tori Jun 29 '15 at 02:02
  • The following would mutate the callee which would have broken your recursion: `this.value = this.value * x;` in `multiplyBy`. – mostruash Jun 29 '15 at 02:05
  • Using `this` with `*` operator requires an operation overloading mechanism which doesn't exist in Java, but exists in languages like C++ and swift and many others. – mostruash Jun 29 '15 at 02:07
  • that's fascinating, it also makes a lot of sense now why we were directed to really only use multiplyBy10( ), divideBy10( ), and isZero( ) in this code. These are API specific to our school's library. – Tori Jun 29 '15 at 02:09
1

When doing recursion, you have to think of two things.

  • Base case: When do you stop recursion?
  • Recursive case: When do you continue?

For a power, consider that it can be defined like this:

pow(x, p) = x * pow(x, p-1) if p > 0 else 1

The reason for that:

  • x2 is x * x.
  • x0 is 1.

So, with that in mind, let's consider some edge cases. We don't want to accept any values that are negative for this scenario, so the assert works okay. It'd be better to use an exception for this since not everyone is going to enable assertions with the -ea flag.

public long power(int x, int p) {
    if(p < 0) {
        throw new IllegalArgumentException("p is negative, not allowed");
    }
    if(p == 0) {
        return 1;
    } else {
        return x * power(x, p - 1);
    }
}
Community
  • 1
  • 1
Makoto
  • 104,088
  • 27
  • 192
  • 230
  • ***Phenomenal*** point. I hadn't realized that the method only allowed for one parameter, and yes, it turns into factorial. Let me get some things straightened out about that. – Makoto Jun 29 '15 at 01:54
1

I would make the method static (so you don't need an instance). Pass in the value you want to raise to a power and the exponent. Something like

public static long power(int n, int pow) {
    assert pow >= 0 : "Violation of: pow >= 0";
    if (pow == 0) { // <-- n^0 = 1
        return 1;
    } else if (pow == 1) { // <-- n^1 = n
        return n;
    }
    return n * power(n, pow - 1); // <-- recurse
}

As an instance method

Normally I would use Math.pow(double, double) but if you really need an in-place recursive implementation then you could do something like

class Power {
    public Power(int n) {
        this.n = n;
    }
    private int n;
    private long result = -1;

    public String toString() {
        return String.valueOf(result);
    }

    public long getResult() {
        return result;
    }

    public long power(int pow) {
        assert pow >= 0 : "Violation of: pow >= 0";
        if (pow == 0) { // <-- n^0 = 1
            return this.result = 1;
        } else if (pow == 1) { // <-- n^1 = n
            return this.result = this.n;
        }
        return this.result = this.n * this.power(pow - 1); // <-- recurse
    }

    public void setN(int n) {
        this.n = n;
    }

    public int getN() {
        return n;
    }
}
Elliott Frisch
  • 198,278
  • 20
  • 158
  • 249
  • I would LOVE to do it this way, but we have to keep the method as is in the assignment. I think the whole point is he is trying to get us to utilize instance methods with "this" - and then calling that stored value later. – Tori Jun 29 '15 at 02:03
0

I guess you are looking for this.

class Ideone  
{   
  public static void main (String[] args) throws java.lang.Exception  
 {

    Test t = new Test(2);
    System.out.println(t.power(5));
 }
}


class Test
{
int n;
Test(int n)
{
    this.n = n;
}
public int power(int p) {
 int x = 0;

 if (p == 0) {
    return 1;
 }
 if (p == 1) {
     return this.n;
 }
 if (p % 2 == 0) {
    x = this.power(p / 2);
    return x * x;
 } 
 else {
    return this.n * this.power(p - 1);     
     }      
}}

You can check this out at https://ideone.com/0ghIVe .

Shobhit_Geek
  • 591
  • 9
  • 22
  • I have to return it as void though, what way would you suggest this. I wish I could return an integer value. – Tori Jun 29 '15 at 02:20
  • @Tori: If you want to implement this using recursion, you have to use some return type.You can't do it using void as return type.Are you clear with the requirements? – Shobhit_Geek Jun 29 '15 at 02:28