C++ Functions and Function Templates

Carlos Moreno

Copyright © 2000 – 2024 Carlos Moreno
and Mochima Software/AudioSystems

Introduction – The Bad News

Let's face it: Programming, the way we have seen it so far, truly sucks! Programs are horrible, messy, complicated, unreadable — the list goes on and on (so, good news — you thought it was you that were doing something wrong!).^[1]

And that's the really simple little programs that serve almost nothing other than learning purposes. Extrapolate that to, say, an application that generates computer-animated 3D graphics. The outcome may be nice and colourful and flashy — but the program behind would be profoundly horrible!

Let's see; as an example, we have to write a program that implements a simplified version of the minesweeper game — a text-based version running on a console. The program sets up a two-dimensional array representing the board (say, a 10 by 10 array), fills it with mines at random positions (say, 10 mines), and then keeps prompting the user for positions where to try. For each position entered, the program checks if there is a mine — if there is, then game over. If not, then the program counts mines in the eight surrounding positions and writes the number in the given cell. The game continues, prompting the user for a new position.

The following is a sketch of the pseudo-code for what has to be done:

Easy enough! (right?). Well, that's the reason why we start by writing pseudo-code; it's easy to understand and easy to get it right (and no, I'm not referring to the fact that we do not have a real compiler and a real computer pointing out how we got it wrong — they're so pedantic!).

Now, we'd like to zoom in a little bit to get some more details about what needs to be done. We would have to define what we meant (what has to be done) by “fill board with 10 mines” and “count mines around the given position”. Let's sketch the pseudo-code for those:

Again, easy enough (right?). Well, just one more detail that we'd have to define — what do we mean by “position is within the board”. We would again sketch the pseudo-code of what that means:

Easy enough when we look at each little piece independently, right? Now, you have to start plugging in every piece in its place; not only that: we need to write the actual code, which by nature is much longer and with a much larger amount of details, little variables here and there, etc. And that's when we start getting again the feeling that programming sucks.

Notice that in addition to the obvious (the obvious being that the program gets longer and messy when we put all of the above together), there's some rather subtle reasons for the trouble that we typically get in: when we look at the pieces independently, each of the pieces is perfectly well defined, independently of anything else. However, when we put things together, unwanted interactions between the various pieces may lead to headaches; for instance, we have many for loops in here, many positions (row and column representing a cell in the board) throughout the various parts of the program — what if we confuse one loop's control variable with that of another loop? (Granted, with C++ restricted scope to the for loop, we can make this problem virtually inexistent; but still, the point remains valid). What if we confuse one variable row (perhaps representing a surrounding position) with another (the cell given by the user)?

There's another not-so-subtle detail. In two different parts of the program we have to check if a given position is within the board — in one case because we need to validate the user input, and in the other case because if the user input is on an edge of the board, then some of the surrounding positions would fall outside the board, and so we do not want to consider them when counting mines around the given position. Tough luck: you have to repeat that if-else, plugging in the appropriate variables (row, column) for each situation. This also has the unwanted side-effect of increasing the risk of introducing errors (bugs) in the program.

In the pseudo-code, we can get away with describing that action only once and referring to it from the two places because it is pseudo-code. Strange, however, that if we can understand the above in an unambiguous manner, why wouldn't a computer (a C++ compiler) be able to? By this, I mean: if we write “if XX position is within the board” and then define what we mean by “position is within the board”, there is no doubt about what the pseudo-code does. (This is the part where I'm lazy and I resort to I will leave the actual writing of the pseudo-code as an exercise for the reader.)

The Good News

As I am sure you are suspecting, the good news is: yes, of course a compiler can understand in an unambiguous matter a situation like the above. In other words, yes, we do have the tools that, among other things, allow us to organize our code and make it look, to a certain degree, like pseudo-code — at least in the sense of being brief, clear, and readable (readable being defined as easy to understand, with the immediate and obvious consequence of being easier to get it right).

In C++ (and in other languages), functions allow us to “pack” a fragment of code, identify it with a given name (much like we do with variables), and then invoke it from other sections of the program. Presumably, this fragment of code represents, or provides, a specific functionality or task. In a sense, there's a stronger analogy with variables — as much as variables are named pieces of data, functions are named pieces of functionality, or named actions, if you will.

In the above scenario, we would have three functions — Fill board, Count mines around given position, and Is given position within board. Notice the perhaps subtle detail of the name, in question form, of the function to check if the given position is within the board — more on this shortly.

The Formalities

Function Names

First of all, functions — like variables — require names; the same rules applicable to variable names also apply to function names (sequence of letters or numeric digits, but not starting with a digit; no special characters except for the underscore).

In the above example, the three functions could be named fill_board, number_of_mines or mines_around or num_mines_around, and within_board or position_within_board.

Function Parameters or Arguments

The above “named actions” (at least the last two) relate to some piece of data with which something has to be done. For instance, when we say “mines around” we're talking mines around a given position.

In the pseudo-code, it was clear that when we say “count number of mines around the given position”, the values row and column used when we define what we mean by “count mines around position” refer to the row and column entered by the user in the “main program”.

In a situation like this, we say that the function has arguments, or receives arguments or parameters. The function works with these parameters to accomplish its task, possibly producing a result (in the example of the function mines_around, the result is a numeric value representing the number of mines around the position indicated by the parameters).

Defining and Using Functions

Defining Functions

Having discussed the above details, we are now ready to look at the specifics of functions in C++. I'll start with the example (I'll use the function within_board, since it is the easiest and shortest), then explain the formalities. The within_board function would be defined as show in the figure below.

In the fragment of code from the above figure, the first line starts the function definition; it indicates the function's name, parameters, and the data type of the result (the return type). The first token that appears indicates the return type; in this case, the result of this function's task is a boolean value: is the given position within the board? — yes or no.

