5. Fruitful functions

5.1. Return values

Some of the built-in functions we have used, like the math functions, have produced results. That is, the effect of calling the function is to generate a new value, which we usually assign to a variable or use as part of an expression. For example:

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

But so far all the functions we have written have been void functions; that is, functions that do not return a value. When you call a void function, it is typically on a line by itself, with no assignment:

n_lines(3);
countdown(n-1);

In this chapter we are going to write functions that return things, which we will refer to as fruitful functions. The first example is area, which has a double parameter, radius, and which returns the area of a circle with the given radius:

double area(double radius) {
    double pi = acos(-1.0);
    double area = pi * radius * radius;
    return area;
}

The first thing you should notice is that the beginning of the function definition is different. Instead of void, which indicates a void function, we see double, which indicates that the return value from this function will have type double.

Also notice that the last line is an alternative form of the return statement that includes a return value. The statement means, “return immediately from this function and send the value of the following expression to the caller.” The expression you provide can be arbitrarily complicated, so we could have written this function more concisely:

double area(double radius) {
    return acos(-1.0) * radius * radius;
}

On the other hand, temporary variables like pi and area often make your program easier to read and debug. In either case, the type of the expression in the return statement must match the return type of the function. In other words, when you declare that the return type is double, you are making a promise that this function 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:

