Transcript ppt - AD Book Enterprises

8/2: Recursion
• About Scoping.java
• Recursion
• Program of the Day
Scoping.java pt.1
//Fig. 6.10: Scoping.java -- A scoping example
import java.awt.Container;
import javax.swing.*;
public class Scoping extends JApplet {
JTextArea outputArea;
int x = 1; //note: an instance variable
public void init ()
{
outputArea = new JTextArea();
Container c = getContentPane();
c.add ( outputArea );
}
Scoping.java pt.2
public void start ()
{
int x = 5; //note: a local variable with the same name.
outputArea.append ( "local x in start is " + x );
methodA();
methodB();
methodA();
methodB();
//methodA has automatic local x
//methodB uses instance variable x
//methodA reinitializes automatic local x
//instance variable x retains its value
outputArea.append ( "\n\nlocal x in start is " + x );
}
Scoping.java pt.3
public void methodA()
{
int x = 25; //initialized each time methodA is called.
outputArea.append( "\n\nlocal x in methodA is " + x +
" after entering methodA" );
++x;
outputArea.append( "\nlocal x in methodA is " + x +
" before exiting methodA" );
}
Scoping.java pt.4
public void methodB()
{
outputArea.append ( "\n\ninstance variable x is " + x +
" on entering methodB" );
x *= 10;
outputArea.append ( "\ninstance variable x is " + x +
" on exiting methodB" );
}
}
Recursion
•
•
•
•
Somewhat like iteration
A recursive method calls itself.
EX from math: factorial: n! = n * ( n - 1 ) !
EX: finding a name in phone book
– go to the middle of the phone book.
– if name is before that page, go to middle of front half
– if name is before that page, go to middle of front half
of front half
– if name is before that page, go to middle of front half
of front half of front half...
Example: countZeros.java pt. 1
//Counting zeros: a recursion example
import javax.swing.JOptionPane;
public class CountZeros {
public static void main ( String args [] )
{
int number, zeros;
number = Integer.parseInt ( JOptionPane.showInputDialog (
"Give me an integer. I'll count the zeros for you." ) );
zeros = count0s( number );
JOptionPane.showMessageDialog ( null , "The number " +
number + " has " + zeros + " zeros in it." );
System.exit ( 0 );
}
Example: countZeros.java pt. 2
public static int count0s ( int n )
{
if ( n == 0 )
return 1;
else if ( n < 10 )
return 0;
//called by the method above
//and not zero, mind you
else if ( n % 10 == 0 )
//remainder of n/10
return ( count0s ( n / 10 ) + 1 );
else
//n%10 is not = to zero
return ( count0s ( n / 10 ) );
}
}
Notes about Recursive Methods
• base case (or stopping case)
– last one to be evaluated
– must exist for recursion to end. Without it, the
recursion is endless (and the program won’t stop.)
– EX: factorial: n! = n * ( n - 1 ) !
– the base case would be 2 * 1
– factorials, by definition, stop at 1: 0! = 1, 1! = 1
Memory Issue: Recursive Methods
• Java stores all values generated along the way:
– Java calculating factorial of 6 :
6! = 6 * (6 - 1 )! = 720
= 5 * ( 5 - 1 )! = 120
= 4 * ( 4 - 1 )! = 24
= 3 * ( 3 - 1 )! = 6
= 2 * ( 2 - 1 )! = 2
=1
• Java stores these values in a stack.
Recursive vs. Iterative Methods
• Any recursive method can be rewritten as an
iterative method.
• Why use recursion, then?
– recursion may mimic the problem at hand better.
– iterative solutions may not be obvious.
Program of the day
• pg. 239 FibonacciTest.java
• After you get it to work, modify the program to
use an iterative approach rather than a recursive
approach.
• Don’t forget: Quiz #4 (last one!) Tomorrow.
guaranteed programs: scope & recursion.