The second item ^[2] is the name of the function. Following the name of the function, we place the list of parameters between round brackets — if the function does not receive arguments, we must still put the round brackets with nothing inside.

The function's arguments or parameters are like variables in that they are named pieces of data; they are declared indicating their data type and their names; they are used inside the function with the same syntax as we would use to access the value stored in a variable. However, we must not confuse function parameters or arguments with variables — they are two distinct concepts; function parameters could be seen as “fictitious variables” that are reflecting the data of someone else's variable or value (emphasis on the could be seen as part).

After the first line, we enclose the body of the function in curly braces ({ }); the body of the function is the fragment of code that implements the given functionality, and is usually indented with respect to the first line and the curly braces.

Inside the function, we use the return statement to exit the function and specify the result (the return value). After we exit the function, execution resumes at the place where the function was invoked. In the above example, two return statements are used, in different sections of the function — only one of them would be executed in a given instance of execution. This is not only due to the fact that one return statement is in the if and the other one in the else; there's also the fact that as soon as a return statement is executed, execution continues at the place where the function was invoked (the call site), and not on the next line inside the function.

Brainteaser: Can you do better than the above? In particular, can you rewrite the body of the function so that it only has one return statement? (Hint: the function returns a boolean value)

Using (calling) Functions

With the function defined, we can now invoke it or call it from somewhere else in the program — in fact, we could call it from several different places in the program, if needed.

Calling a function that has a return value (that is, a function that produces a result as the outcome of its execution) is, from the point of view of the syntax, similar to reading the value of a variable; we simply write the name of the function, followed by the arguments enclosed in round brackets, and that yields a value, much like writing the name of a variable yields a value. Don't be fooled by the similarity in the syntax, though — they're two very different things; with a variable, we're simply reading a value that is stored in the memory of the computer. With functions, we are invoking a certain fragment of code that will compute and return a result — we are delegating a certain task or functionality to a fragment of code that is defined somewhere else (perhaps at the bottom of the source code file).

In the main program for the minesweeper example, we would call the function within_board as shown below.

Notice that the token within_board is used directly as a name for a boolean value — as if it was a boolean variable. Again, don't be misled by the similarity in the syntax — at the moment of the execution of the if statement, the compiler places a call to the function; execution is suspended in here, and continues in the first line of the function's body. When a return statement is executed inside the function, execution resumes here — the call site — and the return value is used in whatever way the expression requires it. In this case, the return value directly provides the result of the condition for the if, since the return type is bool, yielding a true or false value.

We also use the function within_board when counting the mines around a given position; in that case, we call it as shown below.

Here, again, we use the function's return value for an if; in this case, things are even more interesting, in that we use the function's name directly as part of an expression — one of the operands for the logical and operator; in this case, the compiler places a call to the function, passing the values of r and c as parameters; execution is suspended here, and continues at the first line of the function's body; when a return statement is executed, execution resumes here — in this example, resumes means that now the compiler, if (and only if) the returned value is true, checks the condition for the board content and does the logical AND.^[3] In other words, when the function returns, we continue to evaluate the rest of the expression where the function was used. Neat, isn't it?

Another neat detail is the fact that we are calling a function from within another function (right? Recall that the above fragment is part of what we called mines_around — a function). Surprised that we can call one function from within another function? Why? You didn't seem surprised when you saw it in the pseudo-code!

There is another subtle detail in the above: notice that the caller (or call site) now passes r and c as parameters to the function, instead of row and column, as we might mistakenly think is required.

This should not be any surprise. Think of an analogy with mathematical functions; we could have a function to compute the square root of a number.^[4] In our program, we may need to compute the square root of a given distance; or the square root of the sum of the squares of the sides of a triangle; or maybe we just want to have the computer obtain the square root of 2 for us; thus, it seems reasonable that our code should look like:

However, as far as the sqrt function is concerned, it is computing the square root of a number. Following the typical math notation, we would tend to call it $x$ (a generic value of a variable).

Thus, our definition (if we were to create our own square root function) for the sqrt function would look like:

In this case, for each instance of execution of the function (there are three instances in the above example), different values from the call site will play the role of x. In the first call, the value of the variable distance (the main program's distance variable) will be “plugged” into x;'s content (it will “play the role” of x for this one instance of execution). For the second call (remember, sqrt already finished and returned a value — the square root of the value contained in the variable distance), the result of the expression will be plugged into x's content — it does not have to be a variable from the caller what we pass as parameter!

Local Variables

We can, of course, declare variables as needed inside the body of a function. These are called local or automatic variables, and their scope is restricted to inside the body of the function. In particular, we can have a variable called count in a function, and have a variable count in the main program (or in another function). Those two variables would be entirely independent — even if the main program uses its count to be passed as parameter to the function: in such case, the main program's count will be seen inside the function under a different name (the name of the parameter), and any access to count inside the body of the function would have absolutely nothing to do with the main program's variable count — it will refer to the (local) variable that was declared inside the body of the function. Moreover, if no local variable with that name was declared inside the function, we get a compiler error: undeclared variable — the fact that at the call site there is an entirely different and unrelated variable called count has absolutely nothing to do with this.

What if the function returns nothing?

So far, we have discussed functions that compute and return a result. For the functions like fill_board in the minesweeper example, where the function simply does its job and returns to the caller with nothing more than an implied “done!” (that is, without returning a result), we still have to indicate a return type. In those cases, we use the special void type. As the word indicates, it means that the function returns nothing. We still can use return statements to prematurely exit the function (for instance, inside an if, where a particular error condition is found that forces us to exit without completing the rest of the tasks). In this case, the return keyword is followed directly by a semicolon. But in general, we do not put any return statements in void functions. When execution reaches the last line of the function's body, the function returns to the caller (you could see it as an implicit return statement being executed when reaching the end of the function's body).

