# Value methods¶

## Return values¶

Some of the methods we have used, like the Math functions, produce 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:

```
double e = Math.exp(1.0);
double height = radius * Math.sin(angle);
```

But so far all our methods have been **void**; that is, methods that
return no value. When you invoke a void method, it is typically on a
line by itself, with no assignment:

```
countdown(3);
nLines(3);
```

In this chapter we write methods that return things, which I call
**value** methods. The first example is `area`, which takes a
`double` as a parameter, and returns the area of a circle with the
given radius:

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

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 means
that the return value from this method is a `double`. I still haven’t
explained what `public static` means, but be patient.

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 complicated, so we could have written
this method more concisely:

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

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 `double`.
If you try to `return` with no expression, or an expression with the
wrong type, the compiler will take you to task.

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

1 2 3 4 5 6 7 | ```
public static double absoluteValue(double x) {
if (x < 0) {
return -x;
} else {
return x;
}
}
``` |

Since these return statements are in an alternative conditional, only one will be executed. Although it is legal to have more than one return statement in a method, you should keep in mind that as soon as one is executed, the method terminates without executing any subsequent statements.

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.

If you put return statements inside a conditional, then you have to
guarantee that *every possible path* through the program hits a return
statement. For example:

1 2 3 4 5 6 7 | ```
public static double absoluteValue(double x) {
if (x < 0) {
return -x;
} else if (x > 0) {
return x;
} // WRONG!!
}
``` |

This program is not legal because if `x` is 0, neither condition is
true and the method ends without hitting a return statement. A typical
compiler message would be “return statement required in absoluteValue,”
which is a confusing message since there are already two of them.

## Program development¶

At this point you should be able to look at complete Java methods and
tell what they do. But it may not be clear yet how to go about writing
them. I am going to suggest a method called **incremental development**.

As an example, imagine you want to find the distance between two points, given by the coordinates \((x_1, y_1)\) and \((x_2, y_2)\). By the usual definition,

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`s, although we will see later that
there is a `Point` object in Java that we could use. The return value
is the distance, which will have type `double`.

Already we can write an outline of the method:

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

The statement `return 0.0;` is a place-keeper that is necessary to
compile the program. Obviously, at this stage the program doesn’t do
anything useful, but it is worthwhile to try compiling it so we can
identify any syntax errors before we add more code.

To test the new method, we have to invoke it with sample values.
Somewhere in `main` I would add:

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

I chose these values so that the horizontal distance is 3 and the vertical distance is 4; that way, the result will be 5 (the hypotenuse of a 3-4-5 triangle). When you are testing a method, it is useful to know the right answer.

Once we have checked the syntax of the method definition, 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: in the last line we added.

The next step is to find the differences \(x_2 - x_1\) and
\(y_2 - y_1\). I store those values in temporary variables named
`dx` and `dy`.

1 2 3 4 5 6 7 8 | ```
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;
}
``` |

I added print statements so we can check the intermediate values before proceeding. They should be 3.0 and 4.0.

When the method is finished I remove the print statements. 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.

1 2 3 4 5 6 7 8 | ```
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, I would 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.

1 2 3 4 5 6 7 8 | ```
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;
}
``` |

In `main`, we can print and check the value of the 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. The key aspects of the process are:

- Start with a working program and make small, incremental changes. At any point, if there is an error, you will know exactly where it is.
- Use temporary variables to hold intermediate values so you can print and check them.
- Once the program is working, you can remove scaffolding and consolidate multiple statements into compound expressions, but only if it does not make the program difficult to read.

## Composition¶

Once you define a new method, you can use it as part of an expression, and you can build new methods using existing methods. For example, what if 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, `distance` that does that.

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

The second step is to find the area of a circle with that radius, and return it.

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

Wrapping that all up in a method, we get:

```
public static double circleArea
(double xc, double yc, double xp, double yp) {
double radius = distance(xc, yc, xp, yp);
double area = area(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 invocations:

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

## Overloading¶

You might have noticed that `circleArea` and `area` perform similar
functions—finding the area of a circle—but take different parameters.
For `area`, 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, which is called
**overloading**, is legal in Java *as long as each version takes
different parameters*. So we could rename `circleArea`:

```
public static double area
(double x1, double y1, double x2, double y2) {
return area(distance(xc, yc, xp, yp));
}
```

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 = area(3.0);
```

