Some of the methods we have used, like the `Math`

methods, return values. But all the methods we have *written* so far have been void; that is, they don't return values. In this chapter, we'll write methods that return values, which we call value methods.

## Return values

When you invoke a void method, the invocation is usually on a line all by itself. For example, here is the `countup`

method from Section 5.8:

```
public static void countup(int n) {
if (n == 0) {
System.out.println("Blastoff!");
} else {
countup(n - 1);
System.out.println(n);
}
}
```

And here is how it is invoked:

```
countup(3);
System.out.println("Have a nice day.");
```

On the other hand, when you invoke a value method, you have to do something with the return value. We usually assign it to a variable or use it as part of an expression, like this:

```
double error = Math.abs(expected - actual);
double height = radius \* Math.sin(angle);
```

Compared to void methods, value methods differ in two ways:

- They declare the type of the return value (the return type);
- They use at least one return statement to provide a return value.

Here's an example: `calculateArea`

takes a double as a parameter and returns the area of a circle with that radius:

```
public static double calculateArea(double radius) {
double result = Math.PI * radius * radius;
return result;
}
```

As usual, this method is public and static. But in the place where we are used to seeing void, we see double, which means that the return value from this method is a double.

The last line is a new form of the return statement that includes a return value. This statement means, "return immediately from this method and use the following expression as the return value." The expression you provide can be arbitrarily complex, so we could have written this method more concisely:

```
public static double calculateArea(double radius) {
return Math.PI * radius * radius;
}
```

On the other hand, temporary variables like `result`

often make debugging easier, especially when you are stepping through code using an interactive debugger (see Appendix A.6).

The type of the expression in the return statement must match the return type of the method. When you declare that the return type is double, you are making a promise that this method will eventually produce a double value. If you try to return with no expression, or an expression with the wrong type, the compiler will generate an error.

Sometimes it is useful to have multiple return statements, for example, one in each branch of a conditional:

```
public static double absoluteValue(double x) {
if (x < 0) {
return -x;
} else {
return x;
}
}
```

Since these return statements are in a conditional statement, only one will be executed. As soon as either of them executes, the method terminates without executing any more statements.

Code that appears after a return statement (in the same block), or any place else where it can never be executed, is called dead code. The compiler will give you an "unreachable statement" error if part of your code is dead. For example, this method contains dead code:

```
public static double absoluteValue(double x) {
if (x < 0) {
return -x;
} else {
return x;
}
System.out.println("This line is dead.");
}
```

If you put return statements inside a conditional statement, you have to make sure that *every possible path* through the program reaches a return statement. The compiler will let you know if that's not the case. For example, the following method is incomplete:

```
public static double absoluteValue(double x) {
if (x < 0) {
return -x;
} else if (x > 0) {
return x;
}
// syntax error
}
```

When `x`

is 0, neither condition is true, so the method ends without hitting a return statement. The error message in this case might be something like "missing return statement", which is confusing since there are already two of them. But hopefully you will know what it means.

## Writing methods

Beginners often make the mistake of writing a lot of code before they try to compile and run it. Then they spend way too much time debugging. A better approach is what we call incremental development. The key aspects of incremental development are:

- Start with a working program and make small, incremental changes. At any point, if there is an error, you will know where to look.
- Use variables to hold intermediate values so you can check them, either with print statements or by using a debugger.
- Once the program is working, you can consolidate multiple statements into compound expressions (but only if it does not make the program more difficult to read).

As an example, suppose you want to find the distance between two points, given by the coordinates (x1, y1) and (x2, y2). By the usual definition:

```
distance = √ (x2 − x1)^2 + (y2 − y1)^2
```

The first step is to consider what a `distance`

method should look like in Java. In other words, what are the inputs (parameters) and what is the output (return value)? In this case, the two points are the parameters, and it is natural to represent them using four double values. The return value is the distance, which should also have type double.

Already we can write an outline for the method, which is sometimes called a stub. The stub includes the method signature and a return statement:

```
public static double distance(double x1, double y1, double x2, double y2) {
return 0.0;
}
```

The return statement is a placeholder that is necessary for the program to compile. At this stage the program doesn't do anything useful, but it is good to compile it so we can find any syntax errors before we add more code.

