0.1 Functions and References

Up until now, we had everything in our main function. However, you may have noticed that dumping everything in there is not efficient nor scalable. This is where functions kick in.

0.1.1 Functions

As always, let’s start with definition.

Functions are specially useful as we can use it multiple times just by calling them instead of copy and pasting every time we need them. Functions in C++ generally have the following format.

1outputDataType functionName(parameters) { 
2    code block 
3    return outputValue; 
4}

Looking at a bare main function, we can see that we have int since the main function returns an integer value like \(0\). Since no arguments are taken in a bare main function, we have empty parenthesis. There are some functions that do not return any value. In that case, we would be using void. Moreover to use a function, we need to call it. Below is a quick example.

1#include <iostream> 
2 
3void helloWorld() { 
4    std::cout << "Hello, World!\n"; 
5} 
6 
7int main() { 
8    helloWorld(); 
9    helloWorld(); 
10    helloWorld(); 
11    return 0; 
12}

In the example above, we have our helloWorld function that prints the text “Hello, World!” to the console. The type is void since it does not return any values. By calling the function three times in main, we don’t have to manually write long texts every time!

Hello, World! 
Hello, World! 
Hello, World!

Below is a more practical use of simple functions for basic mathematical operations.

1#include <iostream> 
2 
3int add(int a, int b) { 
4    return a + b; 
5} 
6 
7int subtract(int a, int b) { 
8    return a - b; 
9} 
10 
11int multiply(int a, int b) { 
12    return a * b; 
13} 
14 
15double divide(double a, double b) { 
16    return a / b; 
17} 
18 
19int mod(int a, int b) { 
20    return a % b; 
21} 
22 
23int main() { 
24    std::cout << "1 + 2 = "    << add(1, 2)      << std::endl; 
25    std::cout << "3 - 4 = "    << subtract(3, 4) << std::endl; 
26    std::cout << "5 * 6 = "    << multiply(5, 6) << std::endl; 
27    std::cout << "7 / 8 = "    << divide(7, 8)   << std::endl; 
28    std::cout << "10 mod 9 = " << mod(10, 9)     << std::endl; 
29 
30    std::cout << "((1 + 2) * 4) mod 10 = " 
31              << mod(multiply(add(1, 2), 4), 10) << std::endl; 
32 
33    return 0; 
34}

Each function will take in the values \(a\) and \(b\) to perform the dedicated task. After declaring the functions, we can call them in the main function to display them. Many times it is better to make the functions declare a value rather than print directly to the console for reusability. As shown in the last example, we can call a function as an input of different function.

1 + 2 = 3 
3 - 4 = -1 
5 * 6 = 30 
7 / 8 = 0.875 
10 mod 9 = 1 
((1 + 2) * 4) mod 10 = 2

Another very important technique that allows us to break down hard problems into simpler problems is recursion.

Recursion

As always, let’s get started with definition.

The technique is rather straight forward when we look at some examples.

1#include <iostream> 
2 
3int main() { 
4    int n; 
5    int sum = 0; 
6 
7    std::cout << "Enter n: "; 
8    std::cin >> n; 
9 
10    for (int i = 1; i <= n; i++) { 
11        sum += i; 
12    } 
13    std::cout << "Sum: " << sum << "\n"; 
14 
15    return 0; 
16}

Enter n: 3 
Sum: 6

Enter n: 10 
Sum: 55

1#include <iostream> 
2 
3int sum(int n) { 
4    if (n > 0) { 
5        return n + sum(n-1); 
6    } else { 
7        return 0; 
8    } 
9} 
10 
11int main() { 
12    int n; 
13 
14    std::cout << "Enter n: "; 
15    std::cin >> n; 
16 
17    std::cout << "Sum: " << sum(n) << "\n"; 
18 
19    return 0; 
20}

Enter n: 3 
Sum: 6

Enter n: 10 
Sum: 55

For a simple problem like the exercise above, the could be a more simple solution than recursion. However, the technique will come very handy when the problem gets harder. Now with the ideas of functions in mind, we can continue with another important topic of references.

0.1.2 References

One of the primary goals of writing codes for competitive programming is efficiency. Indeed most, if not all, codes written for competitions are not maintained as the main purpose is to solve problems efficiently [CS02-3]. Moreover, it is important that your program is fast enough to execute under the time limit. One way to achieve this is by preventing making of copies, and this is where reference comes in.

References and pointers serves different purposes, although they look similar. Indeed, references are using pointers behind the scenes. However there are much more topics to discuss for pointers, and let’s focus on references for now for the purpose of this note.

Let’s take a look at a quick example.

1#include <iostream> 
2 
3int main() { 
4    int a = 5; 
5    int& ref = a; // reference to a 
6 
7    std::cout << "ref: " << ref << "\n"; 
8    std::cout << "a:   " << a   << "\n"; 
9    ref++; 
10    std::cout << "After adding 1 to ref\n"; 
11    std::cout << "ref: " << ref << "\n"; 
12    std::cout << "a:   " << a   << "\n"; 
13 
14    return 0; 
15}

When declaring a reference, we use the ampersand &. Technically int& ref and int &ref does the same thing, but let’s use the first one to be consistent. Here, ref is our reference to a. Unlike declaring int ref = a;, which creates a copy of a, reference become an alias of a that we can use to edit a. Below is the output from running the code.

ref: 5 
a:   5 
After adding 1 to ref 
ref: 6 
a:   6

As you can see above, incrementing ref also increments a as they refer to the same object. One of the most common application of reference is passing arguments in functions [CS02-5]. Consider the example below.

1#include <iostream> 
2 
3void increment1(int a) { 
4    a++; 
5    std::cout << a << "\n"; 
6} 
7 
8void increment2(int& a) { 
9    a++; 
10    std::cout << a << "\n"; 
11} 
12 
13int main() { 
14    int x = 5; 
15    increment1(x); 
16    x = 5; 
17    increment2(x); 
18 
19    return 0; 
20}

In the example above, the difference in performance between the two functions are trivial. However, the first function creates a local copy of \(x\) while the second one doesn’t. Passing arguments by reference can be especially helpful when we are dealing with large objects. Indeed, copying large objects won’t be as efficient as just indirectly adjusting the original value.

5 
6

Another use case of reference in arguments is that we can directly change the value. Let’s tweak our code above to further elaborate on the point above.

1#include <iostream> 
2 
3void increment1(int a) { 
4    a++; 
5} 
6 
7void increment2(int& a) { 
8    a++; 
9} 
10 
11int main() { 
12    int x = 5; 
13    increment1(x); 
14    std::cout << x << "\n"; 
15 
16    x = 5; 
17    increment2(x); 
18    std::cout << x << "\n"; 
19 
20    return 0; 
21}

This time, we have cout in the main function. As mentioned previously, the first function creates a local copy and adjust the copy. Meaning, the original values does not change. However, the second function changes the original value. Therefore, the values \(5\) and \(6\) must be the outputs.

5 
6

References are frequently used for efficiency and cleaner code. Before getting into exciting data structures and algorithms, let’s discuss arrays and vectors.