Repeating an action over and over is called repetition. This Chapter introduces techniques and applications of repetition in programming. The Chapter is organized into three distinct parts:
After studying the Chapter, the reader should be able to identify when a programming problem should be solved by means of repetitive computation, apply the appropriate repetitive pattern, and write the pattern in Java.
Computers became popular partly because a computer program will unfailingly repeat a tedious task over and over. For example, perhaps you must know the decimal values of the fractions (reciprocals) 1/2, 1/3, 1/4, and so on, up to 1/20. A painful way of programming these calculations is manually repeating a division statement 19 times:
public static void main(String[] args)
{ System.out.println("1/2 = " + (1.0/2));
System.out.println("1/3 = " + (1.0/3));
System.out.println("1/4 = " + (1.0/4));
...
System.out.println("1/20 = " + (1.0/20));
}
The computer readily computes the reciprocals, but we
should find a simpler
way to request the computations than
the ``copy and paste'' coding technique above. A better solution
is built with
a control structure called
a while loop.
At the beginning of the previous section, we saw two algorithms for tightening a car's wheel and finding a television show. We can rewrite the two algorithms in ``while-loop style,'' where we begin the algorithm with the word, ``while,'' followed by a true-false test, followed by an action to perform as long as the test is true:
We can write while-loops in Java; the format is
while ( TEST ) { BODY }
where
TEST is a boolean-typed expression and BODY
is a sequence of (zero or more) statements.
With Java's while-loop, we can rewrite the method that prints the reciprocals from 1/2 to 1/20. The algorithm goes like this:
public static void main(String[] args)
{ int denominator = 2;
while ( denominator <= 20 )
{ System.out.println("1/" + denominator + " = " + (1.0 / denominator));
denominator = denominator + 1;
}
}
The while-loop prints
the fractional representations of
1/2, 1/3, ..., 1/20 and stops.
Here is a more precise explanation of how the while-loop, while ( TEST ) { BODY }, executes:
Here is the flowchart representation of a a while-loop---it is a graph with a cycle:
and indeed, this is the origin of the term, ``loop.''
Loops fall into two categories: definite iteration, where the number of the loop's iterations is known the moment the loop is started, and indefinite iteration, where it is not. Also, it is possible for a loop's iterations to be unbounded (that is, the loop never stops). We study all three behaviors in the examples in the sections that follow.
String s = "";
while ( s.length() != 5 )
{ s = s + 'a';
System.out.println(s);
}
(Recall that
the length operation returns the length of a string;
for example,
String s = "abcde"; int i = s.length();assigns 5 to i.)
int countdown = 10;
while ( countdown != 0 )
{ System.out.println(i);
countdown = countdown - 1;
}
int countdown = 5;
int countup = -1;
while ( countdown > countup )
{ countdown = countdown - 1;
System.out.println(countdown + " " + countup);
countup = countup + 1;
}
while ( false )
{ System.out.println("false"); }
String s = "";
while ( s.length() < 6 )
{ s = s + "a";
if ( (s.length() % 2) == 1 )
{ System.out.println(s); }
}
Say that we must construct a method that computes the average score of a student's exams. The method first asks the student to type the number of exams and then the method reads the exam scores, one by one, totals them, and computes the average score.
There is a numerical pattern to computing an average score; if the student has taken N exams, then the average score is calculated by this formula:
average = (exam1 + exam2 + ... + examN) / NThe ellipsis in the formula suggests that we should repeatedly sum the scores of the exams until all N scores are totalled; then we do the division. Here is an algorithm that uses several variables, along with a while-loop, to sum the exams:
int how_many = HOW MANY SCORES TO READ;
double total_points = 0.0;
int count = 0;
while ( count != how_many )
{ int score = READ INTEGER FROM THE USER;
total_points = total_points + score;
count = count + 1;
}
return (total_points / how_many);
The algorithm is presented as a Java method, computeAverage, in
Figure 1.
FIGURE 1: while-loop to compute average score=============================
import javax.swing.*;
/** computeAverage computes the average of test scores submitted by a user
* @param how_many - the quantity of test scores to read; must be nonnegative
* @return the average of the test scores */
public double computeAverage(int how_many)
{ double total_points = 0.0; // the total of all test scores
int count = 0; // the quantity of tests read so far
while ( count != how_many )
// at each iteration: total_points == exam_1 + exam_2 + ... + exam_count
{ // ask the user for the next exam score:
String input = JOptionPane.showInputDialog("Type next exam score:");
int score = new Integer(input).intValue();
// add it to the total:
total_points = total_points + score;
count = count + 1;
// print a summary of the progress:
System.out.println("count = " + count + "; total = " + total_points);
}
// at conclusion: total_points == exam_1 + exam_2 + ... + exam_how_many
return (total_points / how_many);
}
ENDFIGURE================================================================
At each iteration of the loop, the method generates a dialog to read
the next exam score, and a
println statement helps us see the loop's
progress. Say that the user wishes to average the scores,
8, 5, 6, and 7. The invocation,
System.out.println(computeAverage(4)), produces this trace information:
By reading the printed trace information, we see that at the beginning (and the end) of each iteration, the value in total_points indeed equals the sum of all the exam scores read so far, that is,
total_points == exam_1 + exam_2 + ... + exam_countThis crucial fact is called the loop's invariant property or invariant, for short. The invariant explains what the loop has accomplished with its iterations so far. Because of their value in helping us understand a loop's secrets, we will state invariant properties for the loops we study.
Because of the loop's invariant property, we know that when the loop stops with count equal to how_many, then it must be the case that total_points holds all the total points for all exams. From here, it is a small step to compute the average.
In the example, variables count and total_points play crucial roles in remembering the loop's progress---the former acts as the loop's counter, and the latter remembers a running total.
It is absolutely crucial to understand the details of loop execution, so we examine part of the execution trace of the example. Say that the method has been invoked as computeAverage(4); once variables count and total_points are initialized, we have the following configuration:
The loop's test evaluates to true, so execution moves into the body:
The user types 8 as the first exam score; the loop's body revises the variables' values:
At this point, the while-loop ``restarts''---the control marker, >, returns to the beginning of the loop, and the process repeats. Of course, the variables retain their updated values:
Again, the test is evaluated and the result is true, so the body of the loop is entered for yet another repetition, and the second score, 5, is read:
The loop repeats twice more, reading the last two scores, and we reach the configuration where count's cell holds 4:
The test evaluates to false, and the loop is abandoned:
This loop is an example of definite iteration, because once the loop is started, the number of iterations is completely decided; here, it is how_many iterations.
Definite iteration loops almost always use
For a loop counter, count, the pattern of definite iteration often looks like this:
int count = INITIAL VALUE;
while ( TEST ON count )
{ EXECUTE LOOP BODY;
INCREMENT count;
}
We have seen this pattern used twice already.
Occasionally, count is incremented at the beginning of the loop body:
int count = INITIAL VALUE;
while ( TEST ON count )
{ INCREMENT count;
EXECUTE LOOP BODY;
}
/** computeMaxScore reads a sequence test scores submitted by a user and * returns the highest score read * @param how_many - the quantity of test scores to read; must be nonnegative * @return the maximum test score */ public double computeMaxScore(int how_many)Add this method to class ExamStatistics and modify the main method you just wrote to invoke computeMaxScore instead.
/** computeBetterAverage computes the average of test scores submitted * by a user _but discards_ the lowest score in the computation. * @param how_many - the quantity of test scores to read; must be > 1 * @return the average of the best (how_many - 1) test scores */
int t = 4;
int count = 2;
while ( count <= 4 )
{ t = t * 2;
count = count + 1;
}
I like my dog
dog my like I
summation(i) = 0 + 1 + 2 + ... + iFor example, summation(4) is 0 + 1 + 2 + 3 + 4 = 10. So, write a method that computes summation whose header line reads like this:
public int summation(int i)
product(a, b) = a * (a+1) * (a+2) * ... * b(Note: if b > a holds true, then define product(a, b) = 1.) For example, product(3, 6) is 3 * 4 * 5 * 6 = 360.
0! = 1 n! = 1 * 2 * ... * n, for positive nFor example, 5! is 1 * 1 * 2 * 3 * 4 * 5 = 120. (Important: Because the values of m! grow large quickly as m grows, use the Java data type long (``long integer'') instead of int for the argument and answer of this function.)
/** sine calculates the sine value of its argument, using the formula * sin(x) = x - (x^3/3!) + (x^5/5!) - (x^7/7!) + ... - (x^n/19!) * @param x - the value, in radians, whose sine is desired * (i.e., sine(0)=0, sine(pi/2)=1, sine(pi)=0, sine(3pi/2)=-1, etc.) * @return the sine as calculated by the formula */ public double sine(double x)(Note: use Math.pow(a,b) to compute ab.) Compare the answers your method produces to the ones produced by the method, Math.sin(...).
/** cosine calculates the cosine value of its parameter, using the formula * cosin(x) = 1 - (x^2/2!) + (x^4/4!) - (x^6/6!) + ... - (x^20/20!) * @param x - the value, in radians, whose cosine is desired * @return the cosine as calculated by the formula */ public double cosine(double x)
Assuming that the size of the bulls-eye is also set by the user, we can use the definite iteration pattern to paint each stripe, one at a time, from the outermost to the innermost. Three variables will be needed to control the painting:
The three variables are used in the painting algorithm:
Perhaps we write the algorithm as a method, so that the method can be used at will to paint bulls-eyes at whatever position, number of rings, and diameter that we desire: Figure 2 displays the Java method that is parameterized on these arguments.
FIGURE 2: method that paints a bulls-eye================================
/** paintBullsEye paints a bulls-eye
* @param x_position - of the upper left corner of the bulls-eye
* @param y_position - of the upper left corner of the bulls-eye
* @param rings - the number of rings in the bulls-eye
* @size - the bulls-eye's diameter
* @param g - the graphics pen */
public void paintBullsEye(int x_position, int y_position,
int rings, int size, Graphics g)
{ int count = 0; // no rings painted just yet
int diameter = size; // diameter of next ring to paint
int ring_width = size / rings; // set width for each ring
Color color = Color.red;
while ( count != rings )
// invariant: have painted count rings so far
{ // calculate upper left corner of ring to paint, centering the
// the ring within the bulls-eye by dividing by 2:
int new_x_position = x_position + ((ring_width * count)/2);
int new_y_position = y_position + ((ring_width * count)/2);
// paint the ring:
g.setColor(color);
g.fillOval(new_x_position, new_y_position, diameter, diameter);
// increment variables:
count = count + 1;
diameter = diameter - ring_width;
if ( color == Color.red )
{ color = Color.white; }
else { color = Color.red; }
}
}
ENDFIGURE======================================================
The method in Figure 2 is used as a helper method in the
class that displays the graphics window---see Figure 3.
FIGURE 3: a panel that displays a bulls-eye===========================
import javax.swing.*;
import java.awt.*;
/** BullsEyeWriter paints a bulls-eye on a panel */
public class BullsEyeWriter extends JPanel
{ private int rings; // how many rings appear in the bulls-eye
private int size; // the size of the completed bulls-eye
private int panel_width; // width of the graphics panel
private int offset = 20; // where to start painting the bulls-eye
/** Constructor BullsEyeWriter constructs the panel and frames it.
* @param number_of_rings - how many rings in the bulls-eye
* @param total_size - the diameter of the bulls-eye */
public BullsEyeWriter(int number_of_rings, int total_size)
{ rings = number_of_rings;
size = total_size;
panel_width = size + (2 * offset);
// construct frame for this panel:
JFrame my_frame = new JFrame();
my_frame.getContentPane().add(this);
my_frame.setTitle("Bulls-Eye");
my_frame.setSize(panel_width, panel_width);
my_frame.setVisible(true);
}
/** paintComponent draws the bulls-eye
* @param g - the graphics pen that does the drawing */
public void paintComponent(Graphics g)
{ g.setColor(Color.yellow); // paint background yellow:
g.fillRect(0, 0, panel_width, panel_width);
paintBullsEye(offset, offset, rings, size, g);
}
... paintBullsEye appears here ...
}
ENDFIGURE=============================================================
To use class BullsEyeWriter, we would construct
a new object such as
new BullsEyeWriter(7, 140)which draws a 7-ring bulls-eye of diameter 140 pixels.
new BullsEyeWriter(21, 200)Explain why it is important that the bulls-eye's circles are painted from the largest to the smallest; explain why the innermost ring (a circle, actually) has a width that is almost twice as large as all the other rings. (Hint: insert a System.out.println(diameter) statement into the paintBullsEye method to monitor the drawing of the rings.)
/** paintSquares paints n squares across the left-to-right diagonal
* of a graphics window
* @param x_position - of the upper left corner of the first square
* @param y_position - of the upper left corner of the first square
* @param n - the number of squares to paint
* @size - the width of each square
* @param g - the graphics pen */
private void paintsquares(int x_position, int y_position,
int n, int size, Graphics g)
Recall the computeAverage method in Figure 1, which read a sequence of exam scores, summed them, and computed their average. What happens when we invoke the method with a negative integer, e.g., computeAverage(-1)? Indeed, the invocation requests exam scores forever, summing the scores without ceasing, and we will see an indefinite produced,
count = 1; total = 8 count = 2; total = 13 count = 3; total = 19 count = 4; total = 26 count = 5; total = 30 ...assuming that the user is patient enough to submit a never-ending sequence of scores!
The loop inside computeAverage iterates indefinitely because its test expression is always true. Such behavior is called nontermination, or more crudely, infinite looping or just ``looping.'' A nonterminating loop prevents the remaining statements in the program from executing, and in this case, the method from computing the average and returning an answer.
Although the method's header comment tells us to supply only nonnegative parameters to computeAverage, the method might defend itself with a conditional statement that checks the parameter's value:
/** computeAverage computes the average of test scores submitted by a user
* @param how_many - the quantity of test scores to read; must be nonnegative
* @return the average of the test scores
* @throw RuntimeException, if how_many is negative */
public double computeAverage(int how_many)
{ if ( how_many <= 0 )
{ throw new RuntimeException("computeAverage error: negative quantity"); }
double total_points = 0.0; // the total of all test scores
int count = 0; // the quantity of tests read so far
while ( count != how_many )
{ ... see Figure 1 for the loop's body ... }
return (total_points / how_many);
}
The initial conditional statement throws an exception to prevent looping.
Often, nontermination is an unwanted behavior, and unfortunately there is no mechanical technique that can verify that a given loop must terminate, but the section titled ``Loop Termination,'' included as an optional section at the end of the Chapter, presents a technique that helps one prove loop termination in many cases.
If one of your Java applications appears to have infinite looping, you can terminate it: When using an IDE, select the Stop or Stop Program button; when using the JDK, press the control and c keys simultaneously.
Finally, we should note that a while-loop's test can sometimes be written cleverly so that looping becomes impossible. Consider again the loop in Figure 1, and say that we rewrite the loop's test so that the Figure reads as follows:
public double modifiedComputeAverage(int how_many)
{ double total_points = 0.0;
int count = 0;
while ( count < how_many )
{ String input = JOptionPane.showInputDialog("Type next exam score:");
int score = new Integer(input).intValue();
total_points = total_points + score;
count = count + 1;
System.out.println("count = " + count + "; total = " + total_points);
}
return (total_points / how_many);
}
Now,
if how_many receives
a nonpositive value, then the loop's test
fails immediately, and the loop executes zero iterations.
But the simple alteration is imperfect, because it allows the method to continue its execution with an improper value for how_many and compute an erroneous result: If how_many holds a negative number, then the method computes that the exam average is 0.0, which is nonsensical, and if how_many holds zero, the result is even more surprising---try modifiedComputeAverage(0) and see.
Perhaps looping is unwanted, but under no conditions do we want a method that returns a wrong answer, either. For this reason, you should take care when altering a while-loop's test to ``ensure'' termination; the alteration might cause a wrong answer to be computed, travel to another part of the program, and do serious damage.
/** printReciprocals displays the decimal values of the fractions, * 1/2, 1/3, 1/4, ..., one at a time: When invoked, * it shows a message dialog with the information, "1/2 = 0.5", * and when the user presses OK, it shows another message dialog * that says, "1/3 = 0.3333333333", and when the user presses OK, * it shows another message dialog, "1/4 = 0.25", and so on.... */ public void printReciprocals()Now, write an application that invokes it. Test the application for as long as you have the patience to do so.
Study the invariant property for the loop in the computeAverage method in Figure 1. When the loop in that method concludes, we know that total_points == exam_1 + exam_2 + ... + exam_how_many holds true.
Now, review modifiedComputeAverage. Is the loop invariant the same as that in Figure 1? Can we conclude the same result when the loop terminates as we did in Figure 1? What can we conclude about the value of total_points when the loop in modifiedComputeAverage terminates?
Many programs are designed to interact with a user indefinitely; for example, the bank-account manager application in Chapter 6 processed as many account transactions as its user chose to enter. The appplication did this by sending a message to restart itself after processing each input request, but we see in this Section that a while-loop is a simpler technique for repetitive input processing.
We can build on the exam-average method in Figure 1 to illustrate the technique. Say that we modify the method so that it does not know how many exam scores it must read. Instead, the user enters exam scores, one by one, into input dialogs until the user terminates the process by pressing the Cancel button. The method handles this behavior with a loop that terminates when Cancel is pressed.
A first attempt at the revised method's algorithm might go,
boolean processing = true;
while ( processing )
{ generate a dialog to read the next exam score;
if ( the user pressed Cancel )
{ processing = false; } // time to terminate the loop!
else { add the score to the total and increment the count; }
}
Figure 4 displays the modified method from Figure 1.
FIGURE 4: processing input transactions===========================
import javax.swing.*;
/** computeAverage computes the average of test scores submitted by a user.
* The user terminates the submissions by pressing Cancel.
* @return the average of the test scores
* @throw RuntimeException if the user presses Cancel immediately */
public double computeAverage()
{ double total_points = 0.0; // the total of all test scores
int count = 0; // the quantity of tests read so far
boolean processing = true;
while ( processing )
// at each iteration: total_points == exam_1 + exam_2 + ... + exam_count
{ String input = JOptionPane.showInputDialog
("Type next exam score (or press Cancel to quit):");
if ( input == null ) // was Cancel pressed?
{ processing = false; } // time to terminate the loop
else { int score = new Integer(input).intValue();
total_points = total_points + score;
count = count + 1;
}
}
if ( count == 0 ) // did the user Cancel immediately?
{ throw new RuntimeException("computeAverage error: no input supplied"); }
return (total_points / count);
}
ENDFIGURE=================================================================
There is a standard way to process a user's input with a while-loop: A sequence of input transactions are submitted, one at a time, and each input transaction is processed by one iteration of the loop. The loop terminates when there are no more input transactions. Here is the pattern:
boolean processing = true;
while ( processing )
{ READ AN INPUT TRANSACTION;
if ( THE TRANSACTION INDICATES THAT THE LOOP SHOULD STOP )
{ processing = false; }
else { PROCESS THE TRANSACTION; }
}
This pattern was used in Figure 4 and can be profitably used for
most input-processing applications.
The loop is an example of indefinite iteration, because
when the loop starts, it is not decided how many iterations will occur
until termination. Note that indefinite iteration is different from
nontermination---assuming that there are finitely many input transactions,
the loop will terminate!
public static void main(String[] args)
{ boolean processing = true;
int total = 0;
while ( processing )
{ String s = JOptionPane.showInputDialog("Type an int:");
int i = new Integer(s);
if ( i < 0 )
{ processing = false; }
else { total = total + i; }
}
JOptionPane.showMessageDialog(null, total);
}
String s = ""; ... s = s + a_line_of_text + "\n";Recall that the \n is the newline character.)
Recall these two useful operations on strings from Table 5, Chapter 3:
String s = "abcde"; int i = s.length();assigns 5 to i. The length of an empty string, "", is 0.
String s = "abcde"; char c = s.charAt(3);assigns 'd' to c. (Recall that a string's characters are indexed by 0, 1, 2, and so on.)
Now we consider how to search a string, s, for a character, c: We examine the string's characters, one by one from left to right, until we find an occurrence of c or we reach the end of s (meaning c is not found). We use an integer variable, index, to remember which character of s we should examine next:
int index = 0;
boolean found = false; // remembers whether c has been found in s
while ( !found && index < s.length() )
{ if ( s.charAt(index) == c )
{ found = true; }
else { index = index + 1; }
}
The loop's test consists of two boolean expressions, combined by
conjunction (&&), and the loop terminates when either of the
conjuncts becomes false.
This algorithm is realized in Figure 5.
FIGURE 5: searching for a character in a string========================
/** findChar locates the leftmost occurrence of a character in a string.
* @param c - the character to be found
* @param s - the string to be searched
* @return the index of the leftmost occurrence of c in s;
* return -1 if c does not occur in s */
public int findChar(char c, String s)
{ boolean found = false; // remembers if c has been found in s
int index = 0; // where to look within s for c
while ( !found && index < s.length() )
// invariant:
// (1) found == false means c is not any of chars 0..(index-1) in s
// (2) found == true means c is s.charAt(index)
{ if ( s.charAt(index) == c )
{ found = true; }
else { index = index + 1; }
}
if ( !found ) // did the loop fail to find c in all of s?
{ index = -1; }
return index;
}
ENDFIGURE===============================================================
The loop's invariant property tells us how the loop operates: As long as found is false, c is not found in the searched prefix of s; when found becomes true, the search has succeeded.
The loop might terminate one of two ways:
A string is a kind of ``collection'' or ``set'' of characters. In the general case, one searches a set of items with the following pattern of while-loop:
boolean item_found = false;
DETERMINE THE FIRST ``ITEM'' TO EXAMINE FROM THE ``SET'';
while ( !item_found && ITEMS REMAIN IN THE SET TO SEARCH )
{ EXAMINE AN ITEM;
if ( THE ITEM IS THE DESIRED ONE )
{ item_found = true; }
else { DETERMINE THE NEXT ITEM TO EXAMINE FROM THE SET; }
}
The loop can terminate in two possible ways:
Here is another use of the searching pattern---determining whether an integer is a prime number. Recall that an integer 2 or larger is a prime if it is divisible (with no remainder) by only itself and 1. For example, 3, 13, and 31 are primes, but 4 and 21 are not.
To determine whether an integer n is prime, we try dividing n by each of the numbers in the set, {2, 3, 4, ..., n/2 }, to try to find a number that divides into n with remainder zero. (There is no need to try integers larger than n/2, of course.) If our search for a divisor fails, then n is a prime.
The method's algorithm is based on the searching pattern:
boolean item_found = false;
current = n / 2; // start searching here for possible integer divisors
// and count downwards towards 2
while ( !item_found && current > 1 )
{ if ( current divides into n with remainder 0 )
{ item_found = true; } // current is a divisor of n
else { current = current - 1; } // select another possible divisor
}
The search through the set, {n/2, (n/2) - 1, ..., 3, 2},
terminates if we find a divisor that produces a remainder of 0 or if
we search the entire set and fail.
Figure 6 shows the completed method.
FIGURE 6: method for prime detection===================================
/** isPrime examines an integer > 1 to see if it is a prime.
* @param n - the integer > 1
* @return 1, if the integer is a prime;
* return the largest divisor of the integer, if it is not a prime;
* @throw RuntimeException, if the argument is invalid, that is, < 2. */
public int isPrime(int n)
{ int answer;
if ( n < 2 )
{ throw new RuntimeException("isPrime error: invalid argument " + n ); }
else { boolean item_found = false;
int current = n / 2; // start search for possible integer divisor
while ( !item_found && current > 1 )
// invariant:
// (1) item_found == false means n is not divisible
// by any of n/2, (n/2)-1, ...down to... current+1
// (2) item_found == true means current divides n
{ if ( n % current == 0 )
{ item_found = true; } // found a divisor
else { current = current - 1; } // try again
}
if ( item_found )
{ answer = current; } // current is the largest divisor of n
else { answer = 1; } // n is a prime
}
return answer;
}
ENDFIGURE===============================================================
/** powerOfTwo determines whether its argument is a power of 2. * @param n - the argument, a nonnegative int * @return m, such that n == 2^m, if n is a power of 2 * return -1, if n is not a power of 2 */ public int powerOfTwo(int n)What is the ``collection'' that you are ``searching'' in this problem?
Definite-iteration loops pervade computer programming. When we use this pattern of definite iteration,
{ int i = INITIAL VALUE;
while ( TEST ON i )
{ EXECUTE LOOP BODY;
INCREMENT i;
}
}
there is a
special loop statement in Java, called a for-statement,
that we can use to tersely code the above pattern; it looks like this:
for ( int i = INITIAL VALUE; TEST ON i; INCREMENT i; )
{ EXECUTE LOOP BODY; }
The semantics of the for-statement is exactly the semantics of the
definite iteration pattern, but there is a small technical point:
The scope of the declaration of i extends only as far as
the for-statement's body---the statements following the
for-statement cannot examine i's value.
If it is important that i's value be available after the
loop terminates, then an extra declaration must be prefixed to the loop:
int i;
for ( i = INITIAL VALUE; TEST ON i; INCREMENT i; )
{ EXECUTE LOOP BODY; }
// because i is declared before the loop starts, i's value can be read here
Here is the for-loop that corresponds to the while-loop we saw at the beginning of this Chapter, which prints the decimal values of the reciprocals, 1/2 to 1/20:
for ( int denominator = 2; denominator <= 20; denominator = denominator+1 )
// invariant: 1/2, ...up to..., 1/(denominator-1) printed so far
{ System.out.println("1/" + denominator + " = " + (1.0 / denominator)); }
Compare this to the original while-loop:
int denominator = 2;
while ( denominator <= 20 )
{ System.out.println("1/" + denominator + " = " + (1.0 / denominator));
denominator = denominator + 1;
}
There are two advantages in using the for-statement for definite iteration:
Begin Footnote: Java's for-statement can be used to compute an indefinite iteration (by omitting the INCREMENT i part), but we do not do this in this text. End Footnote
The for-statement is particularly useful for systematically computing upon all the items in a set; here is a loop that easily prints all the characters in a string s, one per line, in reverse order:
for ( int i = s.length() - 1; i >= 0; i = i - 1 )
// invariant: printed characters at s.length()-1 ...downto... (i+1)
{ System.out.println(s.charAt(i)); }
We might wish to generate a 4-by-5 table of all the mutiplications of 0..3 by 0..4. The output might appear like this:
To do this, we must generate all possible combinations of i * j, when i varies in the range 0..3 and i varies in the range 0..4. The algorithm for printing the multiplications might go:
for ( int i = 0; i <= 3; i = i + 1 )
{ // invariant: printed 0*x up to (i-1)*x, for all values x in 0..4
for ( int j = 0; j <= 4; j = j + 1 )
// invariant: printed i*0 up to i*(j-1)
{ System.out.print(i + "*" + j + "=" + (i * j) + " "); }
System.out.println();
}
Note the uses of print and println to format the
rows of the table.
How might we paint an n-by-n chessboard in a graphics window?
This task is also a table-printing problem, where the ``values'' in the table are red and white squares. To understand which squares should be red and which should be white, consider this numbering scheme for the squares, which was suggested by the multiplication table seen earlier:
0, 0 0, 1 0, 2 ... 0, n-1 1, 0 1, 1 1, 2 ... 1, n-1 ... n-1, 0 n-1, 1 n-1, 2 ... n-1, n-1Assuming that the board's upper-left corner (the one numbered by 0,0) is a red square, then it is easy to calculate the color of every square: If the square's number is i,j, then the square is red when i + j is even-valued; otherwise, it is white (when i + j is odd-valued).
We write the algorithm for painting the board by imitating the algorithm for printing the multiplication table:
We write the method so that a chessboard can be painted at whatever position, number of rows, and size a user desires. Figure 7 shows the method, which can be invoked by a panel's paintComponent method, as we saw in the bulls-eye-painting example earlier in this chapter in Figures 2 and 3.
FIGURE 7: method to paint a chessboard===================================
/** paintBoard paints an n-by-n chessboard of red and white squares
* @param start_x - position of the upper left corner of the board
* @param start_y - position of the upper left corner of the board
* @param total_rows - the number of rows of the board
* @param square_size - the width of each square, in pixels
* @param g - the graphics pen */
private void paintBoard(int start_x, int start_y,
int total_rows, int square_size, Graphics g)
{ for ( int x = 0; x < total_rows; x = x + 1 )
// invariant: have painted x rows so far
{ // calculate position of row x:
int x_position = start_x + (x * square_size);
for ( int y = 0; y < total_rows; y = y + 1 )
// invariant: have painted y squares of row x
{ // calculate position of the y-th square:
int y_position = start_y + (y * square_size);
if ( ((x + y) % 2) == 0 ) // is square x,y a red one?
{ g.setColor(Color.red); }
else { g.setColor(Color.white); }
g.fillRect(x_position, y_position, square_size, square_size);
}
}
}
ENDFIGURE===============================================================
When a set of items must be arranged or reordered, nested loops often give a solution. Given a string, s, say that we must construct a new string that has all of s's characters but rearranged in alphabetical order. For example, if s is butterfly, then its alphabetized form is beflrttuy.
The algorithm for alphabetization will copy the characters, one by one, from string s into a new, alphabetized string, which we call answer. Here is an initial algorithm:
answer = "";
for ( int i = 0; i != s.length(); i = i + 1 )
// invariant: characters at indices 0..i-1 have been inserted into answer
{ insertAlphabetically(s.charAt(i), answer); }
The body of the loop contains a helper method,
insertAlphabetically, which will place its first argument,
the character, into the correct position within its second argument,
answer, so that answer remains alphabetized.
What is the algorithm for insertAlphabetically? Let's consider the general probem of inserting a character, c, into its proper position in an alphabetized string, alpha. This is in fact a searching problem, where we search alpha from left to right until we find a character that appears later in the alphabet than does c. We adapt the searching pattern for loops seen earlier in this Chapter:
Helper method insertAlphabetically uses a searching loop to find the correct position to insert each character into the alphabetized string. When the searching loop finishes, local variable index marks the position where the character should be inserted. The insertion is done by the last statement within insertAlphabetically, which makes clever use of the substring method:
return alpha.substring(0, index) + c + alpha.substring(index, alpha.length());That is, alpha.substring(0, index) is the front half of string alpha, from character 0 up to character index, and alpha.substring(index, alpha.length()) is the back half of alpha, from character index to the end.
FIGURE 8: methods for alphabetizing a string=============================
/** alphabetize computes a string that has the same characters as
* its argument but arranged in alphabetical order
* @param s - the input string
* @return the alphabetized string */
public String alphabetize(String s)
{ String answer = "";
for ( int i = 0; i != s.length(); i = i + 1 )
// update the answer by inserting s.charAt(i) into it:
{ answer = insertAlphabetically(s.charAt(i), answer); }
return answer;
}
/** insertAlphabetically inserts c into alpha, preserving
* alphabetical ordering. */
private String insertAlphabetically(char c, String alpha)
{ int index = 0; // the position where we will possibly insert c
boolean searching_for_c_position = true;
while ( searching_for_c_position && index < alpha.length() )
{ if ( c <= alpha.charAt(index) ) // should c be placed at index?
{ searching_for_c_position = false; }
else { index = index + 1; }
}
// ``break'' alpha into two pieces and place c in the middle:
return alpha.substring(0, index)
+ c + alpha.substring(index, alpha.length());
}
ENDFIGURE==============================================================
Note also within insertAlphabetically that the <= operation is used to compare two characters---for example, 'a' <= 'b' computes to true but 'b' <= 'a' is false.
Alphabetization is a special case of sorting, where a collection of items are arranged ordered according to some standardized ordering. (For example, a dictionary is a collection of words, sorted alphabetically, and a library is a collection of books, sorted by the catalog numbers stamped on the books' spines.)
/** removeDuplicateLetters constructs a string that contains the * same letters as its argument except that all duplicate letters * are removed, e.g., for argument, "butterflies", the result is * "buterflis" * @param s - the argument string * @return a string that looks like s but with no duplicates */ public String removeDuplicateLetters(String s)
0 0 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3
0 3 0 2 0 1 0 0 1 3 1 2 0 1 2 3 2 2 3 3
int i = 2;
while ( i != 0 );
{ i = i - 1; }
fails to terminate
because the semicolon after the test causes the Java
compiler to read the code as while ( i != 0 ) {}; { i = i - 1; }---the
loop has an empty body.
Problems also arise when a loop's test is carelessly formulated. For example, this attempt to compute the sum, 1 + 2 + ... + n, fails,
int total = 0;
int i = 0;
while ( i <= n )
{ i = i + 1;
total = total + i;
}
because the loop iterates one time too many.
This form of error, where a loop iterates one time too many or
one time too few, is commonly made, so be alert for it
when testing the loops you write.
A related problem is an improper starting value for the loop counter, e.g.,
int total = 0;
int i = 1;
while ( i <= n )
{ i = i + 1;
total = total + i;
}
This loop again attempts to compute the summation,
1 + 2 + ... + n, but it forgets to add the starting value of
i into its total.
Examples like these show that it is not always obvious when a loop iterates exactly the correct number of times. When you test a loop with example data, be certain to know the correct answer so that you can compare it to the loop's output.
Here is another technical problem with loop tests: Never code a loop's test expression as an equality of two doubles. For example, this loop
double d = 0.0;
while ( d != 1.0 )
{ d = d + (1.0 / 13);
System.out.println(d);
}
should terminate in 13 iterations but in reality
does not due to computer arithmetic, where fractional
numbers like 1/13 are imperfectly represented as fractions
in decimal format.
Formulating test cases for loops is more difficult than formulating test cases for conditionals, because it is not enough to merely ensure that each statement in the loop body is executed at least once by some test case. A loop encodes a potentially infinite number of distinct execution paths, implying that an infinite number of test cases might be needed. Obviously, no testing strategy can be this exhaustive.
In practice, one narrows loop testing to these test cases:
One more time, this attempt to compute the summation 1 + 2 + ... + n,
int n = ... ; // the input value
int total = 0;
int i = 0;
while ( i != n )
{ total = total + i;
i = i + 1;
}
might be tested with n set to 0 (which
we believe should cause immediate
termination), set to 1 (should cause termination in one iteration),
set to, say, 4 (a typical case that requires
multiple iterations), and set to a negative number, say, -1,
(which might cause unwanted behavior).
These test cases quickly expose that
the test expression forces termination one iteration too soon.
Subtle errors arise when a loop's test expression
stops the loop one iteration too soon or one iteration too late;
testing should try to expose these ``boundary cases.''
A more powerful version of loop testing is invariant monitoring: If you wrote an invariant for the loop, you can monitor whether the invariant is holding true while the loop iterates. To do this, insert inside the loop one or more println statements that display the values of the variables used by the loop. (Or, use an IDE to halt the loop at each iteration and display the values of its variables.) Use the variables's values to validate that the loop's invariant is holding true. If the invariant is remaining true, this gives you great confidence that the loop is making proper progress towards the correct answer.
For example, consider Figure 1, which displays a loop that sums a sequence of exam scores. The loop's invariant,
// at each iteration: total_points == exam_1 + exam_2 + ... + exam_counttells us what behavior to observe at the start (and the end) of each loop iteration. The println statement placed at the end of the loop in Figure 1 lets us verify that the invariant property that we believed to be true is in fact holding true during the execution.
If we monitor a loop's invariant, like the one in Figure 1, and we find that the invariant goes false at some interation, this is an indication that either the loop's code or the invariant is incorrectly written. In the former case, repair is clearly needed; in the latter case, we do not understand what our loop should do and we must study further.
Although loop testing can never be exhaustive, please remember that any testing is preferable to none---the confidence that one has in one's program increases by the number of test cases that the program has successfully processed.
A simple but classic animation is a ball bouncing within a box:
(Although the printed page cannot show it, the red ball is travelling from side to side within the frame.)
A program written in the Model-View-Controller architectural style does best: The animation is modelled, in this case, by objects that represent the ball and box. A view paints the model's current state on the display. Finally a controller monitors the passage of time and tells the model when to update the ball's position and repaint it on the display.
Figure 9 shows the architecture of the animation program. The controller contains a loop that executes an iteration for each unit of time that passes. At each unit of time, the loop's body tells the model to update its state, and it tells the view to repaint the model; the repeated paintings look like movement. The model and view have methods that respond to the controller's requests. Also, the view must ask the model for its current state each time the model must be painted.
FIGURE 9: architecture of a simple animation===========================ENDFIGURE===============================================================
Recall once more the steps we take to design and solve a programming
problem:
Let's move through these steps:
We begin with the model subassembly of the animation---What are the model's components? They are of course the ball and the box in which the ball moves. Our first attempt at specifying the model might place ball and box together in one class, like this:
| class BallAndBox | maintains a ball that moves within a box |
| Attributes | |
| the box's size, the ball's size, the ball's position, the ball's velocity | |
| Methods | |
| moveTheBall(int time_units) | Updates the model's state by moving the ball a distance based on its current position, its velocity, and the amount of time, time_units, that have passed since the last time the state has been updated. |
| getTheState() | Returns the current position of the ball, its size, and the dimensions of the box. |
This initial specification is a bit problematic: The attributes of the ball and the box are mixed together, and this will cause trouble if we later modify the animation, say by using two balls or using a different form of container. The specification of the getTheState also has some confusion about what exactly is the state of the model.
These concerns motivate us to design the model as two classes---one class for the ball and one for the box.
Let's consider the ball's class first---what are its attributes and what are its methods? Of course, a ball has a physical size and location (x- and y-coordinates). Because it is moving in two-dimensional space, it has a velocity in both x- and y-coordinates. The primary method the ball requires is the ability to move on request. This produces the specification of class MovingBall that appears in Table 10.
TABLE 10: specification of moving ball=======================
| class MovingBall | models a ball that moves in two-dimensional space |
| Attributes | |
| int x_pos, int y_pos | the center coordinates of the ball's location |
| radius | the ball's radius (size) |
| int x_velocity, int y_velocity | the ball's horizontal and vertical velocities |
| Method | |
| move(int time_units) | moves to its new position based on its velocity the the elapsed amount of time_units, reversing direction if it comes into contact with a wall of the container (the Box) that holds it. |
ENDTABLE===========================================================In addition to its mutator method, move, the final version of class MovingBall will also possess accessor methods that return the ball's radius, position, and so on.
The description of the move method in Figure 10 makes clear that the moving ball must send messages to the box in which it is contained, to learn if it has hit a well and must change its direction. This motivates us to design class Box. A box's attributes are just the positions of its walls, and assuming that the box is shaped as a square, it suffices to remember just the box's width. A box does not actively participate in the moving-ball animation, but it must have methods that reply when asked if a given position is in contact with a wall.
Table 11 shows one way to specify class Box.
TABLE 11: specification of box====================================
| class Box | models a square box |
| Attribute | |
| int BOX_SIZE | the width of the square box |
| Methods | |
| inHorizontalContact(int x_position): boolean | responds whether x_position (a horizontal coordinate) is in contact with one of the Box's (leftmost or rightmost) walls |
| inVerticalContact(int y_position): boolean | responds whether y_position (a vertical coordinate) is in contact with one of the Box's (upper or lower) walls |
ENDTABLE===========================================================
At this point, the design of the model is mostly complete. Refinements might be made as the programming problem is better understood, but the specifications are a good starting point for developing the remainder of the program.
Now, we can write the classes. As usual, class Ball has accessor methods that yield the values of its attributes. The most interesting method is move, which updates the ball's state; its algorithm goes
FIGURE 12: model of moving ball=============================
/** MovingBall models a moving ball */
public class MovingBall
{ private int x_pos; // ball's center x-position
private int y_pos; // ball's center y-position
private int radius; // ball's radius
private int x_velocity = +5; // horizonal speed; positive is to the right
private int y_velocity = +2; // vertical speed; positive is downwards
private Box container; // the container in which the ball travels
/** Constructor MovingBall constructs the ball.
* @param x_initial - the center of the ball's starting horizontal position
* @param y_initial - the center of the ball's starting vertical position
* @param r - the ball's radius
* @param box - the container in which the ball travels */
public MovingBall(int x_initial, int y_initial, int r, Box box)
{ x_pos = x_initial;
y_pos = y_initial;
radius = r;
container = box;
}
/** xPosition returns the ball's current horizontal position */
public int xPosition()
{ return x_pos; }
/** yPosition returns the ball's current vertical position */
public int yPosition()
{ return y_pos; }
/** radiusOf returns the ball's radius */
public int radiusOf()
{ return radius; }
/** move moves the ball
* @param time_units - the amount of time since the ball last moved */
public void move(int time_units)
{ x_pos = x_pos + (x_velocity * time_units);
if ( container.inHorizontalContact(x_pos) )
{ x_velocity = -x_velocity; } // reverse horizontal direction
y_pos = y_pos + (y_velocity * time_units);
if ( container.inVerticalContact(y_pos) )
{ y_velocity = -y_velocity; } // reverse vertical direction
}
}
ENDFIGURE================================================================
The coding of class Box is simple, because the box's state is fixed when the box is constructed, so the box's methods merely return properties related to the positions of the box's walls. See Figure 13.
FIGURE 13: model of a box======================
/** Box models a box in which moving objects live */
public class Box
{ private int box_size; // the size of the box
/** Constructor Box builds the box
* @param size - the size of the box */
public Box(int size)
{ box_size = size; }
/** inHorizontalContact replies whether a position has contacted a
* horizontal wall.
* @param x_position - the position examined
* @return true, if x_position equals or exceeds the positions of the
* horizontal walls; return false, otherwise */
public boolean inHorizontalContact(int x_position)
{ return (x_position <= 0 ) || (x_position >= box_size); }
/** inVerticalContact replies whether a position has contacted a
* vertical wall.
* @param y_position - the position examined
* @return true, if y_position equals or exceeds the positions of the
* vertical walls; return false, otherwise */
public boolean inVerticalContact(int y_position)
{ return (y_position <= 0 ) || (y_position >= box_size); }
/** sizeOf returns the size of the box */
public int sizeOf()
{ return box_size; }
}
ENDFIGURE==========================================================
Because class MovingBall depends on class Box, we test the classes together, say, by writing a testing program that constructs a box and places the ball in the middle of the box. Then, we tell the ball to move and we print its new position. Of course, we should move the ball until it comes into contact with a wall so that we can see how the ball's direction changes as a result. Here is some testing code:
Box box = new Box(50); // 50 pixels by 50 pixels in size
MovingBall ball = new MovingBall(25, 25, 10, box); // radius is 10 pixels
while ( true )
{ ball.move(1); // 1 unit of elapsed time
System.out.println("x = " + ball.xPosition()
+ "; y = " + ball.yPosition());
}
The ball and box become more interesting once we write a view to paint them. Since the model is designed in two components, we propose a view class that paints the box and a view class that paints the ball. This will make it easier to extend the animation later to contain multiple moving balls, and it suggests the pleasant idea that each model component should have its own view component. Here is a diagram of how the view classes might be specified:
When the animation must be painted, an AnimationWriter is asked to paint the entire picture on a panel. This class asks the BoxWriter to paint the box and it asks the BallWriter to paint a ball. The latter two classes query the accessor methods of their respective model components for the state of the box and ball.
There is little more to specify about the view classes, so we study their codings. Figure 14 presents class AnimationWriter; notice how this class gives its graphics pen to class BoxWriter and then to class BallWriter, presented in Figure 15, so that the box and ball are painted on the window with which the graphics pen is associated.
FIGURE 14: view class for moving-ball simulation======================
import java.awt.*;
import javax.swing.*;
/** AnimationWriter displays a box with a ball in it. */
public class AnimationWriter extends JPanel
{ private BoxWriter box_writer; // the output-view of the box
private BallWriter ball_writer; // the output-view of the ball in the box
/** Constructor AnimationWriter constructs the view of box and ball
* @param b - the box's writer
* @param l - the ball's writer
* @param size - the frame's size */
public AnimationWriter(BoxWriter b, BallWriter l, int size)
{ box_writer = b;
ball_writer = l;
JFrame my_frame = new JFrame();
my_frame.getContentPane().add(this);
my_frame.setTitle("Bounce");
my_frame.setSize(size, size);
my_frame.setVisible(true);
}
/** paintComponent paints the box and ball
* @param g - the graphics pen */
public void paintComponent(Graphics g)
{ box_writer.paint(g);
ball_writer.paint(g);
}
}
ENDFIGURE==================================================
FIGURE 15: view classes for box and ball===========================
import java.awt.*;
/** BoxWriter displays a box */
public class BoxWriter
{ private Box box; // the (address of the) box object that is displayed
/** Constructor BoxWriter displays the box
* @param b - the box that is displayed */
public BoxWriter(Box b)
{ box = b; }
/** paint paints the box
* @param g - the graphics pen used to paint the box */
public void paint(Graphics g)
{ int size = box.sizeOf();
g.setColor(Color.white);
g.fillRect(0, 0, size, size);
g.setColor(Color.black);
g.drawRect(0, 0, size, size);
}
}
import java.awt.*;
/** BallWriter displays a moving ball */
public class BallWriter
{ private MovingBall ball; // the (address of the) ball object displayed
private Color balls_color; // the ball's color
/** Constructor BallWriter
* @param x - the ball to be displayed
* @param c - its color */
public BallWriter(MovingBall x, Color c)
{ ball = x;
balls_color = c;
}
/** paint paints the ball on the view
* @param g - the graphics pen used to paint the ball */
public void paint(Graphics g)
{ g.setColor(balls_color);
int radius = ball.radiusOf();
g.fillOval(ball.xPosition() - radius,
ball.yPosition() - radius, radius * 2, radius * 2);
}
}
ENDFIGURE================================================================
We can test the view classes with the model we have already
built and tested.
Finally, the program's controller uses a loop to control the progress of the simulation; its algorithm is
The while-loop in the run method of class BounceController is intended not to terminate, hence its test is merely true. To present an illusion of movement, the same technique from motion pictures is used: Method delay pauses the program slightly (here, 20 milliseconds, but this should be adjusted to look realistic for the processor's speed) before advancing the ball one more step. The method uses a built-in method, Thread.sleep, which must be enclosed by an exception handler. These details are unimportant, and the delay method may be copied and used whereever needed.
FIGURE 16: controller and start-up class for moving-ball animation========
/** BounceController controls a moving ball within a box. */
public class BounceController
{ private MovingBall ball; // model object
private AnimationWriter writer; // output-view object
/** Constructor BounceController initializes the controller
* @param b - the model object
* @param w - the output-view object */
public BounceController(MovingBall b, AnimationWriter w)
{ ball = b;
writer = w;
}
/** runAnimation runs the animation by means of an internal clock */
public void runAnimation()
{ int time_unit = 1; // time unit for each step of the animation
int painting_delay = 20; // how long to delay between repaintings
while ( true )
{ delay(painting_delay);
ball.move(time_unit);
System.out.println(ball.xPosition() + ", " + ball.yPosition());
writer.repaint(); // redisplay box and ball
}
}
/** delay pauses execution for how_long milliseconds */
private void delay(int how_long)
{ try { Thread.sleep(how_long); }
catch (InterruptedException e) { }
}
}
ENDFIGURE=========================================================
FIGURECONT 16: start-up class for moving-ball animation (concl.)=======
import java.awt.*;
/** BounceTheBall constructs and starts the objects in the animation. */
public class BounceTheBall
{ public static void main(String[] args)
{ // construct the model objects:
int box_size = 200;
int balls_radius = 6;
Box box = new Box(box_size);
// place the ball not quite in the box's center; about 3/5 position:
MovingBall ball = new MovingBall((int)(box_size / 3.0),
(int)(box_size / 5.0),
balls_radius, box);
BallWriter ball_writer = new BallWriter(ball, Color.red);
BoxWriter box_writer = new BoxWriter(box);
AnimationWriter writer
= new AnimationWriter(box_writer, ball_writer, box_size);
// construct the controller and start it:
new BounceController(ball, writer).runAnimation();
}
}
ENDFIGURE=================================================================
The moving-ball animation is a good start towards building more complex animations, such as a billiard table or a pinball machine. Indeed, here is a practical tip: If you are building a complex animation, it helps to build a simplistic first version, like the one here, that implements only some of the program's basic behaviors. Once the first version performs correctly, then add the remaining features one by one.
For example, if our goal is indeed to build an animated pinball machine, we should design the complete pinball machine but then design and code an initial version that is nothing more than an empty machine (a box) with a moving pinball inside it. Once the prototype operates correctly, then add to the machine one or more of its internal ``bumpers'' (obstacles that the ball hits to score points). Once the pinball correctly hits and deflects from the bumpers, then add the scoring mechanism and other parts.
Each feature you add to the animation causes you to implement more and more of the attributes and methods of the components. By adding features one by one, you will not be overwhelmed by the overall complexity of the animation. The Exercises that follow give a small example of this approach.
No doubt, you have seen a ``recursive picture,'' that is, a picture that contains a smaller copy of itself that contains a smaller copy of itself that contains.... (You can simulate this by hanging two large mirrors on opposite walls, standing in the middle, and looking at one of the mirrors.) It is self-reference that characterizes recursion, and when a method contains a statement that invokes (restarts) itself, we say that the method is recursively defined.
In the bank-accounting example in Chapter 6. we used recursion to restart a method, but now we study a more sophisticated use of recursion, where a complex problem is solved by solving simpler instances of the same problem.
Here is an informal example of recursive problem solving: How do you make a three-layer cake? A curt answer is, ``make a two-layer cake and top it with one more layer!'' In one sense, this answer begs the question, because it requires that we know already how to make a cake in order to make a cake, but in another sense, the answer says we should learn how to make first a simpler version of the cake and use the result to solve the more complex problem.
If we take seriously the latter philosophy, we might write this recipe for making a cake with some nonzero number of layers, say, N+1:
By following the arrows, we understand how the problem of making a multi-layer case is decomposed into simpler problems (see the downwards arrows) and the result is assembled from from the solutions---the pan and layers (see the upwards arrows).
The strategy of solving a task by first solving a simpler version of the task and building on the simpler solution is called problem solving by recursion or just recursion, for short. When we solve a problem by recursion, we can approach it as a task of writing simultaneous algebraic equations, like these, for cake making:
bakeACake(0) = ... bakeACake(N + 1) = ... bakeACake(N) ..., where N is nonnegativeThe first equation states how a 0-layer cake is made, and the second explains how an N+1-layer cake is made in terms of making an N-layer one. Based on the narrative for cake making, we would finish the equations like this:
bakeACake(0) = place an empty pan on the table bakeACake(N + 1) = bakeACake(N) and top it with one more layerThe algorithm can be used to generate the steps for a 3-layer cake:
bakeACake(3)
=> bakeACake(2)
and top it with one more layer
=> (bakeACake(1)
and top it with one more layer)
and top it with one more layer
=> ((bakeACake(0)
and top it with one more layer))
and top it with one more layer)
and top it with one more layer
=> ((place an empty pan on the table
and top it with one more layer))
and top it with one more layer)
and top it with one more layer
A recursive algorithm can be reformatted into a Java method that uses recursion. Perhaps there is a Java data type, named Cake, such that new Cake() constructs a 0-layer cake. Perhaps Cake objects have a method, named addALayer, which places one more layer on a cake. For fun, a version of class Cake is displayed in Figure 17.
FIGURE 17: class Cake================================================
/** class Cake is a simple model of a multi-layer cake */
public class Cake
{ int how_many_layers;
/** Constructor Cake constructs a 0-layer cake---a pan */
public Cake()
{ how_many_layers = 0; }
/** addALayer makes the Cake one layer taller */
public void addALayer()
{ how_many_layers = how_many_layers + 1; }
/** displayTheCake prints a representation of the cake */
public void displayTheCake()
{ ... left as a project for you to do ... }
}
ENDFIGURE============================================================
Now, we can use class Cake to reformat the two algebraic equations for cake making into the Java method displayed in Figure 18.
FIGURE 18: a recursive method for cake making========================
/** bakeACake makes a multi-layer cake
* @param layers - the number of the cake's layers
* @return the cake */
public Cake bakeACake(int layers)
{ Cake result;
if ( layers == 0 )
// then the first equation applies:
// bakeACake(0) = place an empty pan on the table
{ result = new Cake(); }
else // the second equation applies:
// bakeACake(N + 1) = bakeACake(N) and top it with one more layer
{ result = bakeACake(layers - 1);
result.addALayer();
}
return result;
}
ENDFIGURE========================================================
Now, the assignment,
Cake c = bakeACake(0);constructs a 0-layer cake. More interesting is
Cake c = bakeACake(3);because this triggers bakeACake(2), which invokes bakeACake(1), which starts bakeACake(0). The last invocation constructs a new cake object, which is then topped by three layers and eventually assigned to variable c. To understand the process, we should study an execution trace.
We now study how the method in Figure 12 contructs its answer by recursion in an example invocation of bakeACake(3).
The invocation causes 3 to bind to the the formal parameter, layers; it and the local variable, result, are created:
The test marked by >1??? computes to false, meaning that the next step is a recursive invocation:
The invocation causes a fresh, distinct activation record of bakeACake to be executed:
This shows that a recursive method invocation works like any other invocation: actual parameters are bound to formal parameters, and a fresh copy of the method's body executes.
Further execution causes two more copies of bakeACake to be invoked, producing this configuration:
Because the conditional's test evaluates to true, the conditional's then-arm constructs a new Cake object and places its address, a1, in the local variable, result.
The 0-layer cake is returned as the result, and the activation record for the completed invocation disappears.
Next, result.addALayer() adds a layer to the cake, and the one-layer cake is returned as the result:
This process repeats until the result variable at the initial invocation receives the cake object at address a1 and places the third layer on it.
The example shows how each recursive invocation decreases the actual parameter by 1, halting when the parameter has 0. When an invoked method returns its result, the result is used by the caller to build its result. This matches our intuition that recursion is best used to solve a problem in terms of solving a simpler or smaller one.
Admittedly, the cake-making example is contrived, and perhaps you have already noticed that, given class Cake, we can ``make'' an N-layer cake with this for-loop:
Cake c = new Cake();
for ( int i = 1; i != N; i = i + 1 )
{ c.addALayer(); }
But the style of thinking used when writing the for-loop is different
than the style used when writing the recursively defined method.
The loop in the previous paragraph should remind you that an incorrectly written repetitive computation might not terminate---this holds true for loops and it holds true for recursively defined methods as well. It is not an accident that the cake-making example used recursive invocations with an argument that counted downward from an nonnegative integer, N, to 0. As a rule:
Many computing problems that require counting can be solved by recursion. One classic example is permutation counting: Say that we want to calculate the total number of permutations (orderings) of n distinct items. For example, the permutations of the three letters a, b, and c are abc, bac, bca, acb, cab, and cba---there. are six permutations.
Permutation generation has tremendous importance to planning and scheduling problems, for example:
It is valuable for us to know how to generate and count permutations. To study this problem, say that we have n distinct letters, and we want to count all the permutations of the letters. The following observation holds the secret to the solution:
Next, given the very last, nth letter, we ask, ``how many permutations can we make from the m words using one more letter?'' The answer is, we can insert the new letter it into all possible positions in each of the m words: We take word1, which has length n-1, and we insert the new letter in all n possible positions in word1. This generates n distinct permutations of length n. We do the same for word2, giving us n more permutations. If we do this for all m words, we generate m sets of n permutations each, that is, a total of n * m permutations of length n. This is the answer.
The above insights tell us how to count the quantity of permutations: For an alphabet of just one letter, there is just one permutation:
number_of_permutations_of(1) = 1If the alphabet has n+1 letters, we count the permutations made from n letters, and we use the technique described above to count the permutations generated by the addition of one more letter:
number_of_permutations_of(n+1) = (n + 1) * number_of_permutations_of(n)
These two equations define an algorithm for computing the quantity of permutations. We can use this algorithm to quickly count the permutations of 4 distinct letters:
number_of_permutations_of(4) = 4 * number_of_permutations_of(3) = 4 * ( 3 * number_of_permutations_of(2) ) = 4 * ( 3 * ( 2 * number_of_permutations_of(1) )) = 4 * 3 * 2 * 1 = 24Calculations with this algorithm quickly convince us that even small alphabets generate huge quantities of permutations.
Not surprisingly, permutation counting occurs often in probability and statistics theory, where it is known as the factorial function. It is traditional to write the factorial of a nonnegative integer, n, as n!, and calculate it with these equations:
It is easy to translate these two equations into a recursively defined method that computes factorials of integers:
public int fac(int n)
{ int answer;
if ( n == 0 )
{ answer = 1; } // 0! = 1
else { answer = n * fac(n - 1); } // (n+1)! = (n+1) * n!
return answer;
}
If you test the function, fac, on the computer,
you will see that, when the argument to fac is greater than
13, the answer is
so huge that it overflows
the internal computer representation of an integer!
BeginFootnote: Unfortunately, a Java int can hold a value only between the range of about negative 2 billion and positive 2 billion. EndFootnote.
For this reason, we revise method fac so that it uses Java's long version of integers. We also make check that the argument to the function is not so large that the computed answer will overflow the internal representation of a long integer. See Figure 19 for the implementation of the factorial function.
FIGURE 19: recursively defined method that computes factorial==============
/** factorial computes n! for n in the range 0..20.
* (note: answers for n > 20 are too large for Java to compute,
* and answers for n < 0 make no sense.)
* @param n - the input; should be in the range 0..20
* @return n!, if n in 0..20
* @throw RuntimeException, if n < 0 or n > 20 */
public long factorial(int n)
{ long answer;
if ( n < 0 || n > 20 )
{ throw new RuntimeException("factorial error: illegal input"); }
else { if ( n == 0 )
{ answer = 1; } // 0! = 1
else { answer = n * factorial(n - 1); } // (n+1)! = (n+1) * n!
}
return answer;
}
ENDFIGURE===============================================================
When you test the factorial function, say by
System.out.println("4! = " + factorial(4));
you will find that the invocation of factorial(4)
generates the invocation to factorial(3), and so on,
down to factorial(0). Then, once the invoked functions
starting returning their answers, a series of four multiplications
are performed, which compute the result, 24. This pattern of
invocations and multiplications are displayed when we compute
with factorial's algorithm:
4! => 4 * 3! => 4 * (3 * 2!) => 4 * (3 * (2 * 1!)) => 4 * (3 * (2 * (1 * 0!))) => 4 * (3 * (2 * (1 * 1))) => 4 * (3 * (2 * 1)) => 4 * (3 * 2) => 4 * 6 => 24
public long factorial(int n)
{ long answer;
if ( n < 0 || n > 20 )
{ throw new RuntimeException("factorial error: illegal input"); }
else { answer = 1;
int count = 0;
while ( count != n )
// invariant: answer == count!
{ count = count + 1;
answer = count * answer;
}
}
return answer;
}
The loop mimicks the sequence of multiplications that compute
the answer.
Since the statements in the body of the loop bear no resemblance to
the original recursive algorithm, we rely on the loop's invariant
to understand why the loop computes the correct result.
In practice, many counting problems are best solved with recursive techniques. If the recursive solution has a simple form, like those seen in the cake-making and factorial examples, then it may be possible to rewrite the recursive implementation into a loop. But the next section shows counting problems where solutions with multiple recursions are needed; such solutions do not always convert to loop code.
Perhaps we are obsessed by insects and want to know how reproductive house flies are. Say that, in its lifetime, one house fly lays exactly two eggs. Each egg produces a fly that itself lays exactly two eggs. If this process occurs for n generations of egg-laying, how many flies result? (Assume that the flies never die.)
Because each fly gives birth to two more flies, which themselves give birth to even more, the pattern of counting cannot be done by a simple iteration---we must solve the problem by thinking about it as a counting problem that ``decomposes'' into two more counting problems.
An answer to the problem is that the total number of flies produced by the original fly is the sum of the flies produced by the first egg, plus the flies produced by the second egg, plus the original fly. If we say that the original fly is n-generations old, then its child flies are one generation younger---each are n-1 generations old. We have this recursive equation:
flies_at_generation(n) = flies_at_generation(n-1) + flies_at_generation(n-1) + 1
A newly hatched fly is 0-generations old:
flies_at_generation(0) = 1that is, the number of flies produced by a newly hatched fly is just the fly itself.
These two equations generate a Java method that contains two recursions:
public int fliesAtGeneration(int n)
{ int answer;
if ( n < 0 )
{ throw new RuntimeException("error: negative argument"); }
else { if ( n == 0 ) // is it a newly hatched fly?
{ answer = 1; }
else { int first_egg_produces = fliesAtGeneration(n - 1);
int second_egg_produces = fliesAtGeneration(n - 1);
answer = first_egg_produces + second_egg_produces + 1;
}
return answer;
}
When executing the innermost else-clause,
the computer computes the first recursion completely to its integer
result before
it starts the second recursive invocation.
Because each recursive invocation uses
an argument that is smaller than the one given to the caller method,
all the recursions will terminate.
Now that we have used recursive problem solving, we can readily see that the two recursions in the method's innermost else-clause can be replaced by one:
int one_egg_produces = fliesAtGeneration(n - 1); answer = (2 * one_egg_produces) + 1;This simplifies the method and even allows us to rewrite the method's body into a loop, if we so desire.
Although the fly-counting example is a bit contrived, there is a related counting problem that is not: the Fibonacci function. The Fibonacci number of a nonnegative integer is defined in the following way:
The algorithm for the Fibonacci function has an easy coding as a method that uses two recursions in its body. It is a fascinating project to rewrite the method so that it uses only o