Notice that with functions returning a result, we can not allow execution to reach the end of the function without a return statement; doing so would result in undefined behaviour. Notice that this does not mean that every (non-void) function must have a return statement the line before the closing curly brace — it simply means that every possible path of execution inside the function must finish with a return statement (the function within_board perfectly illustrates this issue).

Function Declaration vs. Function Definition

For reasons perhaps difficult to understand at this point, the way the compiler deals with functions is quite radical: at the point of the code where we call a function, the compiler must know the function; that is, it must have seen it, to be able to validate the parameters (if they are the correct data type, if conversion is needed — say, convert an integer value to double so that the function can interpret the right way the received bunch of bits). Given the way I presented things in the previous sections, this would mean that the definition of a function should appear in the file before the “main program”, from where the function is being called. You could see this by analogy with variable declarations — the declaration of a variable must have been seen by the compiler at the place where the variable is used.

With functions, however, things would get complicated — given that from inside one function we can call other functions, and that could go for several levels of nested calling, we could end up in a “chicken or the egg” kind of situation; function A could call function B (meaning that the definition of function B has to appear before that of function A), function B calls function C (thus, the definition of function C must be before that of function B — and therefore before the definition of function A, since B appears before A). Now, what if function C needs to call function A? (could be that for some particular condition — read: inside an if). This would imply that function A must appear before function C; but then things would break, since function A requires (indirectly) that function C appear before.

The solution to this messy situation is the use of function declarations or function prototypes. A function declaration or prototype simply informs the compiler what the function looks like, without telling it about how the function does what it has to do. In other words, the function declaration specifies the return type, the function's name, and the list of function parameters (with their data types, of course). That's all the compiler needs to know when seeing a call to the function; first and most obvious, it has to recognize the name, it has to know how to deal with the returned value (for which it has to know its data type), and it has to know how many parameters and their data types, for validation purposes as well as knowing to perform any required conversions.

The syntax for a function declaration is illustrated by the examples below.

Brainteaser: Why don't we have to be careful with the order of the function declarations? Shouldn't the declaration for within_board be first, since mines_around calls it?

Notice the semicolon at the end. This is a requirement for function declarations.

The function declaration usually is placed at the top of the program, before the main function (you had noticed that main is, strictly speaking, a function, right?). The minimum requirement, however, is that it must appear before the first use (the first call to the function). In particular, it could be one line before the line where the function is called.

Brainteaser: The requirement is a bit more strict — a function's declaration has to appear before and be visible to each of the places where it is called. The brainteaser is: What do I mean by that? Can you think of an example in which the function declaration would have to appear more than once?

More Formalities Coming — Some concrete examples first

Why don't we dig a little deeper on that infamous square root example? Of course, we would never do a square root function for a real application,^[5] but it will nicely illustrate, and hopefully clarify, what we have discussed so far in this chapter. We will call our function square_root, to avoid confusion with the built-in sqrt function.

The function declaration is, as we already saw:

For the function definition, we would actually need to know an algorithm to compute the square root of a given number. Here's an easy one: start trying all the numbers (0, then 1, then 2, etc.), until the square of the number we're trying is equal to x. Obviously, this only works for numbers that have an exact integer square root. If x is 9, then we try 0 (0 square is 0), then try 1 (1 square is 1), then 2 (2 square is 4), then 3 (3 square is 9) — bingo! We found the square root of 9. A quick fix would be to settle for an approximation of the square root — the result shall be the largest number for which that number squared is no greater than x. The problem is that this approximation is too coarse (the square root of 99 — which is approximately 9.95 — would result in 9, since 10 square is already greater than 99, so we would keep the previous value).

A solution for that would be to try all the numbers, but instead of going 1 by 1, we go 0.1 by 0.1 — that is, we try 0, then 0.1, then 0.2, etc. That way, the square root of 99 would result in 9.9 — that's a lot better than just 9. If we want two decimals of precision, we just go 0.01 by 0.01. Let's give it a try (shown below).

Here's an interesting improvement — the example in the above figure has the limitation that it produces the square root with one decimal precision. What if for a given application we require three decimals of precision? (and no, in this context, the answer «then we would use the real, built-in sqrt function» is not allowed). You could point out the fact that having three decimals precision covers the requirement of having one decimal as well, since we could discard the extra decimals if we wanted to; so, we could do it always with three decimals (notice how really easy this is: we just have to modify one line of code in the above — I trust that you'll do it). But then, why three? What if we ever need five decimals? Where do we stop? It gets worse: notice that the extra precision does not come for free — if we want, say, the square root of 10 with 3 decimals of precision, we would end up looping close to ten thousand times before finding the result (right? I trust you will explain why ten thousand times?). So, we would really want to let the caller choose what precision they need — if one really requires three decimals of precision, then we choose to live with the rather long (in terms of execution time) processing.

So, how do we actually implement this improvement? Do we create a function to compute the square root with one decimal, and another function for two decimals? (and one for three decimals, and so on?) That would certainly bring back that uncomfortable feeling that programming sucks.

How about telling the function how many decimals we want? I mean, we are “telling” it which number we want the square root of; why wouldn't we be able or allowed to tell it more about what we want? Yes, what I'm suggesting is that we use a second parameter that indicates the number of decimals that we want. The function now would have to determine the value of the step according to the value of the parameter.

Brainteaser: Why don't we just set the parameter to pass the value of step, instead of the number of decimals?

Our function would now look as shown below.

Notice the nice detail that the function from the above figure works as expected when the given number of decimals is 0.

