14: Recursion and Other Topics

What We Will Cover

Continuations

Questions on What's Due Next?

Questions from last class?

^ top

14.1: Other Topics

Objectives

At the end of the lesson the student will be able to:

  • Use implementations of the Toolkit class
  • Play sounds in a Swing application

^ top

14.1.1: About Toolkits

  • The Toolkit class provides some methods that query the operating system directly
  • Look below to see some of the more commonly used methods
  • To get a Toolkit object, you use the getDefaultToolkit() method of the Toolkit class
    • Toolkit tk = Toolkit.getDefaultToolkit();
  • This object then allows you to use Toolkit methods

Some Commonly Used Methods of the Toolkit Class

Method Description
beep() Emits an audio beep.
getDefaultToolkit() A static method that returns the default toolkit for the system.
getScreenSize() Returns the screen resolution of the current system as a Dimension object.

For Example

  • The number of pixels on a screen varies from one computer to the next
  • To determine the number of pixels on a screen, you can use a Toolkit object
  • The getScreenSize() method returns a Dimension object containing the size
  • From the Dimension object you can get the height and width
  • Using the height and width, you can center the location of a frame
import java.awt.*;
import java.awt.event.*;
import javax.swing.*;

public class Beeper extends JFrame
        implements ActionListener{
    public final static int WIDTH = 200, HEIGHT = 125;

    private JButton playButton;

    public Beeper() {
        super("Beeper");
        setDefaultCloseOperation(EXIT_ON_CLOSE);

        playButton = new JButton("Play beep");
        playButton.addActionListener(this);

        Container contentPane = getContentPane();
        contentPane.add(playButton);

        Toolkit tk = Toolkit.getDefaultToolkit();
        Dimension d = tk.getScreenSize();
        setBounds((d.width - WIDTH) / 2,
                  (d.height - HEIGHT) / 2,
                  WIDTH, HEIGHT);
        setVisible(true);
    }

    public void actionPerformed(ActionEvent ae) {
        Toolkit tk = Toolkit.getDefaultToolkit();
        tk.beep();
    }

    public static void main(String[] args) {
        new Beeper();
    }
}

^ top

14.1.2: Playing Sounds

  • Sometimes you want an application to play a sound
  • The Applet class provides a simple method to play recorded sound files
  • You can use this method in either applets or applications
  • Java supports many sound files including: AU, AIFF, MIDI and WAV
  • To play a sound file, you use code like this:
    • AudioClip audioClip = Applet.newAudioClip(urlObject);
audioClip.play();

Applet Method Used to Instantiate an AudioClip

Method Description
Applet.getAudioClip(urlObject) Static method that returns an AudioClip that you can use to play sounds.

Three AudioClip Methods for Controlling Sounds

Method Description
loop() Starts playing this audio clip in a loop.
play() Starts playing this audio clip one time.
stop() Stops playing this audio clip.

For Example

  • To run this example, you will need audio files
  • You can download sample sound files at: a1freesoundeffects.com
import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.io.*;
import java.net.*;
import javax.swing.*;

public class SoundDemo extends JFrame
        implements ActionListener{
    public final static int X_LOC = 100, Y_LOC = 100;

    private JButton loopButton;
    private JButton playButton;
    private JButton stopButton;
    private JTextField nameField;
    private AudioClip audioClip;

    public SoundDemo() {
        super("Sound Application");
        setDefaultCloseOperation(EXIT_ON_CLOSE);

        JLabel prompt = new JLabel("File name:");
        nameField = new JTextField(10);
        JPanel panel = new JPanel();
        panel.add(prompt);
        panel.add(nameField);

        loopButton = new JButton("Loop");
        playButton = new JButton("Play");
        stopButton = new JButton("Stop");
        JPanel buttonPanel = new JPanel();
        buttonPanel.add(playButton);
        buttonPanel.add(loopButton);
        buttonPanel.add(stopButton);

        Container contentPane = getContentPane();
        contentPane.add(panel, BorderLayout.NORTH);
        contentPane.add(buttonPanel);

        loopButton.addActionListener(this);
        playButton.addActionListener(this);
        stopButton.addActionListener(this);
        nameField.addActionListener(this);

        setLocation(X_LOC, Y_LOC);
        pack();
        show();
    }

    public void actionPerformed(ActionEvent ae) {
        Object source = ae.getSource();
        if (source == playButton || source == nameField) {
            play();
        } else if (source == loopButton) {
            loop();
        } else if (source == stopButton) {
            stop();
        }
        nameField.requestFocus();
    }

    public URL getFileURL() {
        File f = new File(nameField.getText());
        URL fileUrl = null;
        try {
            fileUrl = new URL("file:" + f.getPath());
        } catch(IOException ioe) {
            System.out.println(ioe.toString());
            System.exit(1);
        }
        return fileUrl;
    }

    public void play() {
        stop();
        URL soundURL = getFileURL();
        System.out.println("Now playing: " + soundURL);
        audioClip = Applet.newAudioClip(soundURL);
        audioClip.play();
    }

    public void loop() {
        stop();
        URL soundURL = getFileURL();
        System.out.println("Now looping: " + soundURL);
        audioClip = Applet.newAudioClip(soundURL);
        audioClip.loop();
    }

    public void stop() {
        if (audioClip != null) {
            System.out.println("Stopped playing");
            audioClip.stop();
            audioClip = null;
        }
    }

    public static void main(String[] args) {
        new SoundDemo();
    }
}
  • The SoundDemo() constructor creates the GUI
  • actionPerformed() decides which button was and calls the associated method
  • Method getFileURL() uses the nameField to construct a URL object
  • Method play() starts an AudioClip playing
  • Method loop() starts an AudioClip looping
  • Method stop() halts and destroys the current AudioClip object