Java goes looking for a method named `area` 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 x = area(1.0, 2.0, 4.0, 6.0);
```

Java uses the second version of `area`. And notice that the second
version of `area` actually invokes the first.

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 type. In the Math class, there is a version of
`abs` that works on `double`s, and there is also a version for
`int`s.

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.

And 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 day 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 you are not running the version of the program you
think you are. To check, add a `print` statement (it doesn’t matter
what you print) and make sure the behavior of the program changes
accordingly.

## Boolean expressions¶

Most of the operations we have seen produce results that are the same
type as their operands. For example, the `+` operator takes two
`int`s and produces an `int`, or two `double`s and produces a
`double`, etc.

The exceptions we have seen are the **relational operators**, which
compare `int`s and `float`s 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
`int`s, `double`s and `String`s, those sets are pretty big.
For `boolean`s, there are only two values.

Boolean expressions and variables work just like other types of expressions and variables:

```
boolean flag;
flag = true;
boolean testResult = false;
```

The first example is a simple variable declaration; the second example is an assignment, and the third example is an initialization.

The values `true` and `false` are keywords in Java, so they may
appear in a different color, depending on your development environment.

The result of a conditional operator is a boolean, so you can store the result of a comparison in a variable:

```
boolean evenFlag = (n%2 == 0); // true if n is even
boolean positiveFlag = (x > 0); // true if x is positive
```

and then use it as part of a conditional statement later:

```
if (evenFlag) {
System.out.println("n was even when I checked it");
}
```

A variable used in this way is called a **flag** because it flags the
presence or absence of some condition.

## Logical operators¶

There are three **logical operators** in Java: AND, OR and NOT, which
are denoted by the symbols `&&`, `||` and `!`. The semantics of
these operators is similar to their meaning in English. For example
`x > 0 && x < 10` is true only if `x` is greater than zero AND less
than 10.

`evenFlag || n%3 == 0` is true if *either* of the conditions is true,
that is, if `evenFlag` is true OR the number is divisible by 3.

Finally, the NOT operator inverts a boolean expression, so `!evenFlag`
is true if `evenFlag` is false—if the number is odd.

Logical operators can simplify nested conditional statements. For example, can you re-write this code using a single conditional?

```
if (x > 0) {
if (x < 10) {
System.out.println("x is a positive single digit.");
}
}
```

## Boolean methods¶

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

1 2 3 4 5 6 7 | ```
public static boolean isSingleDigit(int x) {
if (x >= 0 && 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. 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 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:

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

In `main` you can invoke this method in the usual ways:

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

The first line sets `bigFlag` to `true` only if 17 is *not* a
single-digit number. The second line prints `true` because 2 is a
single-digit number.

The most common use of boolean methods is inside conditional statements

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

## More recursion¶

Now that we have methods that return values, we have a **Turing
complete** programming language, which means that we 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. You can read more about it at
Wikipedia.

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 contains a reference to the thing being defined. 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. 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 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 \(0!\). 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 method to evaluate it. The first step is to decide what the parameters are and what the return type is. Since factorial is defined for integers, the method takes an integer as a parameter and returns an integer:

```
public static int factorial(int n) {
}
```

If the argument happens to be zero, return 1:

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

That’s the base case.

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\).

1 2 3 4 5 6 7 8 9 | ```
public static int factorial(int n) {
if (n == 0) {
return 1;
} else {
int recurse = factorial(n-1);
int result = n * recurse;
return result;
}
}
``` |

The flow of execution for this program is similar to `countdown` from
Section *Recursion*. 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 0iszero, we take the first branch and return the value 1 immediately without making any more recursive invocations.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)`.

Here is 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 in the last frame `recurse` and `result` do not exist
because when `n=0` the branch that creates them does not execute.

## Leap of faith¶

Following the flow of execution is one way to read programs, but it can
quickly become disorienting. 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 are already practicing this leap of faith when you use Java
methods. When you invoke `Math.cos` or `System.out.println`, you
don’t examine the implementations of those methods. You just assume that
they work.

You can apply the same logic to your own methods. For example, in
Section *Boolean methods* 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 code again.

The same is 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, and then ask yourself,
“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 even finished writing it, but that’s why it’s called a leap of faith!

## One more example¶

The second most common example of a recursively-defined mathematical
function is `fibonacci`, which has the following definition:

Translated into Java, this is

1 2 3 4 5 6 7 | ```
public static int fibonacci(int n) {
if (n == 0 || n == 1) {
return 1;
} else {
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 explodes. But according to the leap of faith, if we
assume that the two recursive invocations work correctly, then it is
clear that we get the right result by adding them together.

## Glossary¶

- return type:
- The part of a method declaration that indicates what type of value the method returns.
- return value:
- The value provided as the result of a method invocation.
- dead code:
- Part of a program that can never be executed, often because it
appears after a
`return`statement. - scaffolding:
- Code that is used during program development but is not part of the final version.
- void:
- A special return type that indicates a void method; that is, one that does not return a value.
- overloading:
- Having more than one method with the same name but different parameters. When you invoke an overloaded method, Java knows which version to use by looking at the arguments you provide.
- boolean:
- A type of variable that can contain only the two values
`true`and`false`. - flag:
- A variable (usually
`boolean`) that records a condition or status information. - conditional operator:
- An operator that compares two values and produces a boolean that indicates the relationship between the operands.
- logical operator:
- An operator that combines boolean values and produces boolean values.

## Exercises¶

### Exercise¶

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¶

Many computations can be expressed 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 their multadditionization.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 \frac{\pi}{4} + \frac{\cos \frac{\pi}{4}}{2}\]and

\[\log 10 + \log 20\]Write a method called

`yikes`that takes a double as a parameter and that uses`multadd`to calculate\[x e^{-x} + \sqrt{1 - e^{-x}}\]HINT: the Math method for raising \(e\) to a power is

`Math.exp`.

In the last part, you get a chance to write a method that invokes a method you wrote. Whenever you do that, it is a good idea to test the first method carefully before you start 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¶

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, then you cannot form a triangle. Otherwise, you can.”

Write a method named `isTriangle` that it takes three integers as
arguments, and that 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¶

What is the output of the following program? The purpose of this exercise is to make sure you understand logical operators and the flow of execution through value methods.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | ```
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;
}
``` |

### Exercise¶

The distance between two points \((x_1, y_1)\) and \((x_2, y_2)\) is

Write a method named `distance` that takes four doubles as
parameters—`x1`, `y1`, `x2` and `y2`—and that prints the
distance between the points.

You should assume that there is a method named `sumSquares` that
calculates and returns the sum of the squares of its arguments. For
example:

```
double x = sumSquares(3.0, 4.0);
```

would assign the value `25.0` to `x`.

The point of this exercise is to write a new method that uses an
existing one. You should write only one method: `distance`. You should
not write `sumSquares` or `main` and you should not invoke
`distance`.

### Exercise¶

The point of this exercise is to use a stack diagram to understand the execution of a recursive program.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | ```
public class Prod {
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 instance of
`prod`completes. What is the output of this program? - Explain in a few words what
`prod`does. - Rewrite
`prod`without using the temporary variables`recurse`and`result`.

### Exercise¶

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

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

Write a method called `ack` that takes two `int`s as parameters
and that computes and returns the value of the Ackerman function.

Test your implementation of Ackerman by invoking it from `main` and
printing the return value.

WARNING: the return value gets very big very quickly. You should try it only for small values of \(m\) and \(n\) (not bigger than 2).

### Exercise¶

Create a program called

`Recurse.java`and type in the following methods:1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

// first: returns the first character of the given String public static char first(String s) { return s.charAt(0); } // last: returns a new String that contains all but the // first letter of the given String public static String rest(String s) { return s.substring(1, s.length()); } // length: returns the length of the given String public static int length(String s) { return s.length(); }

Write some code in

`main`that tests each of these methods. Make sure they work, and make sure you understand what they do.Write a method called

`printString`that takes a String as a parameter and that prints the letters of the String, one on each line. It should be a`void`method.Write a method called

`printBackward`that does the same thing as`printString`but that prints the String backward (one character per line).Write a method called

`reverseString`that takes a String as a parameter and that returns a new String as a return value. The new String should contain the same letters as the parameter, but in reverse order. For example, the output of the following codeString backwards = reverseString("Allen Downey"); System.out.println(backwards);

should be

yenwoD nellA

### Exercise¶

Write a recursive method called `power` that takes a double `x` and
an integer `n` and that returns \(x^n\).

Hint: a recursive definition of this operation is \(x^n = x \cdot x^{n-1}\). Also, remember that anything raised to the zeroeth power is 1.

Optional challenge: you can make this method more efficient, when `n`
is even, using \(x^n = \left( x^{n/2} \right)^2\).

### Exercise¶

(This exercise is based on page 44 of Ableson and Sussman’s *Structure
and Interpretation of Computer Programs*.)

The following technique is known as Euclid’s Algorithm because it
appears in Euclid’s *Elements* (Book 7, ca. 300 BC). It may be the
oldest nontrivial algorithm [1].

The process is based on the observation that, if \(r\) is the remainder when \(a\) is divided by \(b\), then the common divisors of \(a\) and \(b\) are the same as the common divisors of \(b\) and \(r\). Thus we can use the equation

to successively reduce the problem of computing a GCD to the problem of computing the GCD of smaller and smaller pairs of integers. For example,

implies that the GCD of 36 and 20 is 4. It can be shown that for any two starting numbers, this repeated reduction eventually produces a pair where the second number is 0. Then the GCD is the other number in the pair.

Write a method called `gcd` that takes two integer parameters and that
uses Euclid’s algorithm to compute and return the greatest common
divisor of the two numbers.

[1] | For a definition of “algorithm”, jump ahead to
Section Algorithms. |