More on functions in C++

This page gives more examples of how functions are defined and used, and how a function can be defined in terms of itself.

1. Defining and using functions

Here is an example function.

double myfunc( int n , double x )  {
  double y;
  if (n > 0) {
    y = n * x;
  } else { 
    y = -n * x;
  }
  y = y * y;
  return y;
}

This is not meant to do anything useful, but you should at least see what it does. (It just computes ${(|n| x)}^{2}$ .) Note in particular,

The "local" variable y declared inside the function. This variable is local in the sense that it only exists in the body of the function, and can be called anything. Even if there is a variable called y somewhere else this will be a new y.
The return statement that returns a double value to whatever called the function.

Here is some simple code that uses the above function.

int main() {
  double z = 3.14159;
  int k;
  for (k=1; k<10; k++) {
    cout << myfunc( k , z ) << endl;
  }
  return 0;
}

Notice that the new defined function means myfunc( .. ) can be used in expressions, and returns an object of type "double". When such a function is called in this way a number of things happen.

All the data from the current position in the execution of main() is saved. (People usually say this data is "saved on the stack".)
The arguments are copied. This is just like = so it's like the computer would do n = k; x = z; except it is the n,x in myfunc and the k,z in main that's used.
The instructions in myfunc are carried out up to the return statement, and that value is remembered.
The function main() continues with the value obtained.

That's all there is to defining functions. The main thing to remember is that you must be careful when specifying the types of arguments and the return type. If it is wrong the compiler will complain. But the types can be anything at all, even something very complicated.

2. Functions that call themselves

Example.

Here is an example of a function that calls itself. In fact this code tries to compute the factorial function. It doesn't do a very good job, and it is worth experimenting with the program.

// fact.cpp (click here to download)

// Program for factorials
#include <iostream>

using namespace std;

/* function for exact factorial returning an integer */
int fact(int n) {
  if (n < 0) return 0;
  if (n == 0) return 1;
  return n * fact(n - 1);
} 

/* function for approximate factorial returning a double. */
double dfact(int n) {
  if (n < 0) return 0.0;
  if (n == 0) return 1.0;
  return n * dfact(n - 1);
} 

int main() {
  int n;
  cout << "Compute factorials to what maximum input?" << endl;
  cin >> n;
  cout << "Exact" << endl;
  for (int i = 0; i <= n; i++) {
    cout << i << "! = " << fact(i) << endl;
  }
  cout << "Approximate" << endl;
  for (int i = 0; i <= n; i++) {
    cout << i << "! = " << dfact(i) << endl;
  }
  return 0;
}

Using functions that call themselves is a popular and powerful technique, called recursion. It is important to "ground" this recursion somehow, making sure that there is a base case that can always be calculated, and that something gets smaller each time so that the recursion eventually bottoms out. That's done in this example with the "if" statements at the beginning of the function.

Example.

One problem with recursion is that it can be rather slow and wasteful of memory. Here is a better alternative for factorial that does not use recursion.

// fact2.cpp (click here to download)

// Program for factorials, same as fact.cpp except it does not use recursion
#include <iostream>

using namespace std;

/* function for exact factorial returning an integer */
int fact(int n) {
  if (n < 0) return 0;
  int ans = 1;
  for (int f = 1; f <= n; f++ ) {
    ans = ans * f;
  }
  return ans;
} 

/* function for approximate factorial returning a double. */
double dfact(int n) {
  if (n < 0) return 0.0;
  double ans = 1.0;
  for (int f = 1; f <= n; f++ ) {
    ans = ans * f; // f is converted to double
  }
  return ans;
} 

int main() {
  int n;
  cout << "Compute factorials to what maximum input?" << endl;
  cin >> n;
  cout << "Exact" << endl;
  for (int i = 0; i <= n; i++) {
    cout << i << "! = " << fact(i) << endl;
  }
  cout << "Approximate" << endl;
  for (int i = 0; i <= n; i++) {
    cout << i << "! = " << dfact(i) << endl;
  }
  return 0;
}

