Computer Science 210
Data Structures

Fall 2016, Siena College

Home     Syllabus     Schedule     Examples     Style Guide

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.
 *
 * Jim Teresco, The College of Saint Rose, CSC 252, Fall 2013
 * Updated for CSIS 210, Siena College, Fall 2016
 *
 * $Id: Powers.java 2230 2013-10-27 02:26:10Z terescoj $
 */

public class Powers {

    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 using a good old fashioned loop
    public static int loopPower(int base, int exponent) {
        
        int answer = 1;
        for (int i=0; i<exponent; i++) {
            answer *= base;
        }
        return answer;
    }
    
    // the straightforward recursive approach
    public static int recPower(int base, int exponent) {
        
        // our base case is exponent == 0
        if (exponent == 0) {
            return 1;
        }
        
        // otherwise, we have to do some work, b^n = b * b^{n-1}
        return base * recPower(base, exponent -1);
    }
    
    // a more efficient recursive approach, based on the idea
    // that we can compute a power b^{2n} as (b*b)^n
    public static int fastRecPower(int base, int exponent) {
        
        // base case is again exponent == 0
        if (exponent == 0) {
            return 1;
        }
        
        // now, see if the exponent is even or odd
        if (exponent % 2 == 1) {
            // it's odd, so use straightforward recursion to get
            // down to an even case
            return base * fastRecPower(base, exponent - 1);
        }
        
        // if we got here, it's even, so we can do better
        return fastRecPower(base * base, exponent / 2);
    }
}