06. Functions

A function is a named piece of code that can be called many times and can be tested on its own. In OSN, functions are used to break a problem into small parts, each of which is easy to confirm as correct.

The shape of a function

int kuadrat(int x) {
    return x * x;
}

int main() {
    cout << kuadrat(5) << "\n";   // 25
    return 0;
}

Its parts:

What happens when kuadrat(5) ("square") is called, in order:

1. The value 5 is copied into the parameter x.
2. Execution of main pauses, and execution moves into kuadrat.
3. return x * x; computes 25 and sends it back.
4. Execution returns to main, exactly at the call site, and the whole expression kuadrat(5) is replaced by the value 25.

That is why a function call may be placed anywhere a value may appear: inside cout, inside if, even as the input of another function, as in kuadrat(kuadrat(2)).

return also immediately ends the function. Any line after a return that has already run will not be executed:

int uji(int n) {
    if (n < 0) return -1;      // exit immediately
    return n * 2;              // only reached if n >= 0
}

This property is used to exit a checking function early, and you will see it often in bool prima(...) in this chapter's homework.

A function must be written above the place where it is called, or be declared first:

int kuadrat(int x);      // declaration (prototype)

int main() {
    cout << kuadrat(5) << "\n";
}

int kuadrat(int x) {     // definition, may come below
    return x * x;
}

Functions without a return value

If a function only does something (usually printing), its type is void:

void garis(int panjang) {
    for (int i = 0; i < panjang; i++) cout << "-";
    cout << "\n";
}

Multiple parameters

int maksimum(int a, int b) {
    return (a > b) ? a : b;
}

bool di_dalam(int x, int bawah, int atas) {
    return x >= bawah && x <= atas;
}

Functions that return bool are very useful: the name explains the intent of the condition, so if (di_dalam(x, 1, 100)) ("is inside") reads immediately.

Local variables and scope

A variable created inside a function only lives inside that function.

void f() {
    int x = 10;     // exists only inside f
}

int main() {
    // cout << x;   // error: 'x' was not declared in this scope
}

The same applies to a { ... } block inside an if or for: the variable i in for (int i = ...) does not exist after the loop finishes.

Because the names do not collide, two functions may use the same variable name without interfering with each other. int i inside f and int i inside main are two completely different boxes.

The opposite is a global variable: a variable written outside every function, so it can be read and changed from anywhere.

const int MAKS = 100005;
int a[MAKS];        // global: shared by all functions
int n;

int jumlah() {
    int total = 0;  // local: exists only while this function runs
    for (int i = 0; i < n; i++) total += a[i];
    return total;
}

In large software, global variables are avoided because they make code hard to trace. In contests, they are exactly what is used for large arrays and for values that every function needs — the code gets shorter and no large vector is copied back and forth.

Copied values and references

By default, parameters are passed as copies. Changing one inside the function does not change the original variable:

void tambah_salah(int x) { x += 100; }

int a = 5;
tambah_salah(a);
cout << a << "\n";      // still 5

The & sign makes a parameter a reference — another name for the original variable:

void tambah_benar(int &x) { x += 100; }

int a = 5;
tambah_benar(a);
cout << a << "\n";      // 105

The difference can be read like this: without &, the function receives a photocopy; with &, the function receives the original box.

A reference is the way to return more than one value from a function, because return can only return one:

void bagi(int a, int b, int &hasil, int &sisa) {
    hasil = a / b;
    sisa = a % b;
}

Recursion

A function may call itself. This is called recursion, and every recursive function needs two things:

1. Base case — the stopping condition, with no further calls.
2. Shrinking step — a call on a smaller problem.

long long faktorial(int n) {
    if (n <= 1) return 1;          // base case
    return n * faktorial(n - 1);   // shrinking step
}

Tracing faktorial(4):

faktorial(4) = 4 * faktorial(3)
             = 4 * 3 * faktorial(2)
             = 4 * 3 * 2 * faktorial(1)
             = 4 * 3 * 2 * 1
             = 24

What makes recursion work is the call stack: each call keeps its own local variables and the place it must return to. While faktorial(4) is waiting for faktorial(3), both are in memory at the same time, each with its own n:

faktorial(4)   n = 4   waiting for faktorial(3)
  faktorial(3) n = 3   waiting for faktorial(2)
    faktorial(2) n = 2 waiting for faktorial(1)
      faktorial(1) n = 1 -> return 1
    return 2 * 1 = 2
  return 3 * 2 = 6
return 4 * 6 = 24

How to read it: go down until you hit the base case, then come back up while multiplying. The top half is "breaking into smaller problems", the bottom half is "combining the answers".

When recursion becomes slow

The Fibonacci function is very easy to write recursively:

long long fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

But try fib(45): your computer will think for a very long time. The reason becomes visible when the calls of fib(5) are drawn as a tree:

                    fib(5)
              /              \
          fib(4)             fib(3)
         /      \           /      \
     fib(3)    fib(2)    fib(2)   fib(1)
     /    \    /    \    /    \
 fib(2) fib(1) fib(1) fib(0) fib(1) fib(0)
  /  \
fib(1) fib(0)

fib(3) appears twice, fib(2) three times, fib(1) five times — every branch is recomputed from scratch each time. The number of calls grows like the Fibonacci sequence itself:

Every increase of n by 5 multiplies the work by about eleven.

Compare with the loop version, which keeps only the last two values:

long long fib_cepat(int n) {
    long long a = 0, b = 1;
    for (int i = 0; i < n; i++) {
        long long c = a + b;
        a = b;
        b = c;
    }
    return a;
}

The difference is not small: for n = 45, the recursive version makes 3.67 billion function calls (a few seconds to a dozen or more seconds, depending on the computer), while the loop version needs only 45 iterations and finishes before you notice. Both print the same answer, 1134903170.

What the loop version drops is not the recursion but the repeated work. This problem of "the same computation being done many times" is what dynamic programming solves in Chapter 13 — and this chapter's homework challenge is the first half-step toward it.

Why functions matter in contests

• Testing small parts. bool prima(long long n) can be tried with 1, 2, 9, and 97 before being used in a large problem.
• Fewer typing mistakes. Logic used three times only needs to be written once.
• Keeping code readable when time runs short. if (prima(x)) is quicker to understand than seven lines of loop in the middle of main.

Homework

Most common mistakes

OSN tips

Functions are a testing tool, not a tidying tool. In contests, the biggest benefit of functions is not tidy code but the ability to test one part separately. bool prima(long long n) can be tried with 1, 2, 9, and 97 in ten seconds; the same logic embedded in the middle of main can only be tested through the whole problem.

Recursion has a depth limit. Every function call stores its data on the stack, and a stack that runs out makes the program stop by itself — judged as Runtime Error, not Wrong Answer. Recursion 10⁶ calls deep almost certainly fails. If the depth is proportional to N and N can reach 10⁵ or more, turn the recursion into a loop.

Recursion without a base case will not stop. Every recursive function must have two parts: a base case that stops, and a call that moves toward the base case. If either is missing, the symptom is the same as an infinite loop.

Count how many times the function is called first. Recursion that calls itself twice at every level makes the number of calls multiply. The naive fib(45) needs 3.67 billion calls — compare that with the rule of 10⁸ operations per second in Chapter 05. If the number is unreasonable, the solution really has to be replaced, not slightly optimized.

Large parameters are passed by reference. Passing a vector of length 10⁶ as a copy means copying 10⁶ elements on every call. The & sign on the parameter removes that cost entirely. This only becomes noticeable from Chapter 07 on, but the habit is formed now.

Some library functions that save typing time:

Summary

• A function has a return type, a name, parameters, and return. void is for functions that do not return a value.
• return immediately ends the function; the call is replaced by the returned value.
• Local variables only live inside the block where they were created. In contests, large arrays are made global.
• Without & a parameter is received as a copy; with & the function works on the original variable — used to return more than one value and to avoid copying large vectors.
• A recursive function must have a base case and a shrinking step.
• Recursion that recomputes the same subproblems can be very slow; storing the results (memoization) is the entry point to Chapter 13.

OSN-style exercises

The three problems below ask for the answer to be broken into functions. Write the functions first, test them yourself with a few numbers, and only then connect them to main.

Starter code for all three is in exercises/06/osn/.

Problem 1 — Digital Root

The digital root of a number is obtained by summing all its digits, then repeating the same step on the result, until only a single digit remains.

Input format. The first line contains an integer T, the number of test cases. Each of the next T lines contains one integer N.

Output format. T lines containing the digital root of each N.

Constraints.

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10¹⁸

Sample input

3
9875
9
1000000000000000000

Sample output

2
9
1

Explanation. For 9875: 9 + 8 + 7 + 5 = 29, then 2 + 9 = 11, then 1 + 1 = 2. A number that already has a single digit is its own answer.

Starter code: exercises/06/osn/01-akar-digit.cpp

Problem 2 — Tower of Hanoi

There are three pegs named A, B, and C. Peg A holds N disks of different sizes, the largest at the bottom and the smallest at the top. All the disks must be moved to peg C under two rules:

• a single move may move only one disk, namely the top disk of one of the pegs;
• a larger disk may not be placed on top of a smaller disk.

Print the sequence of moves that completes the arrangement with as few moves as possible.

Input format. One line containing an integer N.

Output format. The first line contains the number of moves. Each following line contains two peg letters: the source peg and the destination peg, separated by one space.

Constraints. 1 ≤ N ≤ 15.

Sample input

2

Sample output

3
A B
A C
B C

Explanation. The small disk is moved to B so the large disk can move to C, then the small disk follows. The minimum number of moves is always 2^N − 1.

Starter code: exercises/06/osn/02-menara-hanoi.cpp

Problem 3 — Perfect Numbers

The proper divisors of a number are all its positive factors except the number itself. A number is called perfect if the sum of its proper divisors equals the number, abundant if the sum is larger, and deficient if the sum is smaller.

Input format. The first line contains an integer T. Each of the next T lines contains one integer N.

Output format. T lines containing SEMPURNA (perfect), BERLEBIH (abundant), or KURANG (deficient).

Constraints.

• 1 ≤ T ≤ 100
• 1 ≤ N ≤ 10⁹

Sample input

4
6
12
8
1

Sample output

SEMPURNA
BERLEBIH
KURANG
KURANG

Explanation. The proper divisors of 6 are 1, 2, and 3, which sum to 6. The proper divisors of 12 are 1, 2, 3, 4, 6, which sum to 16 — larger than 12. The proper divisors of 8 are 1, 2, 4, summing to 7. The number 1 has no proper divisors at all, so its sum is 0.

Starter code: exercises/06/osn/03-bilangan-sempurna.cpp

Confused, or already done? Open the homework solutions page.