More Information

^ top

14.1.3: Running Java as a Windows Executable

  • Windows users are used to double-clicking an icon to launch an application
  • Java does not support directly this type of action
  • However, you can use the Marner Java Launcher to achieve this effect
  • The Marner Java Launcher consists of two files:
    • launch.exe
    • launcher.cfg
  • launch.exe is a Windows executable that launches a Java application
  • launcher.cfg is a text file that tells launch.exe what to run

A Simple Example Using the Marner Java Launcher

  1. Install all your files into one directory including
    • launch.exe
    • launcher.cfg
    • Your .class files
  2. Rename the launch.exe file to any name you like
    3. HelloButton.exe
  3. Edit the launcher.cfg file like the one shown below

Example Configuration File: HelloButton.cfg

.
javaw.exe
HelloButton
  1. First line: use the current directory (.) for running or specify a path to another directory
  2. Second line: the java executable file (java.exe or javaw.exe) to run. If the JDK bin directory is not in the path, you should specify an exact path.
    3. C:\j2sdk1.4.2\bin\javaw.exe
  3. Third line: parameters to java.exe (or javaw.exe) such as your .class file that contains the main() method.
  4. Optionally, package the files using ZIP or JAR

Using java.exe vs. javaw.exe

  • You can use either java.exe or javaw.exe to run a Java application
  • java.exe runs with a console window
  • javaw.exe runs without a console window

Example Application: HelloButton

import javax.swing.*;
import java.awt.event.*;

public class HelloButton extends JFrame
        implements ActionListener {

    public static void main(String[] args) {
        HelloButton hb = new HelloButton();
    }

    public HelloButton() {
        super("Hello Button Application");
        JButton exitButton = new JButton("Hello");
        getContentPane().add(exitButton);
        exitButton.addActionListener(this);
        setSize(300, 150);
        setVisible(true);
    }

    public void actionPerformed(ActionEvent e) {
        System.out.println("Goodbye!");
        System.exit(0);
    }
}

More Information

^ top

Exercise 14.1

  1. Run the SoundDemo application shown below.
  2. Setup the Marner Java Launcher to run the application.
import java.applet.*;
import java.awt.*;
import java.awt.event.*;
import java.io.*;
import java.net.*;
import javax.swing.*;

public class SoundDemo extends JFrame
        implements ActionListener{
    public final static int X_LOC = 100, Y_LOC = 100;

    private JButton loopButton;
    private JButton playButton;
    private JButton stopButton;
    private JTextField nameField;
    private AudioClip audioClip;

    public SoundDemo() {
        super("Sound Application");
        setDefaultCloseOperation(EXIT_ON_CLOSE);

        JLabel prompt = new JLabel("File name:");
        nameField = new JTextField(10);
        JPanel panel = new JPanel();
        panel.add(prompt);
        panel.add(nameField);

        loopButton = new JButton("Loop");
        playButton = new JButton("Play");
        stopButton = new JButton("Stop");
        JPanel buttonPanel = new JPanel();
        buttonPanel.add(playButton);
        buttonPanel.add(loopButton);
        buttonPanel.add(stopButton);

        Container contentPane = getContentPane();
        contentPane.add(panel, BorderLayout.NORTH);
        contentPane.add(buttonPanel);

        loopButton.addActionListener(this);
        playButton.addActionListener(this);
        stopButton.addActionListener(this);
        nameField.addActionListener(this);

        setLocation(X_LOC, Y_LOC);
        pack();
        show();
    }

    public void actionPerformed(ActionEvent ae) {
        Object source = ae.getSource();
        if (source == playButton || source == nameField) {
            play();
        } else if (source == loopButton) {
            loop();
        } else if (source == stopButton) {
            stop();
        }
        nameField.requestFocus();
    }

    public URL getFileURL() {
        File f = new File(nameField.getText());
        URL fileUrl = null;
        try {
            fileUrl = new URL("file:" + f.getPath());
        } catch(IOException ioe) {
            System.out.println(ioe.toString());
            System.exit(1);
        }
        return fileUrl;
    }

    public void play() {
        stop();
        URL soundURL = getFileURL();
        System.out.println("Now playing: " + soundURL);
        audioClip = Applet.newAudioClip(soundURL);
        audioClip.play();
    }

    public void loop() {
        stop();
        URL soundURL = getFileURL();
        System.out.println("Now looping: " + soundURL);
        audioClip = Applet.newAudioClip(soundURL);
        audioClip.loop();
    }

    public void stop() {
        if (audioClip != null) {
            System.out.println("Stopped playing");
            audioClip.stop();
            audioClip = null;
        }
    }

    public static void main(String[] args) {
        new SoundDemo();
    }
}

