C++ Tutorial 6 - Functions And Recursion Using Collatz

This is the sixth tutorial in our series on the C++ programming language. This lesson will go over functions which might not seem to be a terribly new concept at first, because we will start by going over the same material which we have already gone over so checkout the earlier lessons, but by the end of this lesson we will have introduced several new and vital ideas so try to follow along as much as you can and when something seems unclear it would probably be best if you try out some of your own code to understand it better.

In order to get a better look at functions we will again return to our old friend the Collatz conjecture. If you look back at the programs in our previous lessons, then you might notice that the code is a bit long and if you were reading through the code before running it, or if you made a mistake somewhere, or perhaps you wanted to change the code in some way then you probably noticed it was quite a bit of work. Well there is a way simplifying that code, or any code which has repeat code, considerably with functions. Consider the following code:

#include <iostream>
using namespace std;

int collatz(int n)
{
int steps = 0;

while(n != 1)
{
if(n % 2 == 0)
{
n /= 2;
}

else
{
n = n * 3 + 1;
}

++steps;
}

return steps;
}

int main(int argc, char *argv[])
{
cout << "=== Starting Program ===\n" << endl;

const int SIZE_OF_DATASET = 100;

int array_of_steps[SIZE_OF_DATASET];

for(int i = 1; i <= SIZE_OF_DATASET; ++i)
{
int steps = 0;

array_of_steps[i - 1] = collatz(i);
}

int max = 0;
double avg = 0;
int num = 0;

for(int i = 0; i < SIZE_OF_DATASET; ++i)
{
if(array_of_steps[i] > max)
{
max = array_of_steps[i];
}

avg += array_of_steps[i];

bool unique_value = true;

for(int j = 0; j < i; ++j)
{
if(array_of_steps[i] == array_of_steps[j])
{
unique_value = false;
}
}

if(unique_value)
{
++num;
}
}

avg /= SIZE_OF_DATASET;

cout << "The maximum number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << max << endl;
cout << "The average number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << avg << endl;
cout << "The number of unique values from 1 to: " << SIZE_OF_DATASET << " is: " << num << endl;

cout << "=== Ending Program ===\n" << endl;

return 0;
}

There are two functions in this program. The first one, reading from top to bottom, is simply called collatz, we will return to this function in a moment. After this we see another function named "main". A small side note on the syntax is required here. First of all, every function needs to have a name, and every name has to follow the same rules for naming variables. Secondly, each program has to have one and only one, in other words unique, function named main. This "main" function is the first function which the compiler will look at and it is from this function that other functions are called - even if the functions called by main also call other functions. Next, every function has to have a set of parenthesis after the name of the function. Some functions, such as the collatz function in this program, have parameters which are used to pass values into the function. A word of caution on the terminology, many people conflate the difference between parameters and arguments. Parameters are the variables which are defined between the two parenthesis, which along with the name of the function is called the function definition, but arguments are the variables which are passed to the function from its calling function - like in the main function where we call collatz using the i value.

Additionally, some functions also "return" a value to their caller function, the collatz function in this program returns an integer to main, and to define this behavior in the function definition by including the return type just before the name of the function. So, a generalized function definition would look something like, <return type> <function name> (<first parameter type> <first parameter name>, <second parameter type> <second parameter name>) open brace ... etc.

Moving onto the actual purpose and behavior of two functions. If we compare this code to the code in the previous lessons, we can see that the main function is mostly unchanged except the while loop in which we performed our calculations has been moved into the collatz function. The rest of the main function is unchanged but the while loop which was moved to the collatz function has one addition, the line "return steps;" which uses the keyword "return" and tells the compiler to return the number of steps taken. If you omit this line of code the compiler will most likely object to a non void, void is the keyword which we use in the definition of a function that does not return any values, function not returning a value. Additionally, a <return statement> also tells the compiler that a function has ended so any code that appears after the return statement is not executed. None of the logic found in the previous programs has substantially changed except for the fact that this is considerably more readable. Additionally, if we wanted to compute some arbitrary value, not in the loop, it would be trivial to simply call the function which would look something like, "collatz(n)" which is a convenient and easy notation that probably looks more familiar.

