Conditionals and recursion

The modulus operator works on integers (and integer expressions) and yields the remainder when the first operand is divided by the second. In Java, the modulus operator is a percent sign, %. The syntax is the same as for other operators:

The first operator, integer division, yields 2. The second operator yields 1. Thus, 7 divided by 3 is 2 with 1 left over.

The modulus operator turns out to be surprisingly useful. For example, you can check whether one number is divisible by another: if x % y is zero, then x is divisible by y.

Also, you can use the modulus operator to extract the rightmost digit or digits from a number. For example, x % 10 yields the rightmost digit of x (in base 10). Similarly x % 100 yields the last two digits.

4.2 Conditional execution

To write useful programs, we almost always need to check conditions and change the behavior of the program accordingly. Conditional statements give us this ability. The simplest form is the if statement:

The expression in parentheses is called the condition. If it is true, then the statements in brackets get executed. If the condition is not true, nothing happens.

The condition can contain any of the comparison operators, sometimes called relational operators:

Although these operations are probably familiar to you, the syntax Java uses is a little different from mathematical symbols like =, ≠ and ≤. A common error is to use a single = instead of a double ==. Remember that = is the assignment operator, and == is a comparison operator. Also, there is no such thing as =< or =>.

The two sides of a condition operator have to be the same type. You can only compare ints to ints and doubles to doubles.

The operators == and != work with Strings, but they don’t do what you expect. And the other relational operators don’t do anything at all. We will see how to compare strings Section 8.10.

4.3 Alternative execution

A second form of conditional execution is alternative execution, in which there are two possibilities, and the condition determines which one gets executed. The syntax looks like:

If the remainder when x is divided by 2 is zero, then we know that x is even, and this code prints a message to that effect. If the condition is false, the second print statement is executed. Since the condition must be true or false, exactly one of the alternatives will be executed.

As an aside, if you think you might want to check the parity (evenness or oddness) of numbers often, you might want to “wrap” this code up in a method, as follows:

Now you have a method named printParity that will print an appropriate message for any integer you care to provide. In main you would invoke this method like this:

Always remember that when you invoke a method, you do not have to declare the types of the arguments you provide. Java can figure out what type they are. You should resist the temptation to write things like:

4.4 Chained conditionals

Sometimes you want to check for a number of related conditions and choose one of several actions. One way to do this is by chaining a series of ifs and elses:

These chains can be as long as you want, although they can be difficult to read if they get out of hand. One way to make them easier to read is to use standard indentation, as demonstrated in these examples. If you keep all the statements and squiggly-brackets lined up, you are less likely to make syntax errors and more likely to find them if you do.

4.5 Nested conditionals

In addition to chaining, you can also nest one conditional within another. We could have written the previous example as:

There is now an outer conditional that contains two branches. The first branch contains a simple print statement, but the second branch contains another conditional statement, which has two branches of its own. Those two branches are both print statements, but they could have been conditional statements as well.

Indentation helps make the structure apparent, but nevertheless, nested conditionals get difficult to read very quickly. Avoid them when you can.

On the other hand, this kind of nested structure is common, and we will see it again, so you better get used to it.

4.6 The return statement

The return statement allows you to terminate the execution of a method before you reach the end. One reason to use it is if you detect an error condition:

This defines a method named printLogarithm that takes a double named x as a parameter. It checks whether x is less than or equal to zero, in which case it prints an error message and then uses return to exit the method. The flow of execution immediately returns to the caller and the remaining lines of the method are not executed.

I used a floating-point value on the right side of the condition because there is a floating-point variable on the left.

4.7 Type conversion

You might wonder how you can get away with an expression like "The log of x is " + result, since one of the operands is a String and the other is a double. In this case Java is being smart on our behalf, automatically converting the double to a String before it does the string concatenation.

Whenever you try to “add” two expressions, if one of them is a String, Java converts the other to a String and then perform string concatenation. What do you think happens if you perform an operation between an integer and a floating-point value?

4.8 Recursion

I mentioned in the last chapter that it is legal for one method to invoke another, and we have seen several examples. I neglected to mention that it is also legal for a method to invoke itself. It may not be obvious why that is a good thing, but it turns out to be one of the most magical and interesting things a program can do.

