Computer Science 210
Data Structures

Fall 2018, 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, Fall 2018
 *
 */

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 a, int n) {
        
        int answer = 1;
        for (int i = 0; i < n; i++) {
            answer *= a;
        }
        return answer;
    }
    
    // the straightforward recursive approach
    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);
    }
    
    // a more efficient recursive approach, based on the idea
    // that we can compute a power a^{2n} as (a*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);
    }
}