So far, we have gotten away without worrying very much about scope. Scope is an interesting concept which allows us to define and use variables inside of a control structure, like a loop or an if statement, between two braces, {}, or in these programs in another function. Fundamentally, this is fine, but in practice what this means is that once we leave that scope then the variable and the data which that variable held is destroyed. We can see this effect in action when we call the function collatz multiple times in a row. The number of steps returned is set to zero at the start of the function and the value calculated throughout the rest of the function. Then, the number of steps is finally returned to the main function at the very end of the collatz function but the variable steps is destroyed and its value is passed to the array in main. Sometimes however it is helpful for us to preserve a variable for later use after the instance of that scope is closed. We can do that with something called a static variable which will create a single variable for whatever instance we use. Because the number of steps is somewhat unique to a giving input, we will refrain from passing any values into the collatz function. Instead, we will use a static variable which will be incremented each time that we call the function. Consider the following code:

#include <iostream>
using namespace std;

int collatz()
{
static int val = 0;
++val;
int n = val;

int steps = 0;
cout << n << endl;

while(n != 1)
{
if(n % 2 == 0)
{
n /= 2;
}

else
{
n = n * 3 + 1;
}

++steps;
}

return steps;
}

int main(int argc, char *argv[])
{
cout << "=== Starting Program ===\n" << endl;

const int SIZE_OF_DATASET = 100;

int array_of_steps[SIZE_OF_DATASET];

for(int i = 1; i <= SIZE_OF_DATASET; ++i)
{
//cout << collatz() << endl;
array_of_steps[i - 1] = collatz();
}

int max = 0;
double avg = 0;
int num = 0;

for(int i = 0; i < SIZE_OF_DATASET; ++i)
{
if(array_of_steps[i] > max)
{
max = array_of_steps[i];
}

avg += array_of_steps[i];

bool unique_value = true;

for(int j = 0; j < i; ++j)
{
if(array_of_steps[i] == array_of_steps[j])
{
unique_value = false;
}
}

if(unique_value)
{
++num;
}
}

avg /= SIZE_OF_DATASET;

cout << "The maximum number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << max << endl;
cout << "The average number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << avg << endl;
cout << "The number of unique values from 1 to: " << SIZE_OF_DATASET << " is: " << num << endl;

cout << "=== Ending Program ===\n" << endl;

return 0;
}

The only thing which might appear to be confusing about this section of code is that we are defining the variable, remember the only variable that is created, is not initialized in our code. Actually, it is initialized but the way in which it is initialized might not appear obvious. The compiler performs something called default initialization on static variables which means that when a static variable is declared, the value that it is assigned is equal the default value for that type. There really is no benefit to using static variables in this program because even though we can get away without passing any values through the main function, passing a value to a function is not a "free" operation and causes some load on your CPU, but because the value "n" is mutated we still have to create another variable to set n equal to and the amount of time saved from not passing values to the collatz function is negligible . Sometimes, it is quite helpful or more ideal from a performance perspective to use static variables instead of passing values through parameters.

One common performance optimization trick is to include something called an inline function. In order explain what an inline function is and what it does we will have to explain how the compilation process works. Up until now we have gotten away without having to clearly define how the compiler works but we need to introduce the idea at some point and now makes at least as much sense as any other place. When we write our code it does not mean anything until we run our compiler and our source code, the C++, is turned into machine, binary, instructions, exactly what instructions will depend upon what hardware and operating system you have, and only after we run the "binary" file does the code actually do something. When we write a function in a C++ program, that function along with its calling function are translated into instruction which will run on your machine. Included in those instructions is the logic to "jump" from one segment to another and of course return to the previous segment, the calling function, along with all of the associated argument passing etc. Function inlining takes the instructions which are generated by creating the new function and inserts them between the calling segment of the calling function, and the return segment of the calling function. None of the operations which were involved in calling another code segment, passing arguments, or returning values are required anymore. This can lead to significant performance boosts but as with most things in computer science there are some disadvantages also. First of all, function inlining can vastly increase the size of your binary which can be undesirable. Secondly, when a function becomes too large, in terms of the number of instructions it requires, the advantages start to disappear. There are some other miscellaneous problems associated with inline functions, but those are big ones and as long as you use them occasionally there should not any major issues with using them. The good time is that inline functions only require the addition of one key word, "inline".

