|How to Think Like a Computer Scientist|
source ref: ebookit.html
Some of the built-in methods we have used, like the Math functions, have produced results. That is, the effect of invoking the method is to generate a new value, which we usually assign to a variable or use as part of an expression. For example:
But so far all the methods we have written have been void methods; that is, methods that return no value. When you invoke a void method, it is typically on a line by itself, with no assignment:
In this chapter, we are going to write methods that return things. The first example is circleArea, which takes a double as a parameter, and returns the area of a circle with the given radius:
The first thing you should notice is that the beginning of the method definition is different. Instead of public static void, which indicates a void method, we see public static double, which indicates that the return value from this method will have type double. I still haven't explained what public static means, but be patient.
Also, notice that the last line is an alternate form of the return statement that includes a return value. This statement means, "return immediately from this method and use the following expression as a return value." The expression you provide can be arbitrarily complicated, so we could have written this method more concisely:
On the other hand, temporary variables like area often make debugging easier. In either case, the type of the expression in the return statement must match the return type of the method. In other words, when you declare that the return type is double, you are making a promise that this method will eventually produce a floating-point value. If you try to return with no expression, or an expression with the wrong type, the compiler will take you to task.
On the other hand, you can have more than one return statement in a conditional:
But you cannot have more than one return statement in sequence. Once the first one is executed, the method terminates immediately without executing the second (or anything else after the first). Code that appears after a return statement, or any place else where it can never be executed, is called dead code. Some compilers warn you if part of your code is dead.
As you should expect by now, once you define a new method, you can use it as part of an expression, and you can build new methods using others. For example, what if someone gave you two points on the x-axis, and told you that one point is the center of a circle and the other is a point on the circle itself, and asked for the area of the circle?
The first step is to find the radius of the circle, which is the distance between the points, which is the absolute value of their difference:
The second step is to find the area of a circle with that radius, and return it.
Wrapping that all up in a method, we get:
Or, again, we could make that more concise by composing the method invocations:
Finally, you might notice that there is a method in the Math class that calculates absolute values, that you might want to use:
One of the things that's nice here is that built-in methods and the methods that you write work exactly the same way.
The previous section demonstrates some Java language features, but it also suggested a way to develop programs, by starting with a working program and gradually adding one line at a time, so that the program always does something, and so that at any step, if something goes wrong, you know exactly where the error is, because it has to be in the last line you added.
For example, when I write a new method, I often start with something that simply prints its arguments and then returns a bogus value.
The println statement allows me to check whether the method is receiving the arguments I think I am sending it. The return statement is necessary in order to get the program to compile.
Then I would add the first step of the procedure and print the result.
This example shows why temporary variables are useful for debugging--because you can print them. Also, by giving them names, you make the program easier to read.
To test this version I would try invoking it with different values (from main):
That way I can confirm that absoluteValue is doing what I expect, so that the radius is the same in both cases. Finally, I would calculate the area and fix the return statement.
The final version of this method does not print anything; it only produces a return value. The print statements that I included temporarily are called scaffolding, because they were helpful for building the program, but they are not part of the final product. Sometimes it is a good idea to keep the scaffolding around, but comment it out, just in case you need it later.
The key aspects of this development process are:
In the previous section you might have noticed that there are two methods called circleArea that take different parameters. The first version takes a single parameter that is the radius of the circle. The second version takes two points along the x-axis, computes the radius, and then uses the first version to compute the area.
Having more than one method with the same name, which is called overloading, is legal in Java as long as each version takes different parameters. That restriction is important, because the only way Java knows which version to invoke is by looking at the arguments that you provide. If you write:
Java goes looking for a method named circleArea that takes a single double as an argument, and so it uses the first version, which interprets the argument as a radius. If you write:
Java uses the second version of circleArea, which interprets the arguments completely differently.
Many of the built-in Java commands are overloaded, meaning that there are different versions that accept different numbers or types of parameters. For example, there are versions of print and println that accept a single parameter of any type. In the Math class, there is a version of abs that works on doubles (which we used in the previous example), and there is also a version for ints.
Although overloading is a useful feature, it should be used with caution. You might get yourself nicely confused if you are trying to debug one version of a method while accidently invoking a different one.
Actually, that reminds me of one of the cardinal rules of debugging: make sure that the version of the program you are looking at is the version of the program that is running!. Some time you may find yourself making one change after another in your program, and seeing the same thing every time you run it. This is a warning sign that for one reason or another you are not running the version of the program you think you are. To check, stick in a print statement (it doesn't matter what you print) and make sure the behavior of the program changes accordingly.
Many of the operations we have seen so far produce results that are the same type as their operands. For example, the + operator takes two ints and produces an int, or two doubles and produces a double, etc.
The exceptions we have seen are the relational operators, which compare ints and floats and return either true or false. true and false are special values in Java, and together they make up a type called boolean. You might recall that when I defined a type, I said it was a set of values. In the case of ints, doubles and Strings, those sets are pretty big. For booleans, not so big.
Boolean expressions and variables work just like other types of expressions and variables:
The first example is a simple variable declaration; the second example is an assignment, and the third example is a combination of a declaration and as assignment that is sometimes called an initialization. The values true and false are keywords in Java, so they may appear in a different color, depending on your development environment.
As I mentioned, the result of a conditional operator is a boolean, so you can store the result of a comparison in a variable:
and then use it as part of a conditional statement later:
A variable used in this way is frequently called a flag, since it flags the presence or absence of some condition.
There are three logical operators in Java: AND, OR and NOT, which are denoted by the symbols &&, || and !. The semantics (meaning) of these operators is similar to their meaning in English. For example x >= 0 && x < 10 is true only if x is between 0 and 10 (including 0 but not including 10).
evenFlag || n\%3 == 0 is true if either of the flags is true, that is, if the number is even OR the number is divisible by 3.
Finally, the NOT operator has the effect of negating or inverting a boolean expression, so !evenFlag is true if evenFlag is false--if the number is odd.
Logical operators often provide a way to simplify nested conditional statements. For example, how would you write the following code using a single conditional?
Methods can return boolean values just like any other type, which is often convenient for hiding complicated tests inside methods. For example:
The name of this method is isSingleDigit. It is common to give boolean methods names that sound like yes/no questions. The return type is boolean, which means that every return statement has to provide a boolean expression.
The code itself is straightforward, although it is a bit longer than it needs to be. Remember that the expression x >= 0 && x < 10 has type boolean, so there is nothing wrong with returning it directly, and avoiding the if statement altogether:
In main you can invoke this method in the usual ways:
The first line assigns the value true to bigFlag only if 17 is not a single-digit number. The second line prints true because 2 is a single-digit number. Yes, println is overloaded to handle booleans, too.
The most common use of boolean methods is inside conditional statements
Now that we have methods that return values, you might be interested to know that we have a complete programming language, by which I mean that anything that can be computed can be expressed in this language. Any program ever written could be rewritten using only the language features we have used so far (actually, we would need a few commands to control devices like the keyboard, mouse, disks, etc., but that's all).
Proving that that claim is true is a non-trivial exercise first accomplished by Alan Turing, one of the first computer scientists (well, some would argue that he was a mathmatician, but a lot of the early computer scientists started as mathematicians). Accordingly, it is known as the Turing thesis. If you take a course on the Theory of Computation, you will have a chance to see the proof.
To give you an idea of what you can do with the tools we have learned so far, I want to look at some methods for evaluating recursively-defined mathematical functions. A recursive definition is similar to a circular definition, in the sense that the definition contains a reference to the thing being defined. A truly circular definition is typically not very useful:
If you saw that definition in the dictionary, you might be annoyed. On the other hand, if you looked up the definition of the mathematical function factorial, you might get something like:
(Factorial is usually denoted with the symbol !, which is not to be confused with the Java logical operator ! which means NOT.) This definition says that the factorial of 0 is 1, and the factorial of any other value, n, is n multiplied by the factorial of n-1. So 3! is 3 times 2!, which is 2 times 1!, which is 1 times 1!. Putting it all together, we get 3! equal to 3 times 2 times 1 times 1, which is 6.
If you can write a recursive definition of something, you can usually write a Java program to evaluate it. The first step is to decide what the parameters are for this function, and what the return type is. With a little thought, you should conclude that factorial takes an integer as a parameter and returns an integer:
If the argument happens to be zero, all we have to do is return 1:
Otherwise, and this is the interesting part, we have to make a recursive call to find the factorial of n-1, and then multiply it by n.
If we look at the flow of execution for this program, it is similar to nLines from the previous chapter. If we invoke factorial with the value 3:
Since 3 is not zero, we take the second branch and calculate the factorial of n-1...
Since 2 is not zero, we take the second branch and calculate the factorial of n-1...
Since 1 is not zero, we take the second branch and calculate the factorial of n-1...
Since 0 is zero, we take the first branch and return the value 1 immediately without making any more recursive calls.
The return value (1) gets multiplied by n, which is 1, and the result is returned.
The return value (1) gets multiplied by n, which is 2, and the result is returned.
The return value (2) gets multiplied by n, which is 3, and the result, 6, is returned to main, or whoever invoked factorial (3).
Following the flow of execution is one way to read programs, but as you saw in the previous section, it can quickly become labarynthine. An alternative is what I call the "leap of faith." When you come to a method invocation, instead of following the flow of execution, you assume that the method works correctly and returns the appropriate value.
In fact, you have already been practicing this leap of faith when you use built-in methods. When you invoke Math.cos or drawOval, you don't examine the implementations of those methods. You just assume that they work, because the people who wrote the built-in classes were good programmers.
Well, the same is true when you invoke one of your own methods. For example, in Section 5.7 we wrote a method called isSingleDigit that determines whether a number is between 0 and 9. Once we have convinced ourselves that this method is correct--by testing and examination of the code--we can use the method without ever looking at the code again.
The same is also true of recursive programs. When you get to the recursive invocation, instead of following the flow of execution, you should assume that the recursive invocation works (yields the correct result), and then ask yourself, "Assuming that I can find the factorial of n-1, can I compute the factorial of n?" In this case, it is clear that you can, by multiplying by n.
Of course, it is a bit strange to assume that the method works correctly when you have not even finished writing it, but that's why it's called a leap of faith!
In the previous example I used temporary variables to spell out the steps, and to make the code easier to debug, but I could have saved a few lines:
From now on I will tend to use more concise version, but I recommend that you use the more explicit version while you are developing code. When you have it working, you can tighten it up, if you are feeling inspired.
After factorial, the classic example of a recursively-defined mathematical function is fibonacci, which has the following definition:
Translated into Java, this is
If you try to follow the flow of execution here, even for fairly small values of n, your head explodes. But according to the leap of faith, if we assume that the two recursive calls (yes, you can make two recursive calls) work correctly, then it is clear that we get the right result by adding them together.
The Fine Print: Any comments/annotations are owned by whoever posted them. We are not responsible for them in any way. The text of the comments/annotation, and that of any comments/annotation that you post, is covered under the Open Publication License v1.0.
|The Andamooka logo is (C) 2000 by David Sweet. Andamooka is built on SlashCode, MySQL, FreeBSD, and Apache.|
|[ Home | Submit | Preferences ]|