This is still quite bad (and again, I'm not referring to the fact that there is already a square root function and we are reinventing the wheel). We will continue to improve this. In the mean time, I invite you to improve the algorithm as follows: we look for the square root value with a coarse approximation first, then refine the approximation that we found; iterate first in steps of 1 to find an integer approximation of the square root; then, continue iterating in steps of 0.1; once you found the one-decimal approximation, continue increasing in steps of 0.01 — and so on, until you have an approximation with the specified number of decimals (really, try it out!).

How about creating a function that computes the hypotenuse of a triangle given the two sides? An obvious name for such function would be... ta-da! ... hypotenuse, per chance? (see figure below)

Nothing wrong with a function that is a one-liner. You may feel uncomfortable in that you're replacing one line with another line. But there are still advantages — first of all, when we use the function, the code conveys much more directly the intent: the code explicitly says that we are computing a hypotenuse (instead of having to carefully check the formula and then realize that “oh! this is the Pythagoras formula for the hypotenuse!”). But also, the fact is that if we need to type and type that formula over and over, there is the increased risk of making a mistake (e.g., a simple typo) and getting one of the calculations wrong. If we call the function, it is far less likely to make a mistake, and we already know that the formula inside the function is mistake-free. (huh? didn't we say that we, programmers, always make mistakes? Well, think of it this way: at some point in time, the function will be mistake-free; the thing is, if you always use the function, then it will either always be subject to the mistake, or never; so we should easily notice if there is a mistake).

An obvious improvement on the above is to allow the caller to specify how many decimals they want, instead of having the function decide that we want it with two decimals (see figure below).

Any surprises? Can we use the received decimals parameter to be passed as parameter to the square_root? Why not — if we can use side1 and side2 as part of an expression to be passed as the first parameter, why wouldn't we be allowed to do the trick with decimals?

But is it Always Numbers?

All of the examples so far have been sort of mathematical functions. However, we can create functions that deal with text, for example, both as parameters and as return value. We could for example set up a function that assembles a full name in a single string, given first name and last name. To make it more fun, let's say that the function will produce a full name with format "MORENO, Carlos". We could set up one function that computes the uppercase equivalent of a string (seems useful anyway), and then set up our fullname function that makes use of the uppercase one, as shown below.

We could now improve it by allowing the caller to specify the format that they want (for example, "First Last" or "LAST, First"), as shown below.

Brainteaser: There is a severe bug in the function fullname from the above figure. Can you spot it — and of course fix it? (and no, it's not the missing upper function; it is assumed that the function is defined somewhere; it's just that the second fragment of code only shows the fullname function)

In addition to the severe bug that I trust you have found and fixed by now, the above string functions (both!) illustrate a very bad practice in the way the parameters are passed. We will discuss this detail in the next section.

More on Parameters

The Problem

Say that we want to create a function to sort the elements in a vector (say, a vector<int>). Seems like an honorable goal, right? Let's try it out — I'll use the following algorithm: find the lowest element in the vector, and swap it with the first element in the vector (which means that we'll really have to find the position of the lowest value); then, find the second lowest (or, in other words, the lowest element starting at the second position) and swap it with the second element, and so on, until reaching the last element. At that point, the elements in the vector are in order from lowest to highest.

I will split this task into several functions, but will only provide the definition for the function sort_values:

Nice, isn't it? Too bad that it does not work (at all!). Try it out if you don't believe me (which means that you would have to write the other two functions as well). Set up a vector with whatever values (not in order), then call the function passing the given vector, and after returning from the function, print the values in the vector — you'll notice that nothing changed, and that the values are not sorted.

This is due to the mechanism used to pass the parameters to functions. In particular, if the call site uses a variable as parameter to the called function, what is passed as parameter is the value stored in that variable, and not the variable itself. This is consistent with the notion that we can pass the result of an expression, or even a literal value (e.g., a numeric value given directly).

The function is allowed to modify the parameter, but what really is being modified is the copy of the value that the function is receiving, and not the variable at the call site where the value came from.

Brainteaser: It's not only the function sort_values that won't work — or you could say that there are two reasons why it won't work. Can you spot this additional problem? (I won't ask you to fix it, since that requires the solution that we're about to see in the next section)

The Solution — Passing Parameters by Reference

In the previous section, we discussed the way that arguments are passed to functions by default — they're passed by value. Passing parameters by value involves creating a copy of the value if the caller uses a variable, or simply passing the result of the expression used as parameter in the function call (a value).

An alternative mechanism can be used — passing parameters by reference. This does not involve making a copy of the value, but instead, telling the function where to find those values (all this “telling” happens behind the scenes, of course).

Remember that every variable really represents a value stored somewhere in the memory of the computer. Where? We do not know — the compiler knows, since it is the one that creates the CPU-level code that executes the tasks indicated by our C++ code.

The twist here is that if the function is told where the values are, then it can modify them — it can simply read them if it chooses to, but the fact is that it now has access to modifying those variables at the call site.

A parameter simply has to be declared as a reference, and the compiler will automatically figure things out and do the right thing. To declare a parameter as passed by reference, we simply place an ampersand sign (&) after the type, and before the parameter name. The function sort_values should have the signature as follows:

At the call site, we call the function by simply indicating the vector that we want to pass — nothing special is required; the very fact that the function's parameter has been declared by reference (which the compiler knows, since at the time that a function is called, the compiler must have seen the function's declaration) suffices — the compiler will know to do the right thing behind the scenes.

The definition of the function is exactly the same — only that now it will work, since whatever modifications done to values in the body of the function will be reflected on the vector used in the call site (e.g., the main function).