^ top

14.2: Introduction to Recursion

Objectives

At the end of the lesson the student will be able to:

  • Design recursive algorithms
  • Code recursive methods
  • Trace the processing steps of recursive methods

"To understand recursion, one must first understand recursion."
-- Unknown

^ top

14.2.1: About Recursion

Recursion: when an algorithm is defined in terms of itself.

  • Recursion is a natural approach to some problems
  • It allows us to break down a problem into one or more subproblems similar in form to the original problem
    • Sounds circular, but in practice is not
  • Recursion divides the problem into two parts:
    • Recursive step
    • Base case
  • The recursive step solves part of the problem
  • Then it calls the method again and passes it the smaller problem
  • Eventually the smaller problem becomes easy enough to just solve
  • The easy-to-solve problem is known as the base case

For Example: Many Hands Make Light Work

  • What if you were asked to do some task like washing the dishes?
  • You look at the pile of dishes and realize you have better things to do
  • So you wash one dish and then ask someone else to wash the dishes
    • Then you leave as soon as possible
  • The next person notices your actions and decides to do the same
  • They wash one set of dishes and then ask someone else to wash the dishes
  • This sequence repeats until all the dishes are washed
  • Writing this as an algorithm, we have:

Algorithm For Washing Dishes

  • If the sink is empty, do nothing
  • Else:
    • Wash one dish
    • Ask someone else to wash the dishes

Recursive Elements

  • Notice the recursive nature of the algorithm
  • The "else" clause contains a reference to itself
    • To do the dishes, we ask someone else to do the dishes
  • To make sure this algorithm is not an endless passing of the buck, each person does some work
  • This makes the job passed to the next person smaller
  • When all the dishes are done, the chain of asking someone else to do the dishes is broken

^ top

14.2.2: Implementing Recursive Methods

  • Recursion is an easy and powerful way of tackling many difficult computing problems
  • You implement recursion using methods that call themselves
  • Like a loop, a recursive method must have some way to end
  • Usually the base case is written first and the recursive step second

Recursive Method Structure

returnType recursiveMethod(parameters) {
    If (stopping condition) { // base case
        // Problem is very easy
        // so solve it and return
    } else { // recursive step
        // Solve part of the problem
        // leaving a smaller problem
        recursiveMethod(arguments);
    }
}

For Example

import javax.swing.JOptionPane;

public class RecDishes {
    public static void main(String[] args) {
        String msg = "How many dishes to wash?";
        String input = JOptionPane.showInputDialog(msg);
        int count = Integer.parseInt(input);
        wash(count);
        System.exit(0);
    }

    static void wash(int count) {
        if (count == 0) {
            System.out.println("Done washing dishes");
            return;
        } else {
            System.out.print("Washing one dish; ");
            count = count - 1;
            System.out.println("number reamining: "
                + count);
            wash(count);
        }
    }
}

^ top

14.2.3: Developing a Recursive Algorithm

  • To develop a recursive algorithm, we must find a way to do the following:
    • Use a solution to a smaller or easier version of a problem to arrive at the solution itself
    • Know when the problem is small enough to solve directly
  • As another example of recursion, let us look at exponentiation
  • We will limit ourselves to positive integers
  • The notation for exponentiation is:

    • xy

  • A method for exponentiation might start like:
    • int power(int x, int y)
  • The definition of exponentiation is:

    • xy = 1 * x * x * x ... (y times)

Developing the Recursive Algorithm

  • We start developing the algorithm by working through the process by hand
  • It seems like a lot of work, and so we get someone else to do most of the work
  • If we could get someone else to calculate xy - 1, we could just multiply by y

    • xy = x * xy - 1

  • This process could repeat until we are done
  • How do we know when we are done?

Recursive Algorithm For Exponentiation

  • If y is 0, we are done and the result is x0, which is 1
  • Else (while y ≥ 1):
    • Ask someone else to compute xy - 1
    • We multiply the result of xy - 1 times x

^ top