It's usually a good idea to think about testing *before* you develop new methods; doing so can help you figure out how to implement them. To test the method, we can invoke it from `main`

using sample values:

```
double dist = distance(1.0, 2.0, 4.0, 6.0);
```

With these values, the horizontal distance is 3.0 and the vertical distance is 4.0. So the result should be 5.0, the hypotenuse of a 3-4-5 triangle. When you are testing a method, it is helpful to know the right answer.

Once we have compiled the stub, we can start adding lines of code one at a time. After each incremental change, we recompile and run the program. If there is an error at any point, we have a good idea where to look: the last line we added.

The next step is to find the differences `x2 − x1`

and `y2 − y1`

. We store those values in temporary variables named `dx`

and `dy`

.

```
public static double distance(double x1, double y1, double x2, double y2) {
double dx = x2 - x1;
double dy = y2 - y1;
System.out.println("dx is " + dx);
System.out.println("dy is " + dy);
return 0.0;
}
```

The print statements allows us to check the intermediate values before proceeding. They should be 3.0 and 4.0. We will remove the print statements when the method is finished. Code like that is called scaffolding, because it is helpful for building the program, but it is not part of the final product.

The next step is to square `dx`

and `dy`

. We could use the `Math.pow`

method, but it is simpler to multiply each term by itself.

```
public static double distance(double x1, double y1, double x2, double y2) {
double dx = x2 - x1;
double dy = y2 - y1;
double dsquared = dx * dx + dy * dy;
System.out.println("dsquared is " + dsquared);
return 0.0;
}
```

Again, you should compile and run the program at this stage and check the intermediate value, which should be 25.0. Finally, we can use `Math.sqrt`

to compute and return the result.

```
public static double distance(double x1, double y1, double x2, double y2) {
double dx = x2 - x1;
double dy = y2 - y1;
double dsquared = dx * dx + dy * dy;
double result = Math.sqrt(dsquared);
return result;
}
```

As you gain more experience programming, you might write and debug more than one line at a time. Nevertheless, incremental development can save you a lot of time.

## Method composition

Once you define a new method, you can use it as part of an expression, or build new methods using existing methods. For example, suppose someone gave you two points, the center of the circle and a point on the perimeter, and asked for the area of the circle. Let's say the center point is stored in the variables `xc`

and `yc`

, and the perimeter point is in `xp`

and `yp`

.

The first step is to find the radius of the circle, which is the distance between the two points. Fortunately, we have a method that does just that (`distance`

).

```
double radius = distance(xc, yc, xp, yp);
```

The second step is to find the area of a circle with that radius. We have a method for that computation too (`calculateArea`

).

```
double area = calculateArea(radius); return area;
```

Putting everything together in a new method, we get:

```
public static double circleArea(double xc, double yc, double xp, double yp) {
double radius = distance(xc, yc, xp, yp);
double area = calculateArea(radius);
return area;
}
```

The temporary variables `radius`

and `area`

are useful for development and debugging, but once the program is working we can make it more concise by composing the method calls:

```
public static double circleArea(double xc, double yc, double xp, double yp) {
return calculateArea(distance(xc, yc, xp, yp));
}
```

This example demonstrates a process called functional decomposition; that is, breaking a complex computation into simple methods, testing the methods in isolation, and then composing the methods to perform the computation. This process reduces debugging time and yields code that is more likely to be correct and easier to maintain.

## Overloading

You might have noticed that `circleArea`

and `calculateArea`

perform similar functions. They both find the area of a circle, but they take different parameters. For `calculateArea`

, we have to provide the radius; for `circleArea`

we provide two points.

If two methods do the same thing, it is natural to give them the same name. Having more than one method with the same name is called overloading, and it is legal in Java as long as each version takes different parameters. So we could rename `circleArea`

to `calculateArea`

:

```
public static double calculateArea(double xc, double yc, double xp, double yp) {
return calculateArea(distance(xc, yc, xp, yp));
}
```

Note that this new `calculateArea`

method is *not* recursive. When you invoke an overloaded method, Java knows which version you want by looking at the arguments that you provide. If you write:

```
double x = calculateArea(3.0);
```

Java looks for a method named `calculateArea`

