Example - Power Function With Recursion

An integer taken to another integer power can be coded recursively. Suppose we want to find \(x^y\), where \(x\) and \(y\) are both integers. Here is one way to write the Java program:

public static double power(int x, int y){
   if (y == 0){
      return 1;
   }
   else if (y < 0){
      return 1.0 / power(x, -y);
   }
   else {
      return x * power(x, y - 1);
   }
}

Practice Questions

1. Identify the base case(s) in the power method.

2. Identify the recursive call(s) in the power method.

3. Explain how the recursive call(s) move(s) toward base case(s) in the power method.

4. Draw the execution stack frames to visualize power(25, 3).

5. Draw the execution stack frames to visualize power(3, -1).

6. Is the power method tail recursive? Why or why not?

7. Rewrite the power method to include a wrapper so that there is only one recursive call in the code. This will reduce the complexity by avoiding one comparison per recursive call at run-time.

To Solutions