Well, it won't really work, since there was an additional detail (that hopefully you spotted — brainteaser at the end of the previous section). What about the function swap? Can that function possibly work? Let's see; if we have (in the main program) two variables, called age1 and age2, containing the values 13 and 15 (respectively), then, when we call swap (age1,age2), copies of age1 and age2 are made and passed to the function — the values 13 and 15 will be passed, and not the variables age1 and age2. The function swap would do the standard three-steps trick with a temporary variable, but it will be swapping only a and b; that is, it will swap the copies of the values; any actions inside the body of the function swap will have absolutely no effect on the variables age1 and age2. The solution is, of course, that swap should receive its arguments by reference (see figure below).

Now you can try it out! (you would still have to write the function pos_lowest)

Notice that the function pos_lowest does not need to receive any parameters by reference — it only has to look at the values stored in the vector, and not modifying them; those values are the same if the function is looking at the original or at a copy of the vector.

Keeping in mind...

When a function receives parameters by reference, the caller is not allowed to call the function passing the result of an expression, or a literal value, or anything that is not a persistent value owned by the caller — a variable, or an element of a vector, or one of its parameters, if the caller is another function (would that require that it be a parameter that was received by reference?).

To help you visualize the above, think of what could possibly be the meaning of the following (all incorrect) statements:

    swap (age, 10);
    swap (a+1, b);

More Uses for Parameters Pass-by-reference

The discussion on the function pos_lowest and how it does not need to receive the parameter by reference should have gotten you worried; imagine a vector that has several million elements; whenever we pass that vector to a function, a copy must be made — that's several million elements that need to be copied from one area of the memory to another. Doesn't look good, does it?

The use of parameter pass-by-reference sounds quite tempting to tackle this problem — we do not create a copy of the vector; instead, we leave it exactly where it is, and tell the function where to find it. The function will now go and read the elements — notice that, in principle, the function does not need to modify the elements; in this context, we are talking about a function for which passing the vector by value would be an option, and we are suggesting now the use of parameter pass-by-reference as an optimization, to avoid the effort of creating a copy to be passed to the function.

The caveat, of course, is that now we introduce the risk of the function accidentally modifying the values from the caller, leading to somewhat hard to trace bugs — as much as functions help us in isolating the various pieces of functionality to organize our code, they could end up having the unwanted effect of isolating the bugs so that they're harder to find!

The “best of both worlds” in this case is to pass by reference, only that we use a const-qualified reference. We usually refer to this as parameter pass-by-reference-to-const, and translates to (informally speaking) telling the function “the parameter, which you are not allowed to modify, is there”.

Using this convention, the function signature for pos_lowest would be as shown below.

In the function's body, we simply use values exactly as we would if the parameter had been passed by value — except that if we attempt to modify it (presumably by mistake), we would get a compiler error.

This is a standard practice for strings and vectors, since they potentially contain large amounts of data — an integer is just a few bytes (four on many platforms); a string could contain tens or hundreds of bytes; making a copy of strings is in general considered expensive (in terms of execution time).

The examples with strings should be rewritten as shown below.

Default Argument Values

There are still a few inconvenient details in the examples that we have discussed so far — I will discuss now an additional tool that addresses some of these details.

The Inconvenience

Recall the functions square_root and hypotenuse that we discussed earlier. We added a second parameter for increased flexibility — the caller can choose how many decimals they want. Also, in the function fullname we added some degree of flexibility via a second parameter to indicate the desired format.

However, in all cases, this increased flexibility could turn into an inconvenience — if most of the time that we call the function square_root we want two decimals, then having to type an additional parameter, almost always a 2, becomes rather an annoyance. Same thing for the hypotenuse. Same thing for the full name, if most of the time we want it with format "LAST, First".

The Good News

We can still have the best of both worlds: increased flexibility through an additional parameter, but the ability to omit such parameter at the call site if we want some default behaviour — a default behaviour in the form of a default value for the parameter that we omit.

When declaring the function, we can specify default argument values for the right-most arguments (any amount of them, but always the right-most parameters). To do so, we place, after the parameter name, an equal sign followed by the value that we want as the default.

For instance, if we want the ability to call the square_root function omitting the decimals parameter with a default of two decimal places, we would declare the function as follows:

When calling the function, if we do use a second parameter, then decimals would take that value; if not, the function will still receive a second parameter, with a value of 2 in it (see figure below).

The restriction of the right-most arguments only refers to the fact that the following, as an example, is not valid (see figure below):

The above code, however, would be valid — even if this particular example would not make much sense.

With the above function signature, calling the function with a = square_root(); would be exactly equivalent to a = square_root(0, 2);.

In the example of the fullname, the function declaration could look as follows:

Details, details...

It is important to highlight that default argument values can only be specified in the function declaration; they are not allowed in the function definition — unless the definition is acting as both declaration and definition (when would that be the case?).

The rationale is the following: the function does receive all the parameters, regardless of whether or not they were omitted at the call site. Always.