double absolute_value(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 function, you should keep in mind that as soon as one is executed the function 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:

double absolute_value(double x) {
    if (x < 0) {
        return -x;
    } else if (x > 0) {
        return x;
    }
}                     // WRONG!!

The program is not correct because if x happens to be 0, the neither condition will be true and the function will end without hitting a return statement. Unfortunately, many C++ compilers do not catch this error. As a result, the program may compile and run, but the return value when x is 0 could be anything, and will probably be different in different environments.

By now you are probably sick of seeing compiler errors, but as you gain more experience, you will realize that the only thing worse than getting a compiler error is not getting a compiler error when your program is wrong.

Here’s the kind of thing that’s likely to happen: you test absolute_value with several values of x and it seems to work correctly. Then you give your program to someone else and they run it in another environment. It fails in some mysterious way, and it takes days of debugging to discover that the problem is an incorrect implementation of absolute_value. If only the compiler had warned you!

From now on, if the compiler points out an error in your program, you should not blame the compiler. Rather, you should thank the compiler for finding your error and sparing you days of debugging. Some compilers have an option that tells them to be extra strict and report all the errors they can find. You should turn this option on all the time.

As an aside, you know that there is a function in the math library called fabs that calculates the absolute value of a double correctly.

5.2. Program development

At this point you should be able to look at complete C++ functions and tell what they do. But it may not be clear yet how to go about writing them. We are going to suggest on technique 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,

\[distance = \sqrt{(x_2 - x_1)^2 + (y_2 - y_1)^2}\]

The first step is to consider what a distance function should look like in C++. In other word, 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 doubles. The return value is the distance, which will also have type double.

Already we can write an outline of the function:

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

The return statement is a placekeeper so that the function will compile and return somthing, even though it is not the right answer. At this stage the function doesn’t do anything useful, but it is worthwhile to try compiling it so we can identify any syntax errors before we make it more complicated.

Somewhere in main we should add:

double dist = distance(1.0, 2.0, 4.0, 6.0);
cout << "dist is: " << dist << endl;

We 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 function, it is useful to know the right answer.

Once we have checked the syntax of the function definition, we can start adding lines of code, a little at a time. After each incremental change, we recompile and run the program. That way, at any point we know exactly where a new error must be - in the last changes we made to the program.

The next step in the computation is to find the differences \(x_2 - x_1\) and \(y_2 - y_1\). We will store these value in temporary variables named dx and dy.

double distance(double x1, double y1, double x2, double y2) {
    double dx = x2 - x1;
    double dy = y2 - y1;
    cout << "dx is " << dx << endl;
    cout << "dy is " << dy << endl;
    return 0.0;
}

We added output statements that will let us check the intermediate values before proceeding. As mentioned, we already know that they should be 3.0 and 4.0.

When the function is finished we will remove these output statements. Code like this is called scaffolding, because it is helpful in building the program, but it is 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 next step in the development is to square dx and dy. We could use the pow function, but it is simpler and faster to just multiply each term by itself.

double distance(double x1, double y1, double x2, double y2) {
    double dx = x2 - x1;
    double dy = y2 - y1;
    double dsquared = dx * dx + dy * dy;
    cout << "dsquared is " << dsquared << endl;
    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 the sqrt function to compute and return the result (remember to include the cmath library).

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 = sqrt(dsquared);
    return result;
}

Then in main, we should output and check the value of the result.

As you gain more experience programming, you might find yourself writing and debugging more than one line at a time. Nevertheless, this incremental development process can save yiou a lot of debugging 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 output and check them.

• Once the program is working, you might want to remove some of the scaffolding or consolidate multiple statements into compound expressions, but only if it does not make the program difficult to read.

5.3. Composition

As you should expect by now, once you define a new function, ou can use it as part of an expression, and you can build new functions using existing functions. For example, what if someone gave you two points, the center of a circle and a point on its 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 permimeter 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 function, distance, that does that. we have a function, distance, that does that. we have a function, distance, that does that. we have a function, distance, that does that.

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

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

double result = area(radius);
return result;

Wrapping that all up in a function, we get:

double anna(double xc, double yc, double xp, double yp) {
    double radius = distance(xc, yc, xp, yp);
    double result = area(radius);
    return result;
}

5.4. Overloading

In the previous section you might have noticed that anna and area perform similar functions - finding the area of a circle - but have different paramenters.

For area, we have to provide the radius; for anna we provide two points.

If two functions do the same thing, it is natural to give them the same name. In other words, it would make more sense if anna were called area.

Having more than one function with the same name, which is called overloading, is legal in C++ as long as each version has different parameters. So we can go ahead and rename anna:

double area(double xc, double yc, double xp, double yp) {
    return area(distance(xc, yc, xp, yp));
}

This looks like a recursive function, but it is not. Actually, this version of area is calling the other version. When you call an overloaded function, C++ knows which version you want by looking at the number and types of the arguments that you provide. The number of types of the parameters of a function in C++ is called the function’s signature. For example, if you write:

double x = area(3.0);

C++ looks for a function named area with a single double as a parameter, so it will use the first version. If you write:

double x = area(1.0, 2.0, 4.0, 6.0);

C++ will match this function call with the signature of the second version, and call the appropriate version.

Many of the built-in C++ commands are overloaded, meaning that there are different versions that have different numbers and types of paramenters.

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 function while accidently calling a different one.

Actually, this is a good time to mention 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 an output statement (it doesn’t matter what it says) and make sure the behavior of the program changes accordingly.

5.5. Boolean values

The types we have seen so far are pretty big. There are a lot of integers and floating-point numbers. By comparision, the set of characters is pretty small. Well there is another type in C++ that is even smaller. The boolean data type has only two values, true and false.

Without thinking about it, we have been using boolean values for the last few chapters. The condition inside an if statement or a while statement is a boolean expression. Also, the result of a comparision operator is a boolean value. For example:

if (x == 5) {
    // do something
}

The operator == compares two integers and produces a boolean value.

The values true and false are keywords in C++, and can be used anywhere a boolean expression is called for. For example,

while (true) {
    // loop forever
}

is a standard idiom for a loop that should run forever (or until it reaches a return or break statement).

5.6. Boolean variables

As usual, for every type of value, there is a corresponding type of variable. In C++ the boolean type is called bool. Boolean variables work just like the other types:

bool george;
george = true;
bool test_result = false;

The first line is a simple variable declaration; the second line is an assignment, and the third line is a combination of a declaration and an assignment, called an initialization.

As we mentioned, the result of a comparision operator is a boolean, so you can store it in a bool variable

bool even_flag = (n%2 == 0);     // true if n is even
bool positive_flag = (n > 0);    // true if n is positive

and then use it as part of a conditional statement later

if (even_flag) {
    cout << "n was even when I checked it" << endl;
}

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

5.7. Logical operators

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

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

Finally, the NOT operator has the effect of negating or inverting a boolean expression, so !even_flag is true if even_flag is false, that is, if the number is odd.

Logical operators often provide a way to simplify nested conditional statements. For example, the following nested if statements could be written as a single conditional:

if (age > 16) {
    if (age < 65) {
        cout << "age is within the normal working age." << endl;
    }
}

It will be left as an exercise for you to do this.

5.8. Boolean functions

Functions can return bool values just like any other type. These functions are not surprisingly refered to as boolean functions, and they are often useful for hiding complicated tests inside functions. For example:

bool is_single_digit(int d)
{
    if (d >= 0 && d < 10) {
        return true;
    } else {
        return false;
    }
}

The name of this function is is_single_digit. It is common to give boolean functions names that sound like yes/no questions. The return type is bool, 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 d >= 0 && d < 10 has type bool, so there is nothing wrong with returning it directly, and avoiding the if statement altogether:

bool is_single_digit(int d)
{
    return (d >= 0 && d < 10);
}

In main you can call this function in the usual ways:

cout << is_single_digit(2) << endl;
bool bigFlag = !is_single_digit(17);

The first line outputs the value true because 2 is a single-digit number. Unfortunately, when C++ outputs bools, it does not display the words true and false, but rather the integers 1 and 0 (there is a way to that using the boolalpha flag, if you’re interested, but we won’t do that here). The second line assigns the value true to bigFlag only if 17 is not a single digit number.

The most common use of boolean functions is inside conditional statements:

if (is_single_digit(n)) {
    cout << "n is little" << endl;
} else {
    cout << "n is big" << endl;
}

5.9. Returning from main

Now that we have functions that return values, we can let you in on a secret. We have been returning 0 from our main function since our first C++ program. The reason is that 0 indicates that our program successfully finished whatever it was supposed to do. If something goes wrong, it is common to return a -1, or some other value that indicates what kind of error occured.

Of course, you might wonder who this value is returned to, since we never call main ourselves. It turns out that when the operating system executes a program, it starts by calling main in pretty much the same way it calls all the other functions.

There are even some parameters that are passed to main by the system, but we are not going to deal with them yet.

5.10. More recursion

So far we have only learned a small subset of C++, but you might be interested to know that this subset is now a complete programming language, by which we 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 this claim is a non-trivial exercise first accomplished by Alan Turing, one of the first computer scientists (well, some would argue that he was a mathematician, but a lot of early computer scientists started as mathematians). 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, we’ll evaluate a few 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:

fabjuous: an adjective used to describe something that is frabjuous.

If you saw that definition in the dictionary, you’d be justified in being annoyed. On the other hand, if you look up the definition fo the mathematical function factorial, you will get something like:

\[\begin{split}0! &= 1\\ n! &= n\cdot(n-1)!\end{split}\]

(Factorial is usually denoted with the symbol !, which is not to be confused with the C++ 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 C++ program to evaluate it. The first step is to decide what the parameters are for the function, and what the return type is. With a little thought, you should conclude that factorial takes an integer as an argument and returns an integer:

int factorial(int n)
{
}

If the argument happens to be zero, all we have to do is return 1:

int factorial(int n)
{
    if (n == 0) {
        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.

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

If we look at the flow of execution for this program, it is similar to n_lines from the previous chapter. If we call factorial with 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, 1, is returned.

The return value (1) gets multiplied by n, which is 2, and the result, 2, is returned.

The return value (2) gets multiplied by n, which is 3, and the result, 6, is returned to main, or whoever called factorial(3).

Here is what the stack diagram looks like for this sequence of function calls:

The return values are shown being passed back up the stack.

Notice that in the last instance of factorial, the local variables recurse and result do not exist because when n=0 the branch that creates them does not execute.

5.11. Leap of faith

Following the flow of execution is one way to read programs, but as you saw in the prevous section, it can quickly become labarynthine. An alternative is what we call the “leap of faith.” When you come to a function call, instead of following the flow of execution, you assume that the function works correctly and returns the appropriate value.

In fact, you are already practicing this leap of faith when you use built-in functions. When you call cos or exp, you don’t examine the implementations of those functions. You just assume that they work, because the people who wrote the built-in libraries were good programmers.

Well, the same is true when you call one of your own functions. For example, in Boolean functions we wrote a function called is_single_digit that determines whether a number is between 0 and 9. Once we have convinced ourselves that the function is correct - by testing and examination of the code - we can use the function without ever looking at the code again.

The same is true of recursive programs. When you get to the recursive call, instead of following the flow of execution, you should assume that the recursive call 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 function works correctly when you have not even finished writing it, but that’s why it’s called a leap of faith!

5.12. One more example

In the previous example we used temporary variables to spell out the steps, and to make the code easier to debug, but we could have saved a few lines:

int factorial(int n)
{
    if (n == 0) {
        return 1;
    } else {
        return n * factorial(n-1);
    }
}

From now on we will tend to use the more concise version, but we recommend that you use the more explicit version while you are developing the code. When you have it working, you can tighten it up, if you are feeling inspired.

After factorial, the classic example of a recursely-defined mathematical function is the one that generates number in the fibonacci sequence, which has the following definition:

\[\begin{split}fibonacci(0) &= 1\\ fibonacci(1) &= 1\\ fibonacci(n) &= fibonacci(n-1) + fibonacci(n-2)\end{split}\]

Translated into C++, this is

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

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.

5.13. Glossary

dead code

Part of a program that can never be executed, often because it appears after a return statement.

function signature

The function name together with the number and types of parameters. The signature determines which overloaded function is called.

overloading

Having more than one function with the same name but different parameter types. When you call an overloaded function, C++ knows which version to use by looking at the types of the arguments you provide.

return type

The type a value a function sends back to the caller (returns).

return value

The value sent to the caller of a function (returned by the function).

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 function; that is, one that does not return a value.

5.14. Exercises

• Chapter 5 Exercise Set 1