#include <iostream>
using namespace std;

inline int collatz(int n)
{
int steps = 0;

while(n != 1)
{
if(n % 2 == 0)
{
n /= 2;
}

else
{
n = n * 3 + 1;
}

++steps;
}

return steps;
}

int main(int argc, char *argv[])
{
cout << "=== Starting Program ===\n" << endl;

const int SIZE_OF_DATASET = 100;

int array_of_steps[SIZE_OF_DATASET];

for(int i = 1; i <= SIZE_OF_DATASET; ++i)
{
array_of_steps[i - 1] = collatz(i);
}

int max = 0;
double avg = 0;
int num = 0;

for(int i = 0; i < SIZE_OF_DATASET; ++i)
{
if(array_of_steps[i] > max)
{
max = array_of_steps[i];
}

avg += array_of_steps[i];

bool unique_value = true;

for(int j = 0; j < i; ++j)
{
if(array_of_steps[i] == array_of_steps[j])
{
unique_value = false;
}
}

if(unique_value)
{
++num;
}
}

avg /= SIZE_OF_DATASET;

cout << "The maximum number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << max << endl;
cout << "The average number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << avg << endl;
cout << "The number of unique values from 1 to: " << SIZE_OF_DATASET << " is: " << num << endl;

cout << "=== Ending Program ===\n" << endl;
}

Before we end this lesson, there is one concept which is admittedly a bit advance but should be introduced early on so that when we address it later on, probably in Binary Search Trees, it does not appear too foreign, and also because it will help to create useful challenges for you to learn to program better. We have talked in a roundabout fashion about how functions can be called or can call other functions, and how every function is somehow called by the main function , but something which we have not talked about is how functions can be called by themselves. There is nothing illegal about a function myFunction() calling myFunction() inside the definition of myFunction(). This might seem a bit mind bending and if it dos then good because this is something which trips up almost everyone when the first see it. A function calling itself is called recursion. Unconditional recursion is, in theory, infinite and will continue in a pattern which looks quite a bit like the Morton salt girl carrying a container of Morton salt with a picture of the Morton salt girl on the container. It also looks a great deal like a series of consecutive squares, or consecutive circles, or any other regular geometric pattern. Recursion has many interesting theoretical implications which we will have to address at a slightly later time, but for the moment you have to remember that unchecked recursion, or more formally - recursion without base case, will cause an infinite loop, again in theory, which will continue calling the same function until we run out of memory. Part of the reason why we are talking about recursion is to illustrate that every time we call a function, the computer has to save the previous function in memory and it also has to save the argument which are being passed to the function in memory, and finally if the function returns a value then that value also has to be save to memory. All of this happens every time we call a function and recursive functions are no exception, and in the case of a recursive function that lacks a base case it will happen until the computer runs out of room to run these new functions. To illustrate this error, consider the following example of code which WILL NOT WORK and will case the program to give you a small error regarding the stack space on your machine.

#include <iostream>
using namespace std;

int collatz(int n, int steps)
{
if(n % 2 == 0)
{
n /= 2;
}

else
{
n = n * 3 + 1;
}
steps = collatz(n, steps + 1);
}
return steps;
}