At the call site, the preprocessor (the first stage of the compiler, which is in charge of the #include directives, substituting constants by their corresponding values, and other housekeeping tasks prior to actually proceeding to compile the code) replaces the missing parameter with the value provided as default. Notice that the preprocessor does not modify our source code file — it does actually rewrite the code, but to the compiler's temporary internal working files. The important detail is, when we call square_root (a), the compiler (the actual compiling stage) really does see the code square_root (a, 2), and that is the code that gets compiled.

Function Overloading

An alternative to the default arguments value technique is available through the use of function overloading. Careful, though: function overloading is a more general technique — it's simply that one of its uses somewhat overlaps with the use of default argument values (more on this shortly).

Function overloading is a technique where more than one function exist with the same name but different arguments list — the somewhat fancy term refers to the fact that, at first glance, the functions, because they have the same name, look as though they were the same function; overloading refers to the fact that we are giving the same function additional tasks: we're overloading it.

I somewhat dislike this point of view — I prefer the more formal point of view that two functions with different signature are two different functions. Regardless of how we choose to look at it, the fact remains that the technique is called function overloading.

We could use function overloading to tackle the inconvenience discussed for the square_root function — having to always type the number of decimals even if most of the time we're happy with a suitable default number of decimals.

With function overloading, we would define one function called square_root receiving one argument (and computing the square root with a default number of arguments — two, for instance), and one function called square_root receiving two arguments.

Notice that, because one the functions computes the square root with any specified number of decimals, we can implement the other function (the one that computes the square root with two decimals) in terms of the former, as shown below.

To Overload or Not to Overload

The above title really translates to: how do we choose if we should use function overloading or default argument values?

If you are simply worried about achieving the required functionality, then you could pick either one — for instance, in the example of the square root in the previous section, you see that at the call site, we use square_root(x) to compute the square root with two decimals (with a default number of decimals), and we use square_root(x,n) to compute the square root with n decimals — whether we use default argument value of 2 for the parameter decimals or we use function overloading as shown in the previous section, the outcome is exactly the same.

However, there's an additional point of view which is the issue of the function declaration conveying the intent. In the case of the square root, it really does not make sense to use function overloading to allow the caller to omit the second parameter — we really are, in all cases, computing the square root with a certain number of decimals; it's just that in some cases, we want to leave the decision up to the function (that is, if we do not specify how many decimals we want, we really mean: “give me the square root with whatever default number of decimals”).

The technique of function overloading would make sense if there were situations where the square root is not computed with a number of decimals — except that that is never the case. If anything, function overloading would make sense if we had situations where the square root is to be computed with a variable number of decimals — such as, for instance, an algorithm that is designed to finish in a given amount of time, and so, it will come up with an answer that will have as many decimals as it could find in the allocated time. (but we're splitting hairs at this point, aren't we?)

Other Uses of Function Overloading

In the previous sections, we discussed the use of function overloading as an alternative to default argument values. This is not the only type of situation where function overloading provides a convenient solution.

Consider for instance the function swap. We designed it as void swap (int & a, int & b). What happens if we have two double variables, or two string variables that we need to swap?

With strings, there is no argument about the fact that it is not possible to use that function. With doubles, you may be tempted to argue that the compiler can do conversion from double to int — however, because the parameters are references, type conversion, or type casting is not allowed. Think about it: you are not passing the function a copy of the value stored in your variable (in that case, you could convert that value to whatever required data type): you are telling the function where to find your data. But what you have in your variables already has a data type, and it can not be changed (it is something that is already in the memory of the computer); therefore, the compiler enforces the fact that if you call a function that receives a parameter by reference, you pass it a reference to an object of the same data type.

This simply means what you are already thinking: if we want a function to swap two doubles, we must have a function receiving two double arguments by reference; to swap two strings, we need a function receiving two string arguments by reference, and so on. Of course, we wouldn't want these functions to have different names — if it makes sense to call it swap and pass two integers, why wouldn't it make sense to call it swap and pass two doubles?

Our swap function could then become a family of overloaded functions, as illustrated below:

The definitions would be quite similar for all of them — just have the temporary local variable declared as the same data type as the arguments.

Overloading Ambiguity

There is an important aspect to watch out for when using function overloading; it is related to the compiler's choice of which function to call — a feature known as overloading resolution. This choice is clearly made based on the parameters at the call site. For example, if we call a function with square_root (10, 2), to obtain the square root of 10 with two decimals, it is obvious that the compiler would choose the function with signature double square_root (double x, int decimals), because the one receiving only a double would not match.

What about the cases where the number of parameters is the same, and implicit data type conversion is viable? Consider the following example:

What happens when, at the call site, we invoke the function with:

How would the compiler choose which function to call? Both are plausible, as both require an implicit conversion (double to float, or double to int).

In this case, the program is said to be ill-formed (which is a fancy way of saying that we'll get a compiler error), due to overloading ambiguity. The call, as it appears at the call site, is said to be ambiguous, since it could mean more than one available function, without the compiler having the means to resolve the ambiguity.

The rules for overloading resolution are somewhat involved for an introductory chapter; the solution to the above problem is to define the overloaded versions of a function being careful with implicit conversions; another option is to explicitly convert the type at the call site — in a sense, we are resolving the ambiguity for the compiler. The following fragment of code is perfectly valid, as it does not incur in overloading ambiguity:

Function Templates

In the previous section, we discussed the use of function overloading to define a family of overloaded functions.

Though it seems a quite powerful goal, the solution is, at best, annoying — how many data types are there? We have ints (long/short, signed/unsigned — all combinations), chars, floats, doubles, long doubles, strings; then vectors (vector of all of the above). It gets worse (much worse), but I'll stop, as I'm sure you are already depressed enough and are eager to find out what the good news are.

The good news are, of course, template functions. With this technique, we provide a blueprint or template that defines a family of functions with identical implementations.

Notice that the definitions for all the swap functions are really identical: declare a temporary variable with the type of the parameters, assign the first parameter to it, etc.

A template swap function would be defined as shown in below:

The interesting, though perhaps tricky, detail is that the above template does not really materialize into anything — instead, it is used by the compiler to instantiate concrete versions of swap for a given data type, deduced from the call. If we call swap with two variables of type int, the compiler will instantiate a version of that template with T = int. You could look at the Ts in the function definition as fill-in-the-blanks fields that you replace (in your head, so to speak) with the given data type.

In the template function definition, the name given to the generic type (T) is arbitrary; we could have called it Type, or Datatype, or whatever valid name — roughly speaking, following the same naming rules for variables or functions. However, the choice T seems reasonable enough for the general case.

As if things were not confusing enough already,^[6] we can combine template functions with function overloading. This makes sense when we have a family of identical functions with a few exceptional cases — some specific data types for which the function definition is not identical. The rules of overloading resolution, roughly speaking, are the same, with the additional detail that if a concrete version (an overloaded version) is available, then the compiler chooses that one; otherwise, the compiler tries to match the parameter list at the call site against the template definition and see if it can instantiate one version that matches the given call.

As an example, consider a function print that prints its parameter via a cout statement, but with certain possible decorations; if the parameter is a string, we want to print it surrounded by double-quote characters; if it is a char, surrounded by single-quote characters; otherwise, just print it the way cout would. This is implemented by the code shown below.

Recursive Functions

The notion of recursion relates to something that invokes itself; the notion could apply to definitions (as in, a definition of something). For example, a directory (or folder) in a computer could be defined as a section of the hard disk identified by a name, and that contains files and other directories. You'll notice the strange detail that while defining the term “directory” we make a reference to the term “directory”. However, thanks to that “magic” that makes our brains work, we seem to have no problem figuring that out; perhaps more surprisingly is the fact that a computer (well, a compiler) can, in a sense, also figure it out!

In programming — in particular in the context of functions — we talk about recursive functions. A recursive function is a function that invokes (calls) itself. We also talk about recursive structures (or recursive data structures); and in fact, the example of the directory could be seen as an example of a recursive structures; a directory defines the structure of the storage space, and the structure of a directory involves other directories. In this tutorial, however, we'll focus our attention to recursive functions.

As a quick example to get us started “digesting” the idea, say that we want to obtain the total amount of disk space under a given directory (including the space used by the subdirectories). How could we approach that? We could describe the procedure with the following statement: the total disk space used by a directory is the sum of the sizes of the files inside the directory plus the sum of the total disk space used by each of the subdirectories. Surely, you have no problem understanding how to actually obtain the result, right? Each time that you find a subdirectory, you chdir to it and repeat the same procedure. Hmmm.... maybe the difficulty is now in keeping track of things. Perhaps a quick solution is thinking of a group of people, each one with the capacity to follow these instructions to obtain the disk space. With this setup, every time you encounter a subdirectory, you ask someone else to give you the total amount of disk space under that directory (notice that for you, that's a subdirectory, but for that person, that is the directory that they'll work with). And of course, that person will follow the same procedure, and each time they encounter a subdirectory, they will find someone else to delegate the task. Each of the persons simply has to wait for all the others to come back with their results (the space under each of the subdirectories), and then add the values together and return the result. We'll work on the pseudocode for this example in a few moments.

Perhaps another difficulty that comes to mind when being exposed to the notion of recursive functions is understanding how it can work without producing an infinite loop; if the function calls itself, then execution starts over, and because it is the very same function, it will call itself again, right? But being again the exact same function, it will have to call itself again, and so on — right?

Let me give you a hint (in case you want to work on figuring it out yourself before I continue and spoil the puzzle for you): does the fact that two fragments of code are identical means that the sequence of executed statements will be identical?

Clearly not — the same fragment of code working with different data could produce a different actual sequence of executed statemtns; of course, this is the case only if there are conditional statements involving the data.

So, voilà — we discover our first unconditional constraints for a recursive function to work: the recursive call(s) (that is, the call(s) to itself) must be inside some form of conditional statement; could be an if, an if-else, a switch, a ternary operator — even a loop, if you think about it (I trust that you will think about it).

Clearly, the above is a necessary condition, and not a sufficient condition — the recursive call could be inside a conditional and still produce an infinite loop (the condition could happen to always evaluate to true). But what we know is that if it is not inside a conditional, then it is certain that it will produce an infinite loop.

Brainteaser: Actually, the above statements, strictly speaking, are incorrect; the real constraint is not that the recursive call must be inside a conditional statement; the real constraint is that the recursive call should be executed conditionally. The brainteaser is: what do I mean by that? (can you give an example?)

The typical structure of a recursive procedure is one where the problem is broken down into simpler (or smaller) pieces; if the given problem is not simple enough, we continue to further break it down into even simpler pieces, and delegate the processing for those pieces (delegate it to “itself”, or rather, to another instance of execution of the same function). If the broken down piece is simple enough (and by this we mean if it is a trivial case, or the so-called base case), then we simply produce the result. Of course, the section that breaks the problem down and delegates execution of the parts is also responsible for combining the results for the various pieces into the result for the problem that was given to this instance of execution (which may be either the original problem or one of the smaller pieces resulting from breaking down the original problem).

In the example of the disk space used by a directory, the base case would be a directory that contains no subdirectories; we can easily obtain the space used by that directory. The process of braking down the problem refers to the aspect of breaking down the contents of a directory into the files and each of the subdirectories (each of the subdirectories is clearly a smaller piece). The process of combining the results in this case refers to simply adding all of the numbers returned by the recursive calls to obtain the space under each of the subdirectories, and add together with the sizes of the files.

Let's look at the pseudocode for the example of the disk space under a directory (and this is all we'll do, since we would need to deal with the actual facilities to read the contents of directories, file sizes, etc., and that is way beyond the scope of this tutorial):

One of the classical examples for recursive functions is the factorial of a number; ironically enough, using recursion to compute the factorial of a number is the worst, most horrible idea — at least in the vast majority of contexts (but until you get to advanced enough aspects such as template metaprogramming, trust me: worst, most horrible idea!).

Still, the factorial example is definitely one of the examples that most nicely illustrate the workings and the mechanics of recursive functions. In case you don't remember, the factorial of a (positive integer) number n (denoted n!) is the product of all the integer numbers between 1 and the number (notice that 1! = 1); by convention, 0! = 1

An alternative way to define the factorial is as follows: For a nonnegative integer number n, its factorial, denoted n! is defined as:

You'll notice that the definition itself is recursive, in that part of the definition of the factorial of a number involves the factorial (of another number, of course!). But the above leads directly to our implementation of the recursive factorial function:

If you want to get fancier (or I should say, if you're the kind of person that enjoys compact/concise code), you could rewrite the function as a one-liner, even though it doesn't necessarily help in terms of readability (but hey, remember that we would never, ever implement a factorial function like this in a real-life programming situation, right?):

If you are having difficulty visualizing how the whole thing works, you could modify the above code (the first version) and place cout statements to trace the execution. One thing that you have to understand is that each time that factorial is called, it is a new instance of execution, and the compiler treats different instances of factorial as if it was different functions being called. So, the execution “remembers” that the instance of factorial receiving, say, 3 as parameter, was called from the instance receiving 4, and thus, when the instance receiving 3 returns, execution resumes at the point in the instance receiving 4 where it called factorial passing 4 − 1 as parameter (and “resumes” in this case means that the received return value — 6, in this example — is multiplied times n — 4 in this case — to return the result; in this case, 6 × 4 = 24, which is the correct result for 4!).

Exercise for the reader: improve the above “demo” function so that it prints with indentation to show the hierarchy/sequence of calls. That is, instead of simply printing the following for the factorial of 4:

It should output the folowing:

The exercise is far from trivial; that is, once you realize the important detail, then actually writing the code is easy; but you need to think somewhat outside the box.

Another example

Perhaps a more realistic example (that is, one which serves not only learning and illustration purporses) could be a recursive, divide-and-conquer procedure to add the elements of an array of floating-point numbers.

It turns out that floating-point numbers, always giving us a headache, have the annoying characteristic that adding two numbers in different orders of magnitude is particularly inaccurate. If we have an array of numbers where we could reasonably expect that all the numbers are more or less in the same order of magnitude, then adding them sequentially could give a very inaccurate result. This is easy to see, since by the time that we get to half the array, if the number of elememts is large, say 2000 elements, then the sum would be in the order of 1000 times the typical values, and adding each value to the running total would reduce the accuracy of the operation

A better strategy is adding pairs of numbers (e.g., adding together each two contiguous elements), then adding each two contiguous results, and so on. This way, all additions are done with operands that are in the same order of magnitude.

You'll notice that this description is a disguised way of describing a recursive procedure where we break the array in two halves, and recursively obtaining the sum of each half to add the two together and produce the result. The base case being an array of one element, where the sum is the value of the element. The second-to-last recursive call would be the one that adds pairs of contiguous elements, and then pairs of results are added as part of the combining portion of each recursive call. The figure below shows the implementation of this recursive function:

Brainteaser   (more like an are-you-paying-attention kind of thing): why the detail with the way half is computed and used? Why not the first recursive call from from to half-1 and the second one from half to to?

Exercise for the reader: You'll notice that the extra two parameters, from and to are necessary to avoid the inefficiency of copying values over and over to pass the “half-array” to the recursively called instances. However, this leads to the annoying detail that client code would have to keep in mind that it has to pass those two parameters, always with values 0 and size-1, to obtain the sum of the whole array.   The exercise is modifying the code such that client code does not need to pass any extra parameters besides the array   (Hint: recall function overloading).

Case Study: URL Encoding and Decoding

In this section, I revisit (and hopefully improve upon!) the case-study example from the strings tutorial.

In terms of functionality improvements, I will now consider special characters. The example in that section would fail if the text to encode contains the + character; for instance, I could choose my favourite programming language as my password! In URL-encoding, any character that is not an alphanumeric character in the US alphabet (a to z, A to Z, and 0 to 9) is encoded with a three-character sequence containing the % sign followed by the two-digit hexadecimal representation of the value that encodes the character in question (for instance, the ASCII code on platforms that use this ubiquitous, even if arguably outdated, encoding). I will not discuss ASCII or hexadecimal notation; if you are not familiar with ASCII codes or with hexadecimal notation, please consult some suitable reference (such as http://www.asciitable.com).

This trick also solves the problem of one of the parameters containing the character = or the character &, since these two characters have a special meaning in the URL-encoded string.

As a more complete example to illustrate all the cases in a URL-encoded string, if my password is carlos moreno, a C++ programmer, then the URL-encoded data would be:

(the ASCII code of the character comma is 2C, and the ASCII code of the character + is 2B)

URL-Encoding Data Entered by the User

If we are working on applications that deal with URL-encoding, it seems reasonable to suspect that we'll use this functionality relatively often; this illustrates another advantage of functions: we create the function just once; test it and debug it until we're convinced that it's working as expected — then never again worry about getting it right: we already got it right! From now on, whenever we need a URL-encoded string, we just call the function!

The basic structure of the program is a do-while loop, with stop condition given by an empty string read from the user. At each pass of the loop, the program reads the two pieces from the user and appends the corresponding item, in the form name=value, with proper encoding and separation with the character &.

The figure below shows the program's structure for the URL-encoding.

The ... is not part of the program — it simply indicates that the example intentionally omits the details

Each individual encoding is done by iterating over the characters of the string and replacing it by its encoded version if necessary (replace spaces with + and non-US-alphanumeric characters with its hex-encoded representation).

In this case, however, it would be complicated to replace those characters in the same string while we are looping through its characters, since the length of the string is constantly changing and the loop counter would have to be carefully adjusted. A better approach is to build the encoded string on a separate variable, character by character, as shown below, where the string contained in the variable plaintext is encoded to the variable encoded.