14.2.4: Coding the Recursive Algorithm

  • Implementing a recursive algorithm is usually straightforward

Example Code

import javax.swing.JOptionPane;

public class RecPower {
    public static void main(String[] args) {
        String msg = "Enter an integer value for x";
        String input = JOptionPane.showInputDialog(msg);
        int x = Integer.parseInt(input);
        msg = "Enter an integer value for y";
        input = JOptionPane.showInputDialog(msg);
        int y = Integer.parseInt(input);
        System.out.println(power(x, y));
        System.exit(0);
    }

    static int power(int x, int y) {
        if (y == 0) {
            return 1;
        } else {
            int result = power(x, y - 1);
            return x * result;
        }
    }
}

The Recursive Call

  • Note how the power() method calls itself
    • static int power(int x, int y) {
    ...
        int result = power(x, y - 1);
    ...
}
  • Calling a method from within that method is a recursive call
  • The arguments to the recursive call must define a task that is smaller or easier than the task given to the caller
  • In this case, the caller must calculate xy
  • But the recursive call is an easier task: xy - 1

Termination: I Won't be Back

  • The power() method has a conditional return that does not involve a recursive call:
    • static int power(int x, int y) {
    if (y == 0) {
        return 1;
    ...
    }
}
  • The termination step is essential to any recursive procedure
  • It checks to see if the task can be carried out without using recursion
  • If so, it terminates the recursion by preventing any further recursive calls
  • Note that the terminating condition must be checked before a recursive call
  • Otherwise, the recursive call would go on indefinitely
    • The terminating condition would never be reached

^ top

14.2.5: Tracing the Execution

  • How does the recursive method actually work?
  • We can trace the power(2, 3) called from main()
    • main() calls power(2, 3)
    power(2, 3) calls power(2, 2)
        power(2, 2) calls power(2, 1)
            power(2, 1) calls power(2, 0)
                power(2, 0) returns 1 (base case)
            power(2, 1) returns 2
        power(2, 2) returns 4
    power(2, 3) returns 8
power(2, 3) returns 8 to main()
  • Note that the first half makes successive method calls
    • Until the base case is reached
  • Second half returns the values of the recursive case

Instrumenting the Code

import javax.swing.JOptionPane;

public class RecPower2 {
    public static void main(String[] args) {
        String msg = "Enter an integer value for x";
        String input = JOptionPane.showInputDialog(msg);
        int x = Integer.parseInt(input);
        msg = "Enter an integer value for y";
        input = JOptionPane.showInputDialog(msg);
        int y = Integer.parseInt(input);

        System.out.println("main() calls power(" + x
            + ", " + y + ")");
        int result = power(x, y);
        System.out.println("power(" + x + ", " + y
            + ") returns " + result + " to main()");

        System.exit(0);
    }

    static int power(int x, int y) {
        if (y == 0) {
            System.out.println("power(" + x
                 + ", 0) returns 1 (base case)");
            return 1;
        } else {
            System.out.println("power(" + x +", " + y
                 + ") " + "calls power(" + x + ", "
                 + (y - 1) +")");
            int result = power(x, y - 1);
            System.out.println("power(" + x + ", " + y
                 + ") returns " + (x * result));
            return x * result;
        }
    }
}

^ top

14.2.6: Summary

  • Recursion is when an algorithm is defined in terms of itself
  • Allows us to define subproblems in similar form to the original
  • Recursion always has two parts:
    • Base case
    • A problem that is closer to the solution
  • Eventually, the base case is always called
  • Without the base case, you would have infinite recursion

More Information

^ top

Exercise 14.2

  1. Design a recursive algorithm for summing the values between 1 and n, where n is any positive integer.

    2. Examples of summing:

    sum(1) = 1
sum(2) = 2 + 1 = 3
sum(3) = 3 + 2 + 1 = 6
sum(4) = 4 + 3 + 2 + 1 = 10
  2. Write the recursive form of the algorithm using notation like the following:

    3. sum(1) = ??
    sum(n) = ?? for any ??

  3. Write the code to implement the recursive algorithm, using the following code to get started.
import javax.swing.JOptionPane;

public class RecExer {
    public static void main(String[] args) {
        String msg = "Enter the largest number: ";
        String input = JOptionPane.showInputDialog(msg);
        int number = Integer.parseInt(input);

        System.out.println(sum(number));

        System.exit(0);
    }

    static int sum(int number) {
        // code recursive algorithm here
        return 0; // change the return value
    }
}

^ top

Wrap Up

    Reminders

    Due Next Class: Sampler Project (12/6/04)

  • When class is over, please shut down your computer
  • There is no need to turn in this weeks exercises

^ top

Home | WebCT | Announcements | Schedule | Expectations | Course info
Help | FAQ's | HowTo's | Links

Last Updated: December 01 2004 @19:02:35