Computer Science 210
Data Structures

Fall 2019, Siena College

Powers BlueJ Project

Click here to download a BlueJ project for Powers.


Powers Source Code

The Java source code for Powers is below. Click on a file name to download it.


Powers.java

import java.util.Scanner;

/**
 * Example Powers: examples of recursive methods to compute
 * powers of a number.
 *
 * @author Jim Teresco, The College of Saint Rose, CSC 252, Fall 2013
 * Updated for CSIS 210, Siena College, Fall 2016, Fall 2018
 * @version Fall 2019
 *
 */

public class Powers {

    /**
       main method to test our methods that compute powers.

       @param args not used.
    */
    public static void main(String args[]) {

        // read in the base and exponent from a Scanner
        Scanner s = new Scanner(System.in);
        System.out.println("Let's compute the value of some integer raised to a power.");
        System.out.print("First, enter the base: ");
        int base = s.nextInt();
        int exponent = 0;
        do {
            System.out.print("Next, enter the exponent (>=0): ");
            exponent = s.nextInt();
            if (exponent < 0) {
                System.out.println("Negative exponents are not allowed");
            }
        } while (exponent < 0);
        
        // now we compute in three different ways, using the methods below.
        
        System.out.println("" + base + "^" + exponent + ", computed three ways:");
        System.out.println("Method using a loop: " + loopPower(base, exponent));
        System.out.println("Method using straightforward recursion: " + recPower(base, exponent));
        System.out.println("Method using smarter recursion: " + fastRecPower(base, exponent));
    }

    /**
       Compute the power a^n using a good old fashioned loop.

       @param a the base for the power computation
       @param n the exponent for the power computation
       @return a^n
    */
    public static int loopPower(int a, int n) {
        
        int answer = 1;
        for (int i = 0; i < n; i++) {
            answer *= a;
        }
        return answer;
    }
    
    /**
       Compute the power a^n using a straightforward recursive approach

       @param a the base for the power computation
       @param n the exponent for the power computation
       @return a^n
    */
    public static int recPower(int a, int n) {
        
        // our base case is n == 0
        if (n == 0) {
            return 1;
        }
        
        // otherwise, we have to do some work, a^n = a * a^{n-1}
        return a * recPower(a, n -1);
    }
    
    /**
       Compute the power a^n using a a more efficient recursive
       approach, based on the idea that we can compute a power a^{2n}
       as (a*a)^n

       @param a the base for the power computation
       @param n the exponent for the power computation
       @return a^n
    */
    public static int fastRecPower(int a, int n) {
        
        // base case is again n == 0
        if (n == 0) {
            return 1;
        }
        
        // now, see if n is even or odd
        if (n % 2 == 1) {
            // it's odd, so use straightforward recursion to get
            // down to an even case
            return a * fastRecPower(a, n - 1);
        }
        
        // if we got here, it's even, so we can do better
        return fastRecPower(a * a, n / 2);
    }
}