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

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 ${\left(\left|n\right|x\right)}^{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.

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!

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.

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`.