The name of the method is countdown and it takes a single integer as a parameter. If the parameter is zero, it prints the word “Blastoff.” Otherwise, it prints the number and then invokes a method named countdown—itself—passing n-1 as an argument.

The execution of countdown begins with n=3, and since n is not zero, it prints the value 3, and then invokes itself...

As a second example, let’s look again at the methods newLine and threeLine.

Although these work, they would not be much help if we wanted to print 2 newlines, or 106. A better alternative would be

This program similar to countdown; as long as n is greater than zero, it prints a newline and then invokes itself to print n-1 additional newlines. The total number of newlines that get printed is 1 +(n-1), which usually comes out to roughly n.

When a method invokes itself, that’s called recursion, and such methods are recursive.

4.9 Stack diagrams for recursive methods

In the previous chapter we used a stack diagram to represent the state of a program during a method invocation. The same kind of diagram can make it easier to interpret a recursive method.

Remember that every time a method gets called it creates a new frame that contains a new version of the method’s parameters and variables.

There is one frame for main and four frames for countdown, each with a different value for the parameter n. The bottom of the stack, countdown with n=0 is called the base case. It does not make a recursive call, so there are no more frames for countdown.

The frame for main is empty because main does not have any parameters or variables.

4.10 Glossary

4.11 Exercises

Exercise 1 Draw a stack diagram that shows the state of the program in Section 4.8 after main invokes nLines with the parameter n=4, just before the last invocation of nLines returns.

Exercise 2

This exercise reviews the flow of execution through a program with multiple methods. Read the following code and answer the questions below.

public class Buzz { public static void baffle(String blimp) { System.out.println(blimp); zippo("ping", -5); } public static void zippo(String quince, int flag) { if (flag < 0) { System.out.println(quince + " zoop"); } else { System.out.println("ik"); baffle(quince); System.out.println("boo-wa-ha-ha"); } } public static void main(String[] args) { zippo("rattle", 13); } }

Write the number 1 next to the first statement of this program that will be executed. Be careful to distinguish things that are statements from things that are not.
Write the number 2 next to the second statement, and so on until the end of the program. If a statement is executed more than once, it might end up with more than one number next to it.
What is the value of the parameter blimp when baffle gets invoked?
What is the output of this program?

Exercise 3

The first verse of the song “99 Bottles of Beer” is:

99 bottles of beer on the wall, 99 bottles of beer, ya’ take one down, ya’ pass it around, 98 bottles of beer on the wall.

Subsequent verses are identical except that the number of bottles gets smaller by one in each verse, until the last verse:

No bottles of beer on the wall, no bottles of beer, ya’ can’t take one down, ya’ can’t pass it around, ’cause there are no more bottles of beer on the wall!

And then the song(finally) ends.

Write a program that prints the entire lyrics of “99 Bottles of Beer.” Your program should include a recursive method that does the hard part, but you might want to write additional methods to separate the major functions of the program.

As you develop your code, test it with a small number of verses, like “3 Bottles of Beer.”

The purpose of this exercise is to take a problem and break it into smaller problems, and to solve the smaller problems by writing simple methods.

Exercise 4

What is the output of the following program?

public class Narf { public static void zoop(String fred, int bob) { System.out.println(fred); if (bob == 5) { ping("not "); } else { System.out.println("!"); } } public static void main(String[] args) { int bizz = 5; int buzz = 2; zoop("just for", bizz); clink(2*buzz); } public static void clink(int fork) { System.out.print("It's "); zoop("breakfast ", fork) ; } public static void ping(String strangStrung) { System.out.println("any " + strangStrung + "more "); } }

Exercise 5 Fermat’s Last Theorem says that there are no integers a, b, and c such that

aⁿ + bⁿ = cⁿ

except in the case when n=2.

Write a method named checkFermat that takes four integers as parameters—a, b, c and n—and that checks to see if Fermat’s theorem holds. If n is greater than 2 and it turns out to be true that aⁿ + bⁿ = cⁿ, the program should print “Holy smokes, Fermat was wrong!” Otherwise the program should print “No, that doesn’t work.”

You should assume that there is a method named raiseToPow that takes two integers as arguments and that raises the first argument to the power of the second. For example:

int x = raiseToPow(2, 3);

would assign the value 8 to x, because 2³ = 8.

Chapter 4 Conditionals and recursion

4.1 The modulus operator