The main problem here, however, is that the factorial function grows too fast for int or even double to cope. The factorial function has exponential growth (in fact $n! = O (n^{n})$ and it's not possible to improve on this much). Problems with factorials and growth rates are typical of problems with functions has exponential growth.

Example.

To give an example of recursion and iteration when the growth rates are more reasonable, consider the calculation of Pascal's triangle mod 2. (The pattern obtained is very pretty!) The following program has the option of switching between the recursive method and the iterative method.

// ptriangle.cpp (click here to download)

// Program for Pascal's triangle mod 2
#include <iostream>

using namespace std;

/* function for n-choose-k mod 2 */
int ptriangle(int n, int k) {
  if (n < 0) return 0;
  if (k < 0) return 0;
  if (k > n) return 0;
  if (k == 0) return 1;
  if (k == n) return 1;
  return ( ptriangle( n - 1, k) + ptriangle( n - 1, k - 1 ) ) % 2;
} 

/* calculates the maximum number of times n is exactly divisible by 2 */
int number2s(int n) {
  int c = 0;
  while (n % 2 == 0 ) {
    n = n/2;
    c++;
  }
  return c;
}

/* iterative version of the function for n-choose-k mod 2 */
int ptrianglei(int n, int k) {
  if (n < 0) return 0;
  if (k < 0) return 0;
  if (k > n) return 0;
  if (k == 0) return 1;
  if (k == n) return 1;
  int p = 0;
  // calculate the number of times 2 divides n!
  for (int i=1; i<=n; i++) { p = p + number2s(i); }
  // subtract the number of times 2 divides k!(n-k)!
  for (int i=1; i<=k; i++) { p = p - number2s(i); }
  for (int i=1; i<=n-k; i++) {  p = p - number2s(i); }
  // if there were more 2s in n! than in k!(n-k)! the answer is even
  if (p>0) return 0; else return 1;
} 

int main() {
  int n,m,r;
  cout << "n-choose-m mod 2."  << endl;
  cout << "Enter 1 to use recursion or 0 to use iteration: ";
  cin >> r;
  if (r>=1) {
    cout << "Using recursion" << endl;
  } else {
    cout << "Using iteration" << endl;
  }
  cout << "Enter n m: ";
  cin >> n >> m;
  if (r>=1) {
    cout << n << " -choose- "<< m << " mod 2 = " << ptriangle(n,m) << " ";
  } else {
    cout << n << " -choose- "<< m << " mod 2 = " << ptrianglei(n,m) << " ";
  }
  cout << endl;
  cout << "Now compute full table to what maximum input?" << endl;
  cin >> n;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= i; j++) {
      if (r>=1) {
	cout << ptriangle(i,j) << " ";
      } else {
	cout << ptrianglei(i,j) << " ";
      } 
    }
    cout << endl;
  }
  return 0;
}

The recursive method is particularly slow here because every call of the function generates two new calls of the function for smaller n or k. If you experiment with it you will easily conjecture that the run time of the recursive method is $O (2^{n})$ . Incidentally, both methods can be improved but the above gives the general idea of the performance to be expected.

Example.

Here is a function defined recursively that computes the number of 2s in the prime factorization of $n!$ . (You saw how to do this iteratively in the last example.)

// numbertwos.cpp (click here to download)

// Program for number of 2s in prime factorisation of n!
#include <iostream>

using namespace std;

/* calculates the maximum number of times n is exactly divisible by 2 */
int number2s(int n) {
  int c = 0;
  while (n % 2 == 0 ) {
    n = n/2;
    c++;
  }
  return c;
}

/* calculates the maximum number of times n! is exactly divisible by 2 */
int number2sinfactorial(int n) {
  if (n < 1) return 0;
  if (n % 2 == 1) {
    return number2sinfactorial(n-1);
  } else {
    return number2s(n) + number2sinfactorial(n-2);
  } 
}

/* iterative method to calculate the maximum number of times n! is
   exactly divisible by 2 */
int number2sinfactoriali(int n) {
  if (n < 1) return 0;
  int p = 0;
  for (int i=1; i<=n; i++) {
    p = p + number2s(i);    
  }
  return p;
}

int main() {
  int n;
  cout << "Calculates the number of 2s in the prime factorization of n!" << endl;
  cout << "Enter n: ";
  cin >> n;
  cout << number2sinfactorial(n) << endl;
  return 0;
}