int main(int argc, char *argv[])
{
cout << "=== Starting Program ===\n" << endl;

const int SIZE_OF_DATASET = 100;

int array_of_steps[SIZE_OF_DATASET];

for(int i = 1; i <= SIZE_OF_DATASET; ++i)
{
array_of_steps[i - 1] = collatz(i, 0);
}

int max = 0;
double avg = 0;
int num = 0;

for(int i = 0; i < SIZE_OF_DATASET; ++i)
{
if(array_of_steps[i] > max)
{
max = array_of_steps[i];
}

avg += array_of_steps[i];

bool unique_value = true;

for(int j = 0; j < i; ++j)
{
if(array_of_steps[i] == array_of_steps[j])
{
unique_value = false;
}
}

if(unique_value)
{
++num;
}
}

avg /= SIZE_OF_DATASET;

cout << "The maximum number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << max << endl;
cout << "The average number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << avg << endl;
cout << "The number of unique values from 1 to: " << SIZE_OF_DATASET << " is: " << num << endl;

cout << "=== Ending Program ===\n" << endl;
return 0;
}

If you look at the code above and compare it to our earlier code you might not see very much difference, and you would be right because we have only changed a few lines of code. But even that small change has significantly changed how our code works behind the scenes. The only line which requires significant attention is the recursive call in the collatz function, "steps = collatz(n, steps + 1);". Starting from the first call, from main, of the collatz function, the variable "steps" is equal to zero and of course at the very end of that function we return it to the calling function. In the case of the main function, it passes in a value for n and receives back the appropriate value for n. Between the first calling of collatz and returning line we have the recursive call with what looks like an increment of steps. And in fact it is. The problem with the code above is that it lacks a condition to tell when we have finished computing the number of steps. If you want to include a few lines of code which prints the number of steps taken and the value of n you probably find out that we never get passed the first time that main calls the collatz function. We need to know when the value for n has reached one. If we were approaching this iteratively, in a loop, then we would have a while loop like before or perhaps a for loop. But remember, we are doing this recursively so we really only want to check if n equals one once, so we only need an if statement. Consider the following code:

#include <iostream>
using namespace std;

int collatz(int n, int steps)
{
if(n != 1)
{
if(n % 2 == 0)
{
n /= 2;
}

else
{
n = n * 3 + 1;
}

steps = collatz(n, steps + 1);
}

return steps;
}

int main(int argc, char *argv[])
{
cout << "=== Starting Program ===\n" << endl;

const int SIZE_OF_DATASET = 100;

int array_of_steps[SIZE_OF_DATASET];

for(int i = 1; i <= SIZE_OF_DATASET; ++i)
{
array_of_steps[i - 1] = collatz(i, 0);
}

int max = 0;
double avg = 0;
int num = 0;

for(int i = 0; i < SIZE_OF_DATASET; ++i)
{
if(array_of_steps[i] > max)
{
max = array_of_steps[i];
}

avg += array_of_steps[i];

bool unique_value = true;

for(int j = 0; j < i; ++j)
{
if(array_of_steps[i] == array_of_steps[j])
{
unique_value = false;
}
}

if(unique_value)
{
++num;
}
}

avg /= SIZE_OF_DATASET;

cout << "The maximum number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << max << endl;
cout << "The average number of steps from 1 to: " << SIZE_OF_DATASET << " is: " << avg << endl;
cout << "The number of unique values from 1 to: " << SIZE_OF_DATASET << " is: " << num << endl;

cout << "=== Ending Program ===\n" << endl;

return 0;
}

It should be stressed that recursion is a reasonably abstract concept which we will not revisit for a little while, but it is important to have exposure before jumping into something.

In general, functions are an important concept which allow us to do the same things in an easy and quick fashion, and they also let us do things like recursion which we would not be able to do without functions. Functions will appear in every one of the following lessons because they allow us to break large complex problems into small easier problems and they also allow us to do the same things over and over again without copy and pasting code in multiple places. In general, copy paste code is a bad idea because "in the real world" code gets changed quite often and if you do not update all of the code at the same time bugs will generally follow. When we use functions, we have a powerful way of changing multiple parts of a program by only changing one or two lines of code. Please practice functions by checking out some of the coding katas.