that takes one double as an argument, and so it uses the first version, which interprets the argument as a radius. If you write:

```
double y = calculateArea(1.0, 2.0, 4.0, 6.0);
```

Java uses the second version of `calculateArea`

, which interprets the arguments as two points. In this example, the second version actually invokes the first version.

Many Java methods 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 data type. In the `Math`

class, there is a version of `abs`

that works on doubles, 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 accidentally invoking a different one.

## Boolean methods

Methods can return boolean values, just like any other type, which is often convenient for hiding tests inside methods. For example:

```
public static boolean isSingleDigit(int x) {
if (x > -10 && x < 10) {
return true;
} else {
return false;
}
}
```

The name of this method is `isSingleDigit`

. It is common to give boolean methods names that sound like yes/no questions. Since the return type is boolean, the return statement has to provide a boolean expression.

The code itself is straightforward, although it is longer than it needs to be. Remember that the expression `x > -10 && x < 10`

has type boolean, so there is nothing wrong with returning it directly (without the if statement):

```
public static boolean isSingleDigit(int x) {
return x > -10 && x < 10;
}
```

In `main`

, you can invoke the method in the usual ways:

```
System.out.println(isSingleDigit(2));
boolean bigFlag = !isSingleDigit(17);
```

The first line displays true because 2 is a single-digit number. The second line sets `bigFlag`

to true, because 17 is *not* a single-digit number.

Conditional statements often invoke boolean methods and use the result as the condition:

```
if (isSingleDigit(z)) {
System.out.println("z is small");
} else {
System.out.println("z is big");
}
```

Examples like this one almost read like English: "If is single digit z, print ... else print ...".

## Javadoc tags

In Section 4.9, we discussed how to write documentation comments using `/**`

. It's generally a good idea to document each class and method, so that other programmers can understand what they do without having to read the code.

To organize the documentation into sections, Javadoc supports optional tags that begin with the at sign (`@`

). For example, we can use `@param`

and `@return`

to provide additional information about parameters and return values.

```
/**
* Tests whether x is a single digit integer.
*
* @param x the integer to test
* @return true if x has one digit, false otherwise
*/
public static boolean isSingleDigit(int x) {
```

Figure 6.1 shows part of the resulting HTML page generated by Javadoc. Notice the relationship between the source code and the documentation.

Figure 6.1: HTML documentation for `isSingleDigit` . |

Methods with multiple parameters should have separate `@param`

tags that describe each one. Void methods should have no `@return`

tag, since they do not return a value.

## More recursion

Now that we have methods that return values, we have a Turing complete programming language. That means Java can compute anything computable, for any reasonable definition of "computable". This idea was developed by Alonzo Church and Alan Turing, so it is known as the Church-Turing thesis.

To give you an idea of what you can do with the tools we have learned, let's 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 refers to the thing being defined.

Of course, a truly circular definition is not very useful:

**recursive:** An adjective used to describe a method that is recursive.

If you saw that definition in the dictionary, you might be annoyed. But if you search for recursion on Google, it displays "Did you mean: recursion" as an inside joke.

Many mathematical functions are defined recursively, because that is often the simplest way. For example, the factorial of an integer n, which is written n!, is defined like this:

```
0! = 1
n! = n ·(n−1)!
```

Don't confuse the mathematical symbol !, which means *factorial* , with the Java operator `!`

, which means *not* . This definition says that `factorial(0)`

is `1`

, and that `factorial(n)`

is `n * factorial(n - 1)`

.

So `factorial(3)`

is `3 * factorial(2)`

; `factorial(2)`

is `2 * factorial(1)`

; `factorial(1)`

is `1 * factorial(0)`

; and `factorial(0)`

is `1`

. Putting it all together, we get `3 * 2 * 1 * 1`

, which is 6.

If you can formulate a recursive definition of something, you can easily write a Java method to evaluate it. The first step is to decide what the parameters and return type are. Since factorial is defined for integers, the method takes an int as a parameter and returns an int. So here's a good starting place:

```
public static int factorial(int n) {
return 0;
}
```

Next, we think about the base case. If the argument happens to be zero, we return 1.

```
public static int factorial(int n) {
if (n == 0) {
return 1;
}
return 0;
}
```

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.

```
public static int factorial(int n) {
if (n == 0) {
return 1;
}
int recurse = factorial(n - 1);
int result = n * recurse; return result;
}
```

The flow of execution for this program is similar to `countdown`

from Section 5.8. 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.
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 whatever invoked `factorial(3)`.
```

Figure [6.2] shows what the stack diagram looks like for this sequence of method invocations. The return values are shown being passed back up the stack. Notice that `recurse`

and `result`

do not exist in the last frame, because when `n == 0`

the code that declares them does not execute.

Figure 6.2: Stack diagram for the `factorial` method. |

## Leap of faith

Following the flow of execution is one way to read programs, but it can quickly become overwhelming. An alternative is 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 are already practicing a leap of faith when you use methods in the Java library. When you invoke `Math.cos`

or `System.out.println`

, you don't examine the implementations of those methods. You just assume that they work properly.

You should apply the same reasoning to your own methods. For example, in Section 6.5 we wrote a method called `isSingleDigit`

that determines whether a number is between 0 and 9. Once we convince ourselves that this method is correct -- by testing and examination of the code -- we can use the method without ever looking at the implementation again.

The same is true of recursive methods. When you get to the recursive call, instead of following the flow of execution you should *assume* that the recursive invocation works. For example, "Assuming that I can find the factorial of n−1, can I compute the factorial of n?" Yes you can, by multiplying by n.

Of course, it is strange to assume that the method works correctly when you have not finished writing it, but that's why it's called a leap of faith!

## One more example

Another common recursively-defined mathematical function is the Fibonacci sequence, which has the following definition:

```
fibonacci(1) = 1
fibonacci(2) = 1
fibonacci(n) = fibonacci(n−1) + fibonacci(n−2)
```

Translated into Java, this function is:

```
public static int fibonacci(int n) {
if (n == 1 || n == 2) {
return 1;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
```

If you try to follow the flow of execution here, even for small values of `n`

, your head will explode. But if we take a leap of faith and assume that the two recursive invocations work correctly, it is clear that their sum is the result.

## Vocabulary

**void method:**A method that does not return a value.**value method:**A method that returns a value.**return type:**The type of value a method returns.**return value:**The value provided as the result of a method invocation.**temporary variable:**A short-lived variable, often used for debugging.**dead code:**Part of a program that can never be executed, often because it appears after a return statement.**incremental development:**A process for creating programs by writing a few lines at a time, compiling, and testing.**stub:**A placeholder for an incomplete method so that the class will compile.**scaffolding:**Code that is used during program development but is not part of the final version.**functional decomposition:**A process for breaking down a complex computation into simple methods, then composing the methods to perform the computation.**overload:**To define more than one method with the same name but different parameters.**tag:**A label that begins with an at sign (`@`

) and is used by Javadoc to organize documentation into sections.**Turing complete:**A programming language that can implement any theoretically possible algorithm.**factorial:**The product of all the integers up to and including a given integer.**leap of faith:**A way to read recursive programs by assuming that the recursive call works, rather than following the flow of execution.

## Exercises

The code for this chapter is in the ch06 directory of ThinkJavaCode. See page ?? for instructions on how to download the repository. Before you start the exercises, we recommend that you compile and run the examples.

If you have not already read Appendix A.7, now might be a good time. It describes JUnit, a tool for efficiently testing value methods.

### Exercise 1

*If you have a question about whether something is legal, and what happens if it is not, a good way to find out is to ask the compiler. Answer the following questions by trying them out.*

*What happens if you invoke a value method and don't do anything with the result; that is, if you don't assign it to a variable or use it as part of a larger expression?**What happens if you use a void method as part of an expression? For example, try*`System.out.println(`

"boo!"`) + 7;`

### Exercise 2

*Write a method named isDivisible that takes two integers, n and m, and that returns true if n is divisible by m, and false otherwise.*

### Exercise 3

*If you are given three sticks, you may or may not be able to arrange them in a triangle. For example, if one of the sticks is 12 inches long and the other two are one inch long, you will not be able to get the short sticks to meet in the middle. For any three lengths, there is a simple test to see if it is possible to form a triangle:*

If any of the three lengths is greater than the sum of the other two, you cannot form a triangle.

*Write a method named isTriangle that takes three integers as arguments and returns either true or false, depending on whether you can or cannot form a triangle from sticks with the given lengths. The point of this exercise is to use conditional statements to write a value method.*

### Exercise 4

*Many computations can be expressed more concisely using the "multadd" operation, which takes three operands and computes a * b + c. Some processors even provide a hardware implementation of this operation for floating-point numbers.*

*Create a new program called Multadd.java.**Write a method called*`multadd`

that takes three`doubles`

as parameters and that returns`a * b + c`

.*Write a*`main`

method that tests`multadd`

by invoking it with a few simple parameters, like`1.0, 2.0, 3.0`

.*Also in*`main`

, use`multadd`

to compute the following values:

```
sin (π/4) + ( cos(π/4)/2 )
log10 + log20
```

*Write a method called*`expSum`

that takes a double as a parameter and that uses`multadd`

to calculate:

```
x * e^−x + | √ 1 − e^−x
```

*Hint: The method for raising* e*to a power is Math.exp.*

*In the last part of this exercise, you need to write a method that invokes another method you wrote. Whenever you do that, it is a good idea to test the first method carefully before working on the second. Otherwise, you might find yourself debugging two methods at the same time, which can be difficult.*

*One of the purposes of this exercise is to practice pattern-matching: the ability to recognize a specific problem as an instance of a general category of problems.*

### Exercise 5

*What is the output of the following program?*

```
public static void main(String[] args) {
boolean flag1 = isHoopy(202);
boolean flag2 = isFrabjuous(202);
System.out.println(flag1);
System.out.println(flag2);
if (flag1 && flag2) {
System.out.println("ping!");
}
if (flag1 || flag2) {
System.out.println("pong!");
}
}
```

```
public static boolean isHoopy(int x) {
boolean hoopyFlag;
if (x % 2 == 0) {
hoopyFlag = true;
} else {
hoopyFlag = false;
}
return hoopyFlag;
}
```

```
public static boolean isFrabjuous(int x) {
boolean frabjuousFlag;
if (x > 0) {
frabjuousFlag = true;
} else {
frabjuousFlag = false;
}
return frabjuousFlag;
}
```

*The purpose of this exercise is to make sure you understand logical operators and the flow of execution through value methods.*

### Exercise 6

*In this exercise, you will use a stack diagram to understand the execution of the following recursive program.*

```
public static void main(String[] args) {
System.out.println(prod(1, 4));
}
public static int prod(int m, int n) {
if (m == n) {
return n;
} else {
int recurse = prod(m, n - 1);
int result = n * recurse;
return result;
}
}
```

*Draw a stack diagram showing the state of the program just before the last invocation of*`prod`

completes.*What is the output of this program? (Try to answer this question on paper first, then run the code to check your answer.)**Explain in a few words what*`prod`

does (without getting into the details of how it works).*Rewrite*`prod`

without the temporary variables`recurse`

and`result`

. Hint: You only need one line for the`else`

branch.

### Exercise 7

*Write a recursive method named oddSum that takes a positive odd integer n and returns the sum of odd integers from 1 to n. Start with a base case, and use temporary variables to debug your solution. You might find it helpful to print the value of n each time oddSum is invoked.*

### Exercise 8

*The goal of this exercise is to translate a recursive definition into a Java method. The Ackermann function is defined for non-negative integers as follows:*

```
A(m, n)
n+1 if m = 0
A(m−1, 1) if m > 0 and n = 0
A(m−1, A(m, n−1)) if m > 0 and n > 0
```

*Write a method called ack that takes two ints as parameters and that computes and returns the value of the Ackermann function.*

*Test your implementation of Ackermann by invoking it from main and displaying the return value. Note the return value gets very big very quickly. You should try it only for small values of* m

*and*n*(not bigger than 3).*

### Exercise 9

*Write a recursive method called power that takes a double x and an integer n and returns x^n.*

*Hint: A recursive definition of this operation is x^n = x * x^n−1. Also, remember that anything raised to the zeroth power is 1.*

Optional challenge: you can make this method more efficient, when `n`

is even, using `x^n = ( x^n/2 )^2`