This time, the recursive method reasonably fast because every call of the function generates only one new call, but it runs out of memory for large inputs. (This is a problem you don't get with the iterative method.)

Thus recursion is a useful trick that sometimes makes functions very simple to write, but should only be used in cases where the recursion is rather shallow (because "deep recursion" runs out of memory very quickly) and when the computation times are reasonable. In particular be careful of any recusrion that generates two or more "sub calls" of your function for every one call.

Another possible issue with recursion is a technical one: how to define a function f using g, when the function g must be defined using f. In this case you should declare both functions in C++ first, before defining them. (Often the declaring and defining stages are taken together so the two get muddled up. Try not to be confused here.)

int f( int n ); // declaration of f

int g( int n ); // declaration of g

int f( int n ) {
  // definition of f, may use g
}

int g( int n ) {
  // definition of g, may use f
}

Advice: Although recursion is very simple, it can be costly in computer time and (especially) in memory. Don't use recursion unless you are sure that the number of nested-times the function needs to be called is comparitively small (maybe in the tens, hundreds at most?) and that recursion really is the best (clearest, simplest, easiest to read) solution to the problem at hand. But sometimes it really is!

3. Call by value vs call by reference

This has already been mentioned, but is an important feature that you need to know about. When a function is called, the value of the input is normally copied to the variable in the function. This means the function cannot change the value of any variables outside itself. It can only change one of its own copies of that value. This is called "call by value" in the jargon and is the clearest and safest approach.

Just occasionally you want a function that does change the actual variable. For example, you might want to define a function nextprime(n) that does not return a value but changes n to be the next prime bigger than its current value. This is called a side effect of calling a function. If handled carefully, side effects, especially "obvious" or "simple" side effects, are often useful. The solution to the problem is to use C++'s reference types, which were discussed earlier.

In this case, in C++ the syntax for declaring such a funtion is

void nextprime( int& n ) { .. }

Notice the ampersand (&) after the int. Then when executing nextprime(k) in some program, the machine makes the n in the nextprime function an "alias" for the k in the calling program. That way the nextprime function can change the value of k.

Note that you may get an error message if you now try to do nextprime(2) because the value 2 cannot be changed!

Here is the example in full.

// nextprime.cpp (click here to download)

#include <iostream>

using namespace std;

/* using call-by-reference replaces n 
 * with the least prime greater than n */
void nextprime(int& n) {
  if ( n < 1 ) { 
    n = 2;
    return;
  }
  while (true) {
    n++;
    bool isprime = true;
    for (int d=2; d<n; d++) {
      // if d is a divisor then n is not prime
      if (n % d == 0) {
	isprime = false;
	break;
      }
    }
    // if n is prime break out of the while loop
    if (isprime) break;
  }
}

int main() {
  int n = 1;
  while (n < 1000) { 
    // next, n is increased to the least prime greater than it
    nextprime(n); 
    cout << n << " ";
  }
  cout << endl;  
}

Call by reference is useful, but generally speaking it is probably best avoided except when really necessary, because side-effects sometime obscure what is happening. In the case just given, writing the function as int nextprime(int n) { .. } and in the calling program using k = nextprime(k), would have been clearer.

Having said that, there are cases when it is not possible to avoid it.

It may be that two kinds of output from a function are required (e.g. a value, and possibly an error message to say the value couldn't be computed for some reason). In this case, one solution would be to have the function returning a bool value (whether it was successful or not), and both the actual value, and any error message as well, might be returned using call by reference. We will use simple examples of this kind later. Other solutions to this problem use sophisticated additional features of C++ that will not be covered here.
There are occasions when the time taken to copy a very large item of data as an input to a function is far too costly, in which case call-by-reference avoids the copying time. We will see examples of this later.

4. "const" variables

This is a short lookahead to some slightly more advanced stuff we will occasionally need later. The keyword const means "is a constant", i.e. indicates that you promise not to change its value. For example,

const double pi = 3.14159;

The advantages of declaring variables as const are:

If you first promise not to change a value and then accidentally do so, C++ will spot this as a bug and ask you to fix it, rather that allowing it to happen and having your program work in an erratic way.
If C++ knows a variable cannot change its value it sometimes can generate code that is more efficient. Using const allows C++ to "optimise" your program in the best way it can.

The keyword const is often used for constant inputs to functions. Thus a different version of the "nextprime" example may be written as int nextprime(const int& n) { .. } to indicate that you want to use call by reference on the input n but promise that its value won't be changed. This time k = nextprime(2); will work, even though 2 is passed by reference, since C++ now knows you don't plan to change the value of 2 to something else. For reasons that are probably not so clear at this stage, this style of work is very useful (mainly for other types rather than "int").

Advice: good programmers use const throughout, but beginners need not worry too much at this stage. In this module, when it is needed, you will be told exactly when and how to use const.