C Programming For Beginners (2015)
CHAPTER 7
Functions
In this chapter, we will explain the following:
§ Why functions are important in programming
§ How to write functions
§ What happens when a function is called
§ Where functions are placed in a program
§ Some important concepts relating to functions using several examples
7.1 About Functions
So far, all our programs have consisted of a single function called main. However, we have made use of predefined C functions such as printf, scanf, strcpy and fopen. When we run a program, it starts executing with the first statement in main and ends when it reaches the last statement.
As we have seen, it is possible to write reasonably useful programs with only main. However, there are many limitations to this approach. The problem to be solved may be too complex to be solved with one function. We may need to break it up into subproblems and try to solve each of these individually. It would be impractical to solve all the subproblems in one function. It might be better to write a separate function to solve each subproblem.
Also, we may want to reuse the solution to common problems. It would be difficult to reuse a solution if it is part of the solution to a bigger problem. For example, if we need the highest common factor (HCF) of two numbers in several places, it would be best to write a routine which works out the HCF of two given numbers; we call this routine whenever we need to find the HCF of two numbers.
A well-written function performs some well-defined task; for example, skip a specified number of lines in the output or arrange some numbers in ascending order. However, quite often, a function also returns a value; for example, calculate the salary of a person and return the answer or play one turn of a game and return the score for that turn. The value returned is normally used at the point from which the function was called.
Previously, we used the string function strcmp which returns a value which tells us the result of comparing two strings. And we have used getchar and getc to return the next character in the input.
We are now ready to learn how to write our own functions (called user-defined functions) and we will see several examples in the rest of this book.
7.2 skipLines
We have seen that we can use \n in a printf statement to print a blank line. For example, the statement
printf("%d\n\n%d\n", a, b);
will print a on one line, skip one line and print b on the next line. We can usually skip any number of lines by writing the appropriate number of \n’s in the printf statement.
Sometimes we may want to skip 3 lines, sometimes 2 lines, sometimes 5 lines, and so on. It would be nice if there was a statement we could use to skip any number of lines we want. For instance, to skip 3 lines, we should be able to write
skipLines(3);
and to skip 5 lines, we write
skipLines(5);
What we want is a function called skipLines which takes an integer argument (n, say) and skips n lines. In C, we write this function as follows:
void skipLines(int n) {
for (int h = 1; h <= n; h++)
printf("\n");
}
Observe that the structure of the function is similar to the structure of main. It consists of a header (the first line, except { ) followed by the body enclosed in braces. The word void indicates that the function does not return a value and (int n) defines n as an integer parameter. When the function is called, we must supply it with an integer value to match the parameter n.
This is the definition of the function skipLines. We use the function by calling it when we write, in main, a statement such as:
skipLines(3);
(A function can normally be called from any other function but, to focus our discussion, we will assume it is called from main.)
We say that we call (or invoke) the function with the argument. (In this book, we use the term ‘parameter’ when referring to the definition of the function and the term ‘argument’ when the function is called. Others use the terms interchangeably.) The “call” is executed as follows:
§ The value of the argument is determined. In this case, it is just the constant 3 but, in general, it could be an expression.
§ The value is copied to a temporary memory location. This location is passed to the function where it is labelled with the name of the parameter, n. In effect, the parameter variable n is set to the value of the argument. We can picture this as follows:
§
n |
3 |
§ The body of the function is executed. In this case, since n is 3, the for loop becomes
§ for (int h = 1; h <= 3; h++)
§ and it prints \n three times.
§ When the function is finished, the location containing the argument is discarded and control returns to main to the statement following skipLines(3).
Note that we can get skipLines to print a different number of blank lines by supplying a different argument when we call it.
When the value of an argument is passed to a function, we say the argument is passed “by value”. In C, arguments are passed “by value”.
7.3 A Program with a Function
We write Program P7.1 to show how skipLines fits into a complete program.
Program P7.1
#include <stdio.h>
int main() {
void skipLines(int);
printf("Sing a song of sixpence\n");
skipLines(2);
printf("A pocket full of rye\n");
} //end main
void skipLines(int n) {
for (int h = 1; h <= n; h++)
printf("\n");
} //end skipLines
When we wish to use a variable in main, we must declare the variable in main. Similarly, if we want to use skipLines in main, we must tell C about it using what is called a function prototype. A function prototype is a declarationpretty much like the function header. In the program, we use the prototype:
void skipLines(int);
The prototype describes the function by stating the return type of the function (void, in this case), the name of the function (skipLines) and the type(s) of any argument(s) (int, in this example). If you wish, you can write a variable after the type, as in:
void skipLines(int a);
This variable will be used by the compiler only if it needs to generate an error message. In this book, we will write our prototypes using the type only.
Note that the function prototype is followed by a semicolon whereas the function header is followed by a left brace.
As another example, the prototype
int max(int, int);
says that max is a function which takes two integer arguments and returns an integer value.
A common mistake made by beginners is to forget to write the function prototype. However, that is not a big problem. If you forget, the compiler will remind you of it. It is like forgetting to declare a variable—the compiler will tell you about it. You just fix it and move on.
In terms of layout, the functions, including main, which make up a C program can appear in any order. However, it is customary to place main first where the overall logic of the program can be easily seen.
We emphasize that this program is for illustrative purposes only since the output could be produced more easily with this:
printf("Sing a song of sixpence\n\n\n");
printf("A pocket full of rye\n");
7.3.1 The Function Header
In our example, we used the function header
void skipLines(int n)
In general, the function header consists of:
§ a type (such as void, int, double, char), which specifies the type of value returned by the function. If no value is returned, we use the word void. The function skipLines does not return a value so we use void.
§ the name we make up for the function, skipLines in the example.
§ zero or more parameters, called the parameter list, enclosed in brackets; one parameter n of type int is used in the example. If there are no parameters, the brackets must still be present, as in printHeading().
The function header is followed by the left brace of the body.
Parameters are specified in the same way variables are declared. In fact, they really are declarations. The following are all valid examples of headers of void functions:
void sample1(int m, int n) |
//2 parameters |
void sample2(double a, int n, char c) |
//3 parameters |
void sample3(double a, double b, int j, int k) |
//4 parameters |
Each parameter must be declared individually and two consecutive declarations are separated by a comma. For example, it is invalid to write
void sample1(int m, n) //not valid; must write (int m, int n)
Shortly, we will see examples of functions which return a value.
7.3.2 How a Function Gets Its Data
A function is like a mini program. In the programs we have written, we have stated what data must be supplied to the program, what processing must take place and what the output (results) should be. We must do the same when we write a function.
When we write a function header, we use the parameter list to specify what data must be supplied to the function when it is called. The list specifies how many data items, the type of the each item and the order in which they must be supplied.
For example, we wrote skipLines with an integer parameter n; this says that an integer value must be supplied to skipLines when it is called. When skipLines is called, the argument supplied becomes the specific value of n and the function is executed assuming that n has this value. In the call skipLines(3), the argument 3 is the data that skipLines needs to perform its job.
It is worth emphasizing that main gets its data by using scanf, among other functions, to read and store the data in variables. On the other hand, a function gets its data when it is called. The variables in the parameter list are set to the values of the corresponding arguments used in the call. For example, when we write the header
void sample(int n, char c, double b)
we are saying that, when we call sample, we must do so with 3 arguments: the first must be an int value, the second a char value and the third a double value.
Assuming that num is int, ch is char and x is double, the following are all valid calls to sample:
sample(25, 'T', 7.5);
sample(num, 'A', x);
sample(num, ch, 7); //an int argument can match a double parameter
sample(num + 1, ch, x / 2.0);
If, when a function is called, the type of an argument is not the same as the corresponding parameter, C tries to convert the argument to the required type. For example, in the call
sample(num, 72, 'E');
the value 72 is converted to char and the parameter c is set to 'H' (since the code for H is 72); the numeric value of 'E' (which is 69) is converted to the double value 69.0 and the parameter b is set to 69.0.
If it is not possible to convert the argument to the required type, you will get a “type mismatch” error, as in the call
sample(num, ch, "hi"); // error - cannot convert string to double
You will also get an error if you do not supply the required number of arguments, as in
sample(num, x); // error - must have 3 arguments
7.4 max
Finding the larger of two values is something we need to do sometimes. If a and b are two numbers, we can set the variable max to the larger of the two with this:
if (a > b) max = a;
else max = b;
If the numbers are equal, max will be set to b (the else part will be executed). We can, of course, write this statement every time we want to get the larger of two values. But this will become clumsy and awkward. It will be more convenient and readable if we can simply write something like
big = max(a, b);
or even
printf("The bigger is %d\n", max(a, b));
We can, if we write the function max as follows:
int max(int a, int b) {
if (a > b) return a;
return b;
}
The first line (except { ) is the function header. It consists of
§ The word int, indicating that the function returns an integer value.
§ The name we make up for the function, max in the example.
§ One or more parameters, called the parameter list, enclosed in brackets; two parameters a and b of type int are used in the example.
The body of the function is the part from { to }. Here, we use the if statement to determine the larger of a and b. If a is bigger, the function “returns” a; if not, it returns b.
In C, a function “returns a value” by using the return statement. It consists of the word return followed by the value to be returned. The value is returned to the place at which the function was called.
To show how max fits into an overall program and how it can be used, we write Program P7.2 which reads pairs of integers and, for each pair, prints the larger of the two. The program ends when the user types 0 0.
Program P7.2
#include <stdio.h>
int main() {
int n1, n2;
int max(int, int);
printf("Enter two whole numbers: ");
scanf("%d %d", &n1, &n2);
while (n1 != 0 || n2 != 0) {
printf("The bigger is %d\n", max(n1, n2));
printf("Enter two whole numbers: ");
scanf("%d %d", &n1, &n2);
}
} //end main
int max(int a, int b) {
if (a > b) return a;
return b;
} //end max
The following is a sample run of P7.2:
Enter two whole numbers: 24 33
The bigger is 33
Enter two whole numbers: 10 -13
The bigger is 10
Enter two whole numbers: -5 -8
The bigger is -5
Enter two whole numbers: 0 7
The bigger is 7
Enter two whole numbers: 0 0
In order to call max from main, we must “declare” max in main using the function prototype
int max(int, int);
This says that max takes two integer arguments and returns an integer value.
The variables n1 and n2, declared in main, are considered as belonging to main.
When the program is run, suppose n1 is 24 and n2 is 33. When the function is called with max(n1, n2) from within printf, the following occurs:
§ The values of the arguments n1 and n2 are determined. These are 24 and 33, respectively.
§ Each value is copied to a temporary memory location. These locations are passed to the function max where 24 is labelled with a, the first parameter, and 33 is labelled with b, the second parameter. We can picture this as follows:
§
a |
24 |
b |
33 |
§ The if statement is executed; since a (24) is not greater than b (33), control goes to the statement return b; and 33 is returned as the value of the function. This value is returned to the place from which max was called (the printf statement).
§ Just before the function returns, the locations containing the arguments are thrown away. The value returned by max (33, in our example) replaces the call to max. Thus, max(n1, n2) is replaced by 33 and printf prints
§ The bigger is 33
When a function returns a value, it makes sense for this value to be used in a situation where a value is required. Above, we printed the value. We could also assign the value to a variable, as in
big = max(n1, n2);
or use it as part of an expression, as in
ans = 2 * max(n1, n2);
What does not make sense is to use it in a statement by itself, thus:
max(n1, n2); //a useless statement
Here, the value is not being used in any way, so the statement makes no sense at all. It is the same as if we had written a number on a line by itself, like this
33; //a useless statement
Think carefully when you call a function which returns a value. Be very clear in your mind what you intend to use the value for.
As written, max returns the larger of two integers. What if we want to find the larger of two double numbers? Could we use max? Unfortunately, no. If we called max with double values as arguments, we may get strange results when a double number is assigned to an int parameter.
On the other hand, if we wrote max with double parameters and double return type, it would work for both double and int arguments, since we can assign an int value to a double parameter without losing any information.
Note, however, that if we call max with two character arguments, it would work by returning the larger of the two codes. For example, max('A', 'C') will return 67, the code for C.
Exercise: Write functions to return the smaller of two integers and two floating-point numbers.
7.5 Print the Day
Let us write a program which requests a number from 1 to 7 and prints the name of the day of the week. For example, if the user enters 5, the program prints Thursday. Program P7.3 does the job using a series of if...elsestatements.
Program P7.3
#include <stdio.h>
int main() {
int d;
printf("Enter a day from 1 to 7: ");
scanf("%d", &d);
if (d == 1) printf("Sunday\n");
else if (d == 2) printf("Monday\n");
else if (d == 3) printf("Tuesday\n");
else if (d == 4) printf("Wednesday\n");
else if (d == 5) printf("Thursday\n");
else if (d == 6) printf("Friday\n");
else if (d == 7) printf("Saturday\n");
else printf("Invalid day\n");
}
Now suppose that printing the name of a day of the week was a small part of a much larger program. We wouldn’t want to clutter up main with this code nor would we want to re-write this code every time we needed to print the name of a day. It would be much nicer if we could write printDay(n) and get the appropriate name printed. We would be able to do this if we write a function printDay to do the job.
The first thing to ask is what information does printDay need to do its job. The answer is that it needs the number of the day. This immediately suggests that printDay must be written with the number of the day as a parameter. Apart from this, the body of the function will contain essentially the same code as Program P7.3. Also, printDay does not return a value so its “return type” is void.
void printDay(int d) {
if (d == 1) printf("Sunday\n");
else if (d == 2) printf("Monday\n");
else if (d == 3) printf("Tuesday\n");
else if (d == 4) printf("Wednesday\n");
else if (d == 5) printf("Thursday\n");
else if (d == 6) printf("Friday\n");
else if (d == 7) printf("Saturday\n");
else printf(“Invalid day\n”);
}
Tip: When we write the function, we can use any variable name we want for the parameter. We never have to worry about how the function will be called. Many beginners mistakenly believe that if the function is called with printDay(n), the parameter in the header must be n. But that cannot be true since it could be called with printDay(4) or printDay(n) or printDay(j) or even printDay(n + 1). The choice is up to the calling function.
All we need to know is that whatever the value of the argument, that value will be assigned to d (or whatever variable we happen to use as the parameter) and the function will be executed assuming the parameter (d, in our case) has that value.
We now re-write Program P7.3 as P7.4 to illustrate how the function fits into an overall program and how it can be used.
Program P7.4
#include <stdio.h>
int main() {
int n;
void printDay(int);
printf("Enter a day from 1 to 7: ");
scanf("%d", &n);
printDay(n);
} //end main
void printDay(int d) {
if (d == 1) printf("Sunday\n");
else if (d == 2) printf("Monday\n");
else if (d == 3) printf("Tuesday\n");
else if (d == 4) printf("Wednesday\n");
else if (d == 5) printf("Thursday\n");
else if (d == 6) printf("Friday\n");
else if (d == 7) printf("Saturday\n");
else printf("Invalid day\n");
} //end printDay
Now that we have delegated the printing to a function, notice how main is much less cluttered. However, we do have to write the function prototype for printDay in main so that printDay can be called from main. Here is the prototype:
void printDay(int);
As with all C programs, execution begins with the first statement in main. This prompts the user for a number and the program goes on to print the name of the day by calling the function printDay.
A sample run is:
Enter a day from 1 to 7: 4
Wednesday
In main, suppose n has the value 4. The call printDay(n) is executed as follows:
§ The value of the argument n is determined. It is 4.
§ The value 4 is copied to a temporary memory location. This location is passed to the function printDay where it is labelled with the name of the parameter, d. In effect, d is set to the value of the argument.
§ The body of the function is executed. In this case, since d is 4, the statement printf("Wednesday\n") will be executed.
§ After printing Wednesday, the function is finished. The location containing the argument is discarded and control returns to main to the statement following the call printDay(n). In this case, there are no more statements so the program ends.
7.6 Highest Common Factor
In Chapter 5, we wrote Program P5.2 which read two numbers and found their highest common factor (HCF). You should refresh your memory by taking a look at the program.
It would be nice if, whenever we want to find the HCF of two numbers (m and n, say), we could make a function call hcf(m, n) to get the answer. For instance, the call hcf(42, 24) would return the answer 6. To be able to do this, we write the function as follows:
//returns the hcf of m and n
int hcf(int m, int n) {
while (n != 0) {
int r = m % n;
m = n;
n = r;
}
return m;
} //end hcf
The logic for finding the HCF is the same as that used in program P5.2. The difference here is that values for m and n will be passed to the function when it is called. In P5.2, we prompted the user to enter values for m and n and fetched them using scanf.
Suppose the function is called with hcf(42, 24). The following occurs:
§ Each of the arguments is copied to a temporary memory location. These locations are passed to the function hcf where 42 is labelled with m, the first parameter, and 24 is labelled with n, the second parameter. We can picture this as:
§
m |
42 |
n |
24 |
§ The while loop is executed, working out the HCF. On exit from the loop, the HCF is stored in m, which will contain 6 at this time. This is the value returned by the function to the place from where it was called.
§ Just before the function returns, the locations containing the arguments are thrown away; control then returns to the place from where the call was made.
Program P7.5 tests the function by reading pairs of numbers and printing the HCF of each pair. The call to hcf is made in the printf statement. The program stops if either number is less than or equal to 0.
Program P7.5
#include <stdio.h>
int main() {
int a, b;
int hcf(int, int);
printf("Enter two positive numbers: ");
scanf("%d %d", &a, &b);
while (a > 0 && b > 0) {
printf("The HCF is %d\n", hcf(a, b));
printf("Enter two positive numbers: ");
scanf("%d %d", &a, &b);
}
} //end main
//returns the hcf of m and n
int hcf(int m, int n) {
while (n != 0) {
int r = m % n;
m = n;
n = r;
}
return m;
} //end hcf
The following is a sample run of P7.5:
Enter two positive numbers: 42 24
The HCF is 6
Enter two positive numbers: 32 512
The HCF is 32
Enter two positive numbers: 100 31
The HCF is 1
Enter two positive numbers: 84 36
The HCF is 12
Enter two positive numbers: 0 0
We emphasize again that even though the function is written with parameters m and n, it can be called with any two integer values—constants, variables or expressions. In particular, it does not have to be called with variables named m and n. In our program, we called it with a and b.
We remind you that in order to use hcf in main, we must “declare” it using the function prototype
int hcf(int, int);
If you wish, you could write the two int declarations in main as one:
int a, b, hcf(int, int);
7.6.1 Using HCF to Find LCM
A common task in arithmetic is to find the lowest common multiple (LCM) of two numbers. For example, the LCM of 8 and 6 is 24 since 24 is the smallest number which can divide both 8 and 6 exactly.
If we know the HCF of the two numbers, we can find the LCM by multiplying the numbers and dividing by their HCF. Given that the HCF of 8 and 6 is 2, we can find their LCM by working out
8 × 62
which is 24. In general,
LCM(m, n) = (m x n) / HCF(m, n)
Knowing this, we can easily write a function lcm which, given two arguments m and n, returns the LCM of m and n.
//returns the lcm of m and n
int lcm(int m, int n) {
int hcf(int, int);
return (m * n) / hcf(m, n);
} //end lcm
Since lcm uses hcf, we must declare hcf by writing its prototype. We leave it as an exercise for you to write a program to test lcm. Remember to include the function hcf in your program. You may place hcf before or after lcm.
7.7 factorial
So far, we have written several functions which illustrate various concepts you need to know in writing and using functions. We now write another one and discuss it in detail, reinforcing some of the concepts we have met thus far and introducing new ones.
Before we write the function, let us first write a program which reads an integer n and prints n! (n factorial) where
0! = 1
n! = n(n - 1)(n - 2)...1 for n > 0
For example, 5! = 5.4.3.2.1 = 120.
The program will be based on the following algorithm:
set nfac to 1
read a number, n
for h = 2 to n do
nfac = nfac * h
endfor
print nfac
Dry run the algorithm with a value of 3 for n and convince yourself that it will print 6, the value of 3!. Check also that it produces the correct answer when n is 0 or 1. (Hint: the for loop is not executed when n is 0 or 1.)
The algorithm does not validate the value of n. For instance, n should not be negative since factorial is not defined for negative numbers. As a matter of interest, what would the algorithm print if n is negative? (Hint: the for loop is not executed.) To keep matters simple, our Program P7.6 does not validate n.
Program P7.6
#include <stdio.h>
int main() {
int nfac = 1, n;
printf("Enter a positive whole number: ");
scanf("%d", &n);
for (int h = 2; h <= n; h++)
nfac = nfac * h;
printf("%d! = %d\n", n, nfac);
}
A sample run of this program is shown here:
Enter a positive whole number: 4
4! = 24
We now consider the problem of writing a function (which we will call factorial) which, given an integer n, calculates and returns the value of n!. Since n! is an integer, the “return type” of the function is int.
We first write the function header. It is
int factorial(int n)
It is interesting to note that the function header is all the information we need in order to use the function correctly. Ignoring for the moment what the rest of factorial might look like, we can use it like this:
printf("5! = %d\n", factorial(5));
or like this:
scanf("%d", &num);
printf("%d! = %d\n", num,factorial(num));
In the latter case, if num is 4, printf prints:
4! = 24
The call factorial(num) returns the value 24 directly to the printf statement.
Following the logic of Program P7.6, we write the function factorial as follows:
int factorial(int n) {
int nfac = 1;
for (int h = 2; h <= n; h++)
nfac = nfac * h;
return nfac;
} //end factorial
It is worthwhile comparing Program P7.6 and the function:
§ The program prompts for and reads a value for n; the function gets a value for n when the function is called, as in factorial(4). It is wrong to attempt to read a value for n in this function.
§ In addition to n, both the program and the function need the variables nfac and h to express their logic.
§ The logic for calculating the factorial is the same for both program and function.
§ The program prints the answer (in nfac); the function returns the answer (in nfac) to the calling function. The answer is returned to the point at which factorial was called.
Other comments on factorial
§ Variables declared within a function are said to be local to the function. Thus, nfac is a local variable, used to hold the factorial. As a matter of interest, h is local to the for statement. When factorial is called, storage is allocated to nfac and h. These variables are used to work out the factorial. Just before the function returns, nfac and h are discarded.
§ You should verify that the function works properly if n is 0 or 1 (that is, it returns 1).
We now take a detailed look at what happens when factorial is called (from main, say). Consider the statements (m and fac are int):
m = 3;
fac = factorial(m);
The second statement is executed as follows:
§ The value of the argument m is determined; it is 3.
§ This value is copied to a temporary memory location and this location is passed to the function. The function labels it with the name of the parameter, n. The net effect is as if execution of the function began with the statement
§ n = 3;
§ In programming terminology, we say that the argument m is passed “by value”. The value of the argument is copied to a temporary location and it is this temporary location that is passed to the function. The function has no access whatsoever to the original argument. In this example, factorial has no access to m and, hence, cannot affect it in any way.
§ After n is assigned the value 3, execution of factorial proceeds as described above. Just before the function returns, the storage location occupied by n is discarded. In effect, the parameter n is treated like a local variable except that it is initialized to the value of the argument supplied.
§ The value returned by the function is the last value stored in nfac. In this example, the last value assigned to nfac is 6. Therefore, the value 6 is returned to the place from which the call factorial(3) was made.
§ The value 6 returned by factorial is assigned to fac.
§ Execution continues with the next statement, if any.
7.7.1 Using Factorial
We illustrate how factorial can be used by writing a complete Program P7.7 which prints n! for n = 0, 1, 2, 3, 4, 5, 6 and 7.
Program P7.7
#include <stdio.h>
int main() {
int factorial(int);
printf(" n n!\n\n");
for (int n = 0; n <= 7; n++)
printf("%2d %5d\n", n, factorial(n));
} //end main
int factorial(int n) {
int nfac = 1;
for (int h = 2; h <= n; h++)
nfac = nfac * h;
return nfac;
} //end factorial
When run, this program prints the following:
n |
n! |
|
0 |
1 |
|
1 |
1 |
|
2 |
2 |
|
3 |
6 |
|
4 |
24 |
|
5 |
120 |
|
6 |
720 |
|
7 |
5040 |
As you can see, the value of factorial increases very quickly. Even 8! = 40320, which is too big to fit in a 16-bit integer (largest value which can be stored is 32767). As an exercise, write the loop from 0 to 8 and see what happens.
Let us take a closer look at main. The first statement is the function prototype for factorial. This is needed since factorial will be called from main.
When main is executed,
§ printf prints a heading
§ The for loop is executed with n assuming the values 0, 1, 2, 3, 4, 5, 6, 7. For each value of n, factorial is called with n as its argument. The factorial is calculated and returned to the place in printf from where it was called.
We have deliberately used a variable called n in main to illustrate that this n does not (and cannot) conflict with the parameter n of factorial. Suppose n in main is stored in memory location 865 and has the value 3. The call factorial(n) stores the value of n, i.e. 3, in a temporary location (472, say) and this temporary location is passed to factorial where it is known as n. This is illustrated as follows:
865 |
3 |
472 |
3 |
|
n in main |
n in factorial |
We now have two locations called n. When in factorial, n refers to location 472; when in main, n refers to location 865; factorial has no access whatsoever to location 865.
It does not happen here, but if factorial were to change the value of n, it is the value in location 472 that would be changed; the value in location 865 would not be affected. When factorial finishes, location 472 is discarded—that nno longer exists.
From another point of view, factorial is oblivious to the actual argument that was used to call it since it sees only the argument’s value, not how it was derived.
We used n in main as a loop variable to illustrate the point above. However, we could have used any variable. In particular, we could have used h and there would be no conflict with the local variable h of the function factorial. When in factorial, h refers to the local variable; when in main, h refers to the h declared in main.
7.7.2 Combinations
Suppose there are 7 people on a committee. How many subcommittees of 3 people can be formed? The answer is denoted by 7C3 and calculated as follows:
7!4! 3!
This gives us a value of 35. We say there are 35 combinations of 7 objects taken 3 at a time.
In general, nCr denotes the number of combinations of n objects taken r at a time and is calculated by the formula:
n!(n − r)! r!
Using factorial, we can write a function, combinations, which, given n and r, returns the number of combinations of n objects taken r at a time. Here it is:
int combinations(int n, int r) {
int factorial(int);
return factorial(n) / (factorial(n-r) * factorial(r));
} //end combinations
The body consists of the function prototype for factorial and one return statement with 3 calls to factorial.
We note, in passing, that this is perhaps the easiest, but not the most efficient, way to evaluate nCr. For instance, if we were calculating 7C3 by hand, we would use:
7.6.53.2.1
rather than
7.6.5.4.3.2.14.3.2.1.3.2.1
that the function uses. As an exercise, write an efficient function for evaluating combinations.
To show the functions factorial and combinations in a complete program and to show how they may be used, we write a program to read values for n and r and print the number of combinations we can get from n objects taken r at a time.
Program P7.8 shows how it’s done.
Program P7.8
#include <stdio.h>
int main() {
int n, r, nCr, factorial(int), combinations(int, int);
printf("Enter values for n and r: ");
scanf("%d %d", &n, &r);
while (n != 0) {
nCr = combinations(n, r);
if (nCr == 1)
printf("There is 1 combination of %d objects taken "
"%d at a time\n\n", n, r);
else
printf("There are %d combinations of %d objects taken "
"%d at a time\n\n", nCr, n, r);
printf("Enter values for n and r: ");
scanf("%d %d", &n, &r);
}
} //end main
int factorial(int n) {
int nfac = 1;
for (int h = 2; h <= n; h++)
nfac = nfac * h;
return nfac;
} //end factorial
int combinations(int n, int r) {
int factorial(int);
return factorial(n) / (factorial(n-r) * factorial(r));
} //end combinations
The program reads values for n and r and prints the number of combinations. This is done until a value of 0 is entered for n. The following is a sample run:
Enter values for n and r: 7 3
There are 35 combinations of 7 objects taken 3 at a time
Enter values for n and r: 5 2
There are 10 combinations of 5 objects taken 2 at a time
Enter values for n and r: 6 6
There is 1 combination of 6 objects taken 6 at a time
Enter values for n and r: 3 5
There are 0 combinations of 3 objects taken 5 at a time
Enter values for n and r: 0 0
Observe the use of if...else to get the program to “speak” correct English. In the statement, also note how a long string is broken into two pieces and each piece is put on one line. Recall that, in C, the opening and closing quotes of a string constant must be on the same line. When the program is compiled, the pieces will be joined together and stored in memory as one string.
7.8 Job Charge
In Program 4.6 we read the number of hours worked and the cost of parts and calculated the cost for a job. Let us write a function which, given the hours worked and cost of parts, returns the cost for the job. Here it is:
#define ChargePerHour 100
#define MinJobCost 150
double calcJobCost(double hours, double parts) {
double jobCharge;
jobCharge = hours * ChargePerHour + parts;
if (jobCharge < MinJobCost) return MinJobCost;
return jobCharge;
} //end calcJobCost
When we say that a function is given some data, that immediately implies that such data should be defined as parameters of the function. The logic of the function is the same as that of the program. Here, the parameter list indicates what data would be given to the function when it is called. Also, we must specify the return type of the function; it is double since the job cost is a double value.
When the function is called, as in
jobCost = calcJobCost(1.5, 87.50);
the parameter hours is set to 1.5 and parts is set to 87.50; the body of the function is then executed using these values for hours and parts.
As an exercise, write a complete program to read several values for hours worked and cost of parts and, for each pair, print the cost of the job.
7.9 Calculate Pay
In Program P4.7 we read values for hours and rate, and calculated net pay. All the code was written in main. We now write a function which, given values for hours and rate, returns the value of net pay calculated as described in Section 4.3.1. The function is shown below.
#define MaxRegularHours 40
#define OvertimeFactor 1.5
double calcNetPay(double hours, double rate) {
if (hours <= MaxRegularHours) return hours * rate;
return MaxRegularHours * rate +
(hours - MaxRegularHours) * rate * OvertimeFactor;
} //end CalcNetPay
If hours is less than or equal to MaxRegularHours, the first return is executed; if it is false, the second return is executed. Note that there is no need for else. If the first return is taken, we exit the function and the second returncannot be executed.
If we want to find out the net pay of someone who worked for 50 hours at $12.00 per hour, all we have to do is call calcNetPay(50, 12.00).
As an exercise, write a complete program to read several values for a name, hours worked and rate of pay and, for each person, print the net pay received. Hint: study Program P5.8.
7.10 Sum of Exact Divisors
Let us write a function to return the sum of the exact divisors of a given integer. We assume the divisors include 1 but not the given number. For example, the exact divisors of 50 are 1, 2, 5, 10 and 25. Their sum is 43. The function is shown below.
//returns the sum of the exact divisors of n
int sumDivisors(int n) {
int sumDiv = 1;
for (int h = 2; h <= n / 2; h++)
if (n % h == 0) sumDiv += h;
return sumDiv;
} //end sumDivisors
§ sumDiv is used to hold the sum of the exact divisors; it is set to 1 since 1 is always an exact divisor.
§ Other possible divisors are 2, 3, 4 and so on up to n/2. The for loop checks each of these in turn.
§ If h is an exact divisor of n then the remainder when n is divided by h is 0, that is, n % h is 0. If this is so, h is added to sumDiv.
§ The last statement returns the value of sumDiv to the place from which sumDivisors is called.
In the next example, we will see how sumDivisors may be used.
7.10.1 Classify Numbers
Positive integers can be classified based on the sum of their exact divisors. If n is an integer and s is the sum of its exact divisors (including 1 but not including n) then:
§ if s < n, n is deficient; e.g. 15 (divisors 1, 3, 5; sum 9)
§ if s = n, n is perfect; e.g. 28 (divisors 1, 2, 4, 7, 14; sum 28)
§ if s > n, n is abundant; e.g. 12 (divisors 1, 2, 3, 4, 6; sum 16)
Let us write Program P7.9 to read several numbers and, for each, print whether it is deficient, perfect or abundant.
Program P7.9
#include <stdio.h>
int main() {
int num, sumDivisors(int);
printf("Enter a number: ");
scanf("%d", &num);
while (num != 0) {
int sum = sumDivisors(num);
if (sum < num) printf("Deficient\n\n");
else if (sum == num) printf("Perfect\n\n");
else printf("Abundant\n\n");
printf("Enter a number: ");
scanf("%d", &num);
}
} //end main
//returns the sum of the exact divisors of n
int sumDivisors(int n) {
int sumDiv = 1;
for (int h = 2; h <= n / 2; h++)
if (n % h == 0) sumDiv += h;
return sumDiv;
} //end sumDivisors
Note that we call sumDivisors once (for each number) and store the result in sum. We use sum when we need the “sum of divisors” rather than re-calculate it each time.
The following is a sample run of Program P7.9:
Enter a number: 15
Deficient
Enter a number: 12
Abundant
Enter a number: 28
Perfect
Enter a number: 0
As an exercise, write a program to find all the perfect numbers less than 10,000.
7.11 Some Character Functions
In this Section, we write several functions relating to characters.
Perhaps the simplest is a function which takes a character as argument; it returns 1 if the character is a digit and 0, if it is not. (Recall that, in C, a zero value is interpreted as false and a non-zero value is interpreted as true.) This description suggests that we must write a function which takes a char argument and returns an int value. We will call it isDigit. Here it is:
int isDigit(char ch) {
return ch >= '0' && ch <= '9';
} //end isDigit
The Boolean expression (ch >= '0' && ch <= '9') is true if ch lies between '0' and '9', inclusive; that is, if ch contains a digit. Hence, if ch contains a digit, the function returns 1 (for true); if ch does not contain a digit, it returns 0(for false).
We could have written the body of the function as
if (ch >= '0' && ch <= '9') return 1;
return 0;
but the single return statement used above is the preferred way.
Similarly, we can write the function isUpperCase which returns 1 if its argument is an uppercase letter and 0 if it’s not, thus:
int isUpperCase(char ch) {
return ch >= 'A' && ch <= 'Z';
} //end isUpperCase
Next we have the function isLowerCase which returns 1 if its argument is a lowercase letter and 0 if it’s not.
int isLowerCase(char ch) {
return ch >= 'a' && ch <= 'z';
} //end isLowerCase
If we wish to know if the character is a letter (either uppercase or lowercase), we can write isLetter which uses isUpperCase and isLowerCase.
int isLetter(char ch) {
int isUpperCase(char), isLowerCase(char);
return isUpperCase(ch) || isLowerCase(ch);
} //end isLetter
Note that we need to include the function prototypes for isUpperCase and isLowerCase.
7.11.1 Position of a Letter in the Alphabet
Let us write a function which, given a character, returns 0 if it is not a letter of the English alphabet; otherwise, it returns the position—an integer value—of the letter in the alphabet. The function should work if the character is either an uppercase or a lowercase letter. For example, given 'T' or 't', the function should return 20.
The function takes a char argument and returns an int value. Using the functions isUpperCase and isLowerCase, we write the function (which we call position) as follows:
int position(char ch) {
int isUpperCase(char), isLowerCase(char);
if (isUpperCase(ch)) return ch - 'A' + 1;
if (isLowerCase(ch)) return ch - 'a' + 1;
return 0;
} //end position
We use isUpperCase and isLowerCase to establish what kind of character we have. If it is neither, control goes to the last statement and we return 0.
If we have an uppercase letter, we find the distance between the letter and A by subtracting the code for A from the code for the letter. For example, the distance between A and A is 0 and the distance between A and F is 5. Adding 1gives the position of the letter in the alphabet. Here, adding 1 gives us 1 for A and 6 for F.
If we have a lowercase letter, we find the distance between the letter and a by subtracting the code for a from the code for the letter. For example, the distance between a and b is 1 and the distance between a and z is 25. Adding 1gives the position of the letter in the alphabet. Here, adding 1 gives us 2 for b and 26 for z.
To illustrate how the function may be used, we write Program P7.10 which reads a line of input; for each character on the line, it prints 0 if it is not a letter and its position in the alphabet if it is a letter.
Program P7.10
#include <stdio.h>
int main() {
char c;
int position(char);
printf("Type some letters and non-letters and press 'Enter'\n");
while ((c = getchar()) != '\n')
printf("%c%2d\n", c, position(c));
} //end main
int isUpperCase(char ch) {
return ch >= 'A' && ch <= 'Z';
} //end isUpperCase
int isLowerCase(char ch) {
return ch >= 'a' && ch <= 'z';
} //end isLowerCase
int position(char ch) {
int isUpperCase(char), isLowerCase(char);
if (isUpperCase(ch)) return ch - 'A' + 1;
if (isLowerCase(ch)) return ch - 'a' + 1;
return 0;
} //end isPosition
Here is a sample run of P7.10:
Type some letters and non-letters and press "Enter" |
||
FaT($hY&n |
||
F |
6 |
|
a |
1 |
|
T |
20 |
|
( |
0 |
|
$ |
0 |
|
h |
8 |
|
Y |
25 |
|
& |
0 |
|
n |
14 |
We have written the functions isDigit, isUpperCase, isLowerCase and isLetter to illustrate basic concepts about character functions. However, C provides a number of predefined functions (actually, macros, but the distinction is not important for us) for working with characters. Among these are isdigit (test for a digit), isupper (test for an uppercase letter), islower (test for a lowercase letter) and isalpha (test for a letter). To use these functions, you need to place the directive
#include <ctype.h>
at the head of your program. As an exercise, rewrite P7.10 using isupper and islower. Without isUpperCase, isLowerCase and their prototypes, your program would be much shorter.
7.12 Fetch the Next Integer
Previously, we wrote Program P6.13 which read the data character by character, constructed and stored the next integer found in a variable, and finally printed the integer.
Let us now write a function, getInt, which reads the data character by character and returns the next integer found. The function does not take any arguments but the brackets must still be written after the name. The code is essentially the same as in P6.13, except that we use the predefined function isdigit. Here is getInt:
int getInt() {
char ch = getchar();
// as long as the character is not a digit, keep reading
while (!isdigit(ch)) ch = getchar() ;
// at this point, ch contains the first digit of the number
int num = 0;
while (isdigit(ch)) { // as long as we get a digit
num = num * 10 + ch - '0'; // update num
ch = getchar();
}
return num;
} //end getInt
Note that
while (ch < '0' || ch > '9')
of program P6.13 is replaced by
while (!isdigit(ch))
and
while (ch >= '0' && ch <= '9')
is replaced by
while (isdigit(ch))
We believe this makes the program a little more readable.
The function needs the variables ch and num to do its job; ch holds the next character in the data and num holds the number constructed so far. We declare them within the function, making them local variables. This way, they will not conflict with any variables with the same names declared anywhere else in the program. This makes the function self-contained—it does not depend on variables declared elsewhere.
The function can be used as in
id = getInt();
This fetches the next positive integer from the input, regardless of how many and what kind of characters come before it, and stores it in id. Recall that scanf("%d", &id) works only if the next integer is preceded by zero or more whitespace characters. Our getInt is more general.
We test it by rewriting Program P4.2 which requests two lengths given in metres and centimetres and finds the sum. We observed then that the data must be entered with digits only. If, for instance, we had typed 3m 75cm we would have gotten an error since 3m is not a valid integer constant. With getInt, we will be able to enter the data in the form 3m 75cm. The new program is shown as Program P7.11.
Program P7.11
//find the sum of two lengths given in metres and cm
#include <stdio.h>
#include <ctype.h>
int main() {
int m1, cm1, m2, cm2, mSum, cmSum, getInt();
printf("Enter first length: ");
m1 = getInt();
cm1 = getInt();
printf("Enter second length: ");
m2 = getInt();
cm2 = getInt();
mSum = m1 + m2; //add the metres
cmSum = cm1 + cm2; //add the centimetres
if (cmSum >= 100) {
cmSum = cmSum - 100;
mSum = mSum + 1;
}
printf("\nSum is %dm %dcm\n", mSum, cmSum);
} //end main
int getInt() {
char ch = getchar();
// as long as the character is not a digit, keep reading
while (!isdigit(ch)) ch = getchar() ;
// at this point, ch contains the first digit of the number
int num = 0;
while (isdigit(ch)) { // as long as we get a digit
num = num * 10 + ch - '0'; // update num
ch = getchar();
}
return num;
} //end getInt
A sample run is as follows:
Enter first length: 3m 75cm
Enter second length: 5m 50cm
Sum is 9m 25cm
You are encouraged to do the following:
§ Modify getInt so that it works for negative integers.
§ Write a function getDouble which returns the next floating-point number in the input. It should work even if the next number does not contain a decimal point.
EXERCISES 7
1. Explain why functions are important in writing a program.
2. Given the function header
3. void test(int n)
4. explain carefully what happens when the call test(5) is made.
5. Given the function header
6. double fun(int n)
7. explain carefully what happens when the following statement is executed:
8. printf("The answer is %f\n", fun(9));
9. Given the function header
10. void test(int m, int n, double x)
11. say whether each of the following calls is valid or invalid. If invalid, state why.
12. test(1, 2, 3);
13. test(-1, 0.0, 3.5);
14. test(7, 2);
15. test(14, '7', 3.14);
16. Write a function sqr which, given an integer n, returns n2.
17. Write a function isEven which, given an integer n, returns 1 if n is even and 0 if n is odd.
18. Write a function isOdd which, given an integer n, returns 1 if n is odd and 0 if n is even.
19. Write a function isPerfectSquare which, given an integer n, returns 1 if n is a perfect square (e.g. 25, 81) and 0 if it is not. Use only elementary arithmetic operations. Hint: Try numbers starting at 1. Compare the number times itself with n.
20. Write a function isVowel which, given a character c, returns 1 if c is a vowel and 0 if it is not.
21. Write a function which, given an integer n, returns the sum
22. 1 + 2 +...+ n
23. Write a function which, given an integer n, returns the sum
24. 12 + 22 +...+ n2
25. Write a function which, given three integer values representing the sides of a triangle, returns:
26. 0 if the values cannot be the sides of any triangle. This is so if any value is negative or zero, or if the length of any side is greater than or equal to the sum of the other two.
27. 1 if the triangle is scalene (all sides different).
28. 2 if the triangle is isosceles (two sides equal).
29. 3 if the triangle is equilateral (three sides equal).
30. Write a function which, given three integer values representing the sides of a triangle, returns 1 if the triangle is right-angled and 0 if it is not.
31. Write a function power which, given a double value x and an integer n, returns xn.
32. Using the algorithm of problem 10, Exercises 4, write a function which, given a year between 1900 and 2099, returns an integer value indicating the day on which Easter Sunday falls in that year. If d is the day of the month, return d if the month is March and -d if the month is April. For example, if the year is 1999, return -4 since Easter Sunday fell on April 4 in 1999. Assume that the given year is valid.
33. Write a program which reads two years, y1 and y2, and, using the function above, prints the day on which Easter Sunday falls for each year between y1 and y2.
34. Given values for month and year, write a function to return the number of days in the month.
35. Write a function numLength which, given an integer n, returns the number of digits in the integer. For example, given 309, the function returns 3.
36. Write a function max3 which, given 3 integers, returns the biggest.
37. Write a function isPrime which, given an integer n, returns 1 if n is a prime number and 0 if it is not. A prime number is an integer > 1 which is divisible only by 1 and itself.
38. Using isPrime, write a program to prompt for an even number n greater than 4 and print all pairs of prime numbers which add up to n. Print an appropriate message if n is not valid. For example, if n is 22, your program should print
39. 3 19
40. 5 17
41. 11 11
42. You are required to generate a sequence of integers from a given positive integer n, as follows. If n is even, divide it by 2. If n is odd, multiply it by 3 and add 1. Repeat this process with the new value of n, stopping when n= 1. For example, if n is 13, the following sequence will be generated:
43. 13 40 20 10 5 16 8 4 2 1
44. Write a function which, given n, returns the length of the sequence generated, including n and 1. For n = 13, your function should return 10.
45. Using the function, write a program to read two integers m and n (m < n), and print the maximum sequence length for the numbers between m and n, inclusive. Also print the number which gives the maximum length. For example, if m = 1 and n = 10, your program should print
46. 9 generates the longest sequence of length 20
47. We can code the 52 playing cards using the numbers 1 to 52. We can assign 1 to the Ace of Spades, 2 to the Two of Spades and so on, up to 13 to the King of Spades. We can then assign 14 to the Ace of Hearts, 15 to the Two of Hearts and so on, up to 26 to the King of Hearts. Similarly, we can assign the numbers 27-39 to Diamonds and 40-52 to Clubs.
48. Write a function which, given integers rank and suit, returns the code for that card. Assume rank is a number from 1 to 13 with 1 meaning Ace and 13 meaning King; suit is 1, 2, 3 or 4 representing Spades, Hearts, Diamonds and Clubs, respectively.