14: Applets and Recursion

What We Will Cover Announcements Please silence all cell phones and pagers Sit at a computer station, start your computer and login When class is over, please shut down your computer. Remember that any data or program files are lost. Continuations 14.1: Applets and the Web 14.1.1: The Internet and the Web 14.1.2: Web Technology 14.1.3: Introduction to Applets 14.1.4: Applet Deployment Issues 14.1.5: Applet Security Issues 14.1.6: Applet Construction 14.1.7: Sample Applet Exercise 14.1 14.2: Swing Applets 14.2.1: Developing Swing Applets 14.2.2: Creating an HTML Page for Applets 14.2.3: Running the Applet Viewer 14.2.4: Using the Java Plug-in HTML Converter 14.2.5: Testing and Debugging a Swing Applet 14.2.6: Executing as Applets or Applications Exercise 14.2 14.3: Introduction to Recursion 14.3.1: About Recursion 14.3.2: Implementing Recursive Methods 14.3.3: Developing a Recursive Algorithm 14.3.4: Coding the Recursive Algorithm 14.3.5: Tracing the Execution 14.3.6: Summary Exercise 14.3 Wrap Up Due Next: Sampler Project (12/5/05) Continuations Questions on What's Due Next? Sampler Project (12/5/05) Questions from last class? ^ top 14.1: Applets and the Web Objectives At the end of the lesson the student will be able to: Discuss the technologies used on the Web Describe the uses and limitations of applets List the four important applet methods called by the browser ^ top 14.1.1: The Internet and the Web What is the Internet? Internet is a set of networks connected together with routers Networks move data from one computer to another Router are computers that move the data from one network to another What is the World-Wide Web? The Web is all about delivering hypertext documents over the Internet Hypertext documents are written using Hypertext Markup Language (HTML) Key feature of HTML is the hypertext link Hypertext links connect one document to another Brief History of the Internet 1969: Internet started by US DOD with 4 computers -- called ARPANET 1983: Internet (1000 computers) split into two parts -- military and University 1987: High-speed backbone added to solve performance issues (10K computers) 1989: World-Wide Web and HTML invented by Tim Berners-Lee at CERN 1992-3: US Government decides to commercialize Internet 1993: first graphical browser invented by Marc Andreessen While a student at the University of Illinois ^ top 14.1.2: Web Technology World-Wide Web Architecture Web has four major components: Web client (e.g. browser): requester of documents and services Web server: provider of services e.g. Web documents Internet: very large network to move the data Files: text, images, sound, video, etc. Browser uses Hypertext Markup Language (HTML) to format a page Web Browser Web browser is a program that runs on a computer Allows a person to retrieve and display files in various formats For example: Display a text file in HTML format Display picture files that use Graphics Interchange Format (GIF) format Play a sound file in Windows Waveform (WAV) format HTML HTML files are a mixture of text to display and HTML tags Tags are coded commands that tell the browser how to format the text For example, HTML tags could define text size or color For instance, the following HTML tag changes the text color of red dog <font color="red">red dog</font> HTML tags are shown in bold above Note that tags begin with a less-than sign and end with a greater-than sign Web Server Web servers are programs that provide web documents Often run on dedicated computers, also known as a web server Web server software runs constantly in the background waiting for requests When a request is received, locates and sends the requested document Client/server Interaction User enters query (URL) into client (browser) Client connects to server and sends query Server analyzes query, computes results and respond with information Client receives results and displays them to user ^ top 14.1.3: Introduction to Applets Static Documents At first, only static documents were available on the Web Soon became apparent that more technologies were needed Needed to display dynamic content in browsers Graphics Animation Sound Enter Applets In 1995, Sun Microsystems released Applets Applet: a Java program that runs in a browser People were impressed with applets in Web pages Spinning molecules Sorting demos Both Netscape and Microsoft agreed to support Java applets Advantages of Applets Applets have several advantages when run in a Web browser Applets work on the client and do not use server resources Applets run in most browsers on most operating systems Can use the full power of the Java programming language Applets are secure, running with tight "sandbox" controls Applets can communicate with the web server Demonstration Applets Sun has many demonstration applets Can study and mimic source code to learn new features All programmers can learn by reading the source code of existing programs ^ top 14.1.4: Applet Deployment Issues When Java 1.0 was released, both IE and Netscape included a JVM Allowed any Web page to run applets Unfortunately, neither browser kept up with newer versions of Java Because of this, while most browsers support Java 1.0, only a few support Java 1.1 Thus, most do not support Swing Nor do most of them support recent Java features To allow IE and Netscape to run newer versions of Java, Sun provides a Java Plug-in If the Java Plug-in is installed, the browser can run Swing applets Of course, many Web users have not installed the Java Plug-in People need a strong incentive to bother installing any plug-in Note that the Java Plug-in was automatically installed when you installed Java for this course Two Solutions One solution is to use Swing applets and install the Java Plug-in On every client machine Another solution is to write applets using the older AWT version of Java Swing Applets Pros Swing applets use Swing components More features Common look and feel Can use all of the latest Java language features Cons Developer must run an HTML Converter program Must install the Java Plug-in on client machines AWT Applets Pros Developer does not need to run an HTML Converter program Do not need to install the Java Plug-in on client machines Cons Cannot use Swing components and event model Must restrict Java features to earliest Java releases (e.g. version 1.0) Guidelines and Advice Use Swing on Intranets and places where you can be sure the Java Plug-in is installed Use Swing if people have a strong enough interest in your program to install the Java Plug-in Otherwise, use AWT ^ top 14.1.5: Applet Security Issues Sun wanted to make sure applets could not damage a client system Built strong security restrictions into applets to limit what they can do Applet Restrictions Cannot read, write or delete files on the client system Cannot run programs on the client system Can only access a few properties of the client system: Java version Name of operating system Version of operating system Characters used to separate directories, paths and lines Cannot make network connections to servers Other than the one the applet was loaded from Some Applet Capabilities Display GUI components and graphics Send keystrokes and mouse clicks to the applet's server Make network connections to the applet's server Call public methods of other applets on the same Web page Bypassing Security Can create signed applets to overcome security restrictions Indicates applet comes from a trusted source User must agree to use a signed applet Further information: Lesson: Quick Tour of Controlling Applets ^ top 14.1.6: Applet Construction Inheritance Chain Following is the inheritance chain for applets Use methods of Component and Container with both types of applets Extend Applet class to create AWT applets Extend JApplet class to create Swing applets java.awt.Component | +--java.awt.Container | +--java.awt.Panel | +--java.applet.Applet | +--javax.swing.JApplet Applet Lifecycle Methods Four methods are used to control the execution of an applet All four are methods of the Applet class Browser automatically calls these methods You never need to call them Normally override the init() method in your applet code May also override the other methods The Four Lifecycle Methods of Applet Method Description public void init() Called when the browser loads the applet. public void start() Called after the init method and every time the user moves to the web page with the applet. public void stop() Called before the destroy method and every time the user leaves the web page with the applet. public void destroy() Called when the user exits the browser. ^ top 14.1.7: Sample Applet You can easily create an applet like the following Code for this applet is: 1 2 3 4 5 6 7 8 import javax.swing.*; public class HelloApplet extends JApplet { public void init() { JLabel label = new JLabel("Hello, world!"); getContentPane().add(label); } } Looking at each piece of code: import javax.swing.*; JApplet is part of the Swing class-library Use an import statement to access the library public class HelloApplet extends JApplet { Use and override methods defined in JApplet Using inheritance, we can take advantage of the work someone else did public void init() { Applets start in an init() method, unlike applications which start in main() By default, init() has an empty body We override (redefine) init() in our HelloApplet class JLabel label = new JLabel("Hello, Applet World!"); For our simple Applet we only need to display text We use a label class named JLabel for that purpose One of the constructors for JLabel takes our literal string parameter: "Hello, Applet World!" getContentPane().add(label); We add our JLabel component to the JApplet container Note that we use getContentPane() to so we are compatible with Java before JDK 1.5 JApplet can now display the text we entered ^ top Exercise 14.1 In this exercise we examine applet capabilities and review a few applet concepts. Which demonstration applet impresses you the most? What type of applet is the following: AWT or Swing? How can you tell? import javax.swing.*; public class HelloApplet extends JApplet { public void init() { JLabel label = new JLabel("Hello, world!"); getContentPane().add(label); } } How does the init() method get called? ^ top 14.2: Swing Applets Objectives At the end of the lesson the student will be able to: Develop and test a Swing applet Code the HTML page for an applet View the applet in a browser and the Applet Viewer ^ top 14.2.1: Developing Swing Applets There are two ways to develop the code for Swing applets: Develop code for new applets from scratch Convert existing Swing applications to applets Developing Swing Applets Write or convert the code and compile the Swing applet Write the HTML page for the applet Test the applet with the Applet Viewer Use the HTML Converter program to convert the HTML for the applet Test the HTML page with a browser Converting Swing Applications to Applets Extend the JApplet class rather than the JFrame class Convert the constructor of the JFrame to the init() method of the applet Should not use a constructor because the full applet environment is not available until init() is called Some methods, like image loading methods, do not work until init() is called Remove any code that: Exits the frame Sets the title, size, position or visibility of the GUI You can see these steps in the following example Example Converting an Application to an Applet Rename LoginPane to LoginApplet Extend JApplet rather than JFrame: public class LoginApplet extends JApplet Remove the main() method Recode the constructor to an init() method: public void init() Remove the call to super() since it sets the title Delete the call to setDefaultCloseOperation(EXIT_ON_CLOSE) Remove the calls to setLocation(X_LOC, Y_LOC), pack() and setVisible(true) Original Application Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class LoginPane extends JFrame { public final static int X_LOC = 100, Y_LOC = 100; private JTextField login; private JPasswordField password; private JButton loginButton; public static void main(String[] args) { new LoginPane(); } public LoginPane() { super("Login Application"); setDefaultCloseOperation(EXIT_ON_CLOSE); JLabel loginLabel = new JLabel("User name:"); login = new JTextField(10); JPanel loginPanel = new JPanel(); loginPanel.add(loginLabel); loginPanel.add(login); JLabel pwdLabel = new JLabel("Password:"); password = new JPasswordField("asecret", 10); JPanel pwdPanel = new JPanel(); pwdPanel.add(pwdLabel); pwdPanel.add(password); loginButton = new JButton("Press to Login"); JPanel buttonPanel = new JPanel(); buttonPanel.add(loginButton); add(loginPanel, BorderLayout.NORTH); add(pwdPanel, BorderLayout.CENTER); add(buttonPanel, BorderLayout.SOUTH); LoginListener listener = new LoginListener(); login.addActionListener(listener); password.addActionListener(listener); loginButton.addActionListener(listener); setLocation(X_LOC, Y_LOC); pack(); setVisible(true); } private void showMessage() { String message = "Login: " + login.getText() + "\nPassword: " + new String(password.getPassword()); JOptionPane.showMessageDialog(null, message, "Login Message", JOptionPane.INFORMATION_MESSAGE); } class LoginListener implements ActionListener { public void actionPerformed(ActionEvent e) { if (e.getSource() == login) { password.requestFocus(); } else if (e.getSource() == password) { showMessage(); login.requestFocus(); } else if (e.getSource() == loginButton) { showMessage(); login.requestFocus(); } } } } Converted Applet Code 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class LoginApplet extends JApplet implements ActionListener { private JTextField login; private JPasswordField password; private JButton loginButton; public void init() { JLabel loginLabel = new JLabel("User name:"); login = new JTextField(10); JPanel loginPanel = new JPanel(); loginPanel.add(loginLabel); loginPanel.add(login); JLabel pwdLabel = new JLabel("Password:"); password = new JPasswordField("asecret", 10); JPanel pwdPanel = new JPanel(); pwdPanel.add(pwdLabel); pwdPanel.add(password); loginButton = new JButton("Press to Login"); Container contentPane = getContentPane(); contentPane.add(loginPanel, BorderLayout.NORTH); contentPane.add(pwdPanel, BorderLayout.CENTER); contentPane.add(loginButton, BorderLayout.SOUTH); login.addActionListener(this); password.addActionListener(this); loginButton.addActionListener(this); } public void actionPerformed(ActionEvent e) { if (e.getSource() == login) { password.requestFocus(); } else if (e.getSource() == password) { checkLogin(); login.requestFocus(); } else if (e.getSource() == loginButton) { checkLogin(); login.requestFocus(); } } public void checkLogin() { JOptionPane.showMessageDialog(null, "Login: " + login.getText() + "\nPassword: " + new String(password.getPassword()), "Login Message", JOptionPane.INFORMATION_MESSAGE); } } Actual Applet ^ top 14.2.2: Creating an HTML Page for Applets After you have applet code, you have to view it using a browser To view applets in a browser, you first need to write some HTML code About HTML Hypertext Markup Language (HTML) is the language used to create Web pages A web page is just a text file with HTML tags added Tags are embedded in the text to control page layout Tags consist of: "<": opening character of a tag A layout instruction such as html, body or font ">": closing character of a tag HTML tags are case insensitive: you can use either upper or lower case Note that World Wide Web Consortium (W3C) recommends lowercase tags You can use any text editor to view HTML including Notepad and TextPad Note that most tags come in pairs: opening tag and closing tag Also, you can nest tags, but always close inner tags before closing outer tags For Example Following is a basic HTML document that includes an applet tag One thing to note is you can view the source HTML of a web page 1 2 3 4 5 6 7 8 9 10 11 12 13 14 <html> <head> <title>Login Applet</title> </head> <body> <h1>Login Applet</h1> <applet code="LoginApplet.class" width=200 height=100> If you cannot see this applet, your browser may not be Java-enabled. </applet> </body> </html> See it Some HTML Tags Tag Description <html></html> Marks the start and end of an HTML page. <head></head> Marks the start and end of the section of a page that describes the entire document. <title></title> Defines the title of an HTML page that appears in the title bar of the browser. <body></body> Marks the start and end of the section that contains text, applets and other information to present. <h1></h1> Displays the enclosed text as a level-1 (large) header. <applet></applet> Defines an applet for display in a document. This tag is officially deprecated, but most browsers still support it. <embed></embed> Defines a plug-in application within the document. Netscape uses this tag to define Swing applets. <object></object> Defines an object within a document. IE uses this tag to define Swing applets. Some Attributes of the Applet Tag Attribute Description code Specifies the name of the class file to execute. codebase Specifies the pathname of the applet on the server. width Specifies the width of the applet in pixels. height Specifies the height of the applet in pixels. archive Specifies the archive file (such as a JAR file) that contains class files and other resources. Further Information The APPLET Tag ^ top 14.2.3: Running the Applet Viewer Applet Viewer is included in the SDK Lets you test an applet before running it in a browser Following is our LoginApplet displayed in the Applet Viewer Note that only the applet is displayed All other text is ignored Using the Command Prompt Open a console window or access the command prompt Change to the directory where the applet class file is located Type in the command appletviewer followed by the HTML file for the applet appletviewer LoginApplet.html ^ top 14.2.4: Using the Java Plug-in HTML Converter Different browsers run applets using different tags Embed tag for Netscape Object tag for IE You can set up HTML code so that both types of tags are supported Supporting both tags allows applets to run in more browsers Since coding the HTML is somewhat complex, Sun created a tool called the Java Plug-in HTML Converter You can find the tool in the bin subdirectory of your Java installation A converted page will work for most browsers including Mozilla, Netscape and IE Instructions for and Example of Using the HTML Converter For our example, we will convert the LoginApplet.html file shown below 1 2 3 4 5 6 7 8 9 10 11 12 13 14 <html> <head> <title>Login Applet</title> </head> <body> <h1>Login Applet</h1> <applet code="LoginApplet.class" width=200 height=100> If you cannot see this applet, your browser may not be Java-enabled. </applet> </body> </html> Save the HTML code to a convenient location like your Desktop (or Home) directory Locate the HtmlConverter.exe program and start the application. Located in the jdk/bin subdirectory of the Java installation Click on the Browse... button and find the HTML file to convert. Click on the Convert... button to convert the HTML file See the converted page and view the source. Note that you may have to adjust the width or height specified in the HTML because the applet viewer adds a border to the display area and a browser does not Also note that the Applet Viewer may not display correctly after the conversion More Information Java Plugin Guide Using the HTML Converter to Convert Applet Tags for Java Plug-in ^ top 14.2.5: Testing and Debugging a Swing Applet You need to test an applet in a browser to see if it works correctly However, the browser will not show exceptions or System.out.print() statements Sun provides the Java Console to address these issues Testing a Swing Applet Start your web browser and run the applet If it does not work correctly, start the Java Console You can view any exceptions thrown by the applet in the console window Also you can add System.out.println() statements to the code and view them in the console Displaying the Java Console How to display the Java Console depends both on how you installed it and your browser If it shows in the Windows task bar, double-click the Java Console icon From IE, select the Tools menu and select Sun Java Console From Netscape, select the Tools menu and of the Communicator menu From Mozilla, select the Tools, Web Development and Java Console Firefox requires that you install an extension to view the console I used Show Java Console to add a menu item to display the Java Console Further Information Debugging Support Java Plug-in Console Tracing and Logging ^ top 14.2.6: Executing as Applets or Applications Previously, we converted applications to applets However, you can configure an applet to run as either an applet or application This is possible because a JApplet is a Component You can add any Component to a JFrame We will convert the LoginApplet to run as either an applet or application Example to Convert: LoginApplet.java 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class LoginApplet extends JApplet { private JTextField login; private JPasswordField password; private JButton loginButton; public void init() { JLabel loginLabel = new JLabel("User name:"); login = new JTextField(10); JPanel LoginAppletl = new JPanel(); LoginAppletl.add(loginLabel); LoginAppletl.add(login); JLabel pwdLabel = new JLabel("Password:"); password = new JPasswordField("asecret", 10); JPanel pwdPanel = new JPanel(); pwdPanel.add(pwdLabel); pwdPanel.add(password); loginButton = new JButton("Press to Login"); JPanel buttonPanel = new JPanel(); buttonPanel.add(loginButton); add(LoginAppletl, BorderLayout.NORTH); add(pwdPanel, BorderLayout.CENTER); add(buttonPanel, BorderLayout.SOUTH); LoginListener listener = new LoginListener(); login.addActionListener(listener); password.addActionListener(listener); loginButton.addActionListener(listener); } private void showMessage() { String message = "Login: " + login.getText() + "\nPassword: " + new String(password.getPassword()); JOptionPane.showMessageDialog(this, message, "Login Message", JOptionPane.INFORMATION_MESSAGE); } class LoginListener implements ActionListener { public void actionPerformed(ActionEvent e) { if (e.getSource() == login) { password.requestFocus(); } else if (e.getSource() == password) { showMessage(); login.requestFocus(); } else if (e.getSource() == loginButton) { showMessage(); login.requestFocus(); } } } } Example Converting to Run as Either an Applet or Application Add a main method to the applet public static void main(String[] args) Within main(), instantiate a JFrame and set the title JFrame frame = new JFrame("Login Pane"); Set the desired behavior for when the frame closes frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); Create an instance of the applet LoginApp applet = new LoginApp(); Call the init() and start() methods of the applet applet.init(); applet.start(); Add the applet to the frame frame.add(applet); Arrange, size and display the frame frame.pack(); frame.setVisible(true); Example of Converted Applet 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class LoginApp extends JApplet { public static final int X_LOC = 100, Y_LOC = 100; private JTextField login; private JPasswordField password; private JButton loginButton; public static void main(String[] args) { JFrame frame = new JFrame("Login Pane"); frame.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); LoginApp applet = new LoginApp(); applet.init(); applet.start(); frame.add(applet); frame.pack(); frame.setLocation(X_LOC, Y_LOC); frame.setVisible(true); } public void init() { JLabel loginLabel = new JLabel("User name:"); login = new JTextField(10); JPanel LoginAppl = new JPanel(); LoginAppl.add(loginLabel); LoginAppl.add(login); JLabel pwdLabel = new JLabel("Password:"); password = new JPasswordField("asecret", 10); JPanel pwdPanel = new JPanel(); pwdPanel.add(pwdLabel); pwdPanel.add(password); loginButton = new JButton("Press to Login"); JPanel buttonPanel = new JPanel(); buttonPanel.add(loginButton); add(LoginAppl, BorderLayout.NORTH); add(pwdPanel, BorderLayout.CENTER); add(buttonPanel, BorderLayout.SOUTH); LoginListener listener = new LoginListener(); login.addActionListener(listener); password.addActionListener(listener); loginButton.addActionListener(listener); } private void showMessage() { String message = "Login: " + login.getText() + "\nPassword: " + new String(password.getPassword()); JOptionPane.showMessageDialog(this, message, "Login Message", JOptionPane.INFORMATION_MESSAGE); } class LoginListener implements ActionListener { public void actionPerformed(ActionEvent e) { if (e.getSource() == login) { password.requestFocus(); } else if (e.getSource() == password) { showMessage(); login.requestFocus(); } else if (e.getSource() == loginButton) { showMessage(); login.requestFocus(); } } } } Actual Applet ^ top Exercise 14.2 In this exercise we examine how to run an application as an applet. Specifications Convert the HelloFrame5 application, shown below, to run as an applet. As an optional step, convert it to run as either an application or an applet. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 import java.awt.*; import java.awt.event.*; import javax.swing.*; public class HelloFrame5 extends JFrame { public final static int X_LOC = 100, Y_LOC = 100, WIDTH = 300, HEIGHT = 150; private JButton helloButton; private JButton onOffButton; public static void main(String[] args) { new HelloFrame5(); } public HelloFrame5() { super("Hello Frame Application"); setDefaultCloseOperation(EXIT_ON_CLOSE); helloButton = new JButton("Hello"); helloButton.addActionListener(new HelloListener()); onOffButton = new JButton("On"); onOffButton.addActionListener(new OnOffListener()); JPanel panel = new JPanel(); panel.add(helloButton); panel.add(onOffButton); add(panel); setBounds(X_LOC, Y_LOC, WIDTH, HEIGHT); setVisible(true); } class HelloListener implements ActionListener { public void actionPerformed(ActionEvent ae) { JOptionPane.showMessageDialog( HelloFrame5.this, "Hey"); } } class OnOffListener implements ActionListener { public void actionPerformed(ActionEvent ae) { if (onOffButton.getText().equals("On")) { onOffButton.setText("Off"); } else { onOffButton.setText("On"); } } } } Check Yourself How can the code for a Swing application be converted to a Swing applet? How is an applet placed in an HTML page? What is the Applet Viewer? How can debugging information be displayed when a Swing applet is running? ^ top 14.3: 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.3.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.3.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); } } Implementation of Recursive Example 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 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.3.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.3.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.3.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.3.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 Recursion: from Wikipedia ^ top Exercise 14.3 In this exercise we look at several examples of recursion. You should be able to work out the solutions to the following problems. Recursive Problems What is wrong with the following recursive definition? For the definition of recursion, see recursion :) Write a method using recursion to print numbers from n to 0. Write a method using recursion to print numbers from 0 to n. (You only need to shift one line in the program of the previous problem.) Write a method using recursion to enter and display a string in reverse. Do not use arrays or additional strings. Write a method using recursion to enter and display a string in reverse and state whether the string contains any spaces. Do not use arrays or additional strings. Write a recursive method for summing the values between 1 and n, where n is any positive integer. Examples of summing: sum(1) = 1 sum(2) = 2 + 1 = 3 sum(3) = 3 + 2 + 1 = 6 sum(4) = 4 + 3 + 2 + 1 = 10 ^ top Wrap Up Reminders Due Next: Sampler Project (12/5/05) 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: November 30 2005 @13:41:49