Chapter9.txt

Chapter 9 Functions
一、Reviewing Functions
1.Creating and Using a Simple Function
(1)Function == a self-contained unit of program code designed to accomplish a particular task, and both produces actions and provides values.

(2)Synrax rules == define the structure of a function and how it can be used.

(3)Descriptive function names make it clear what the program does and how it is organized.

(4)Take a look at the lethead1.c program:
It consists of 2 functions: main() and starbar().

2.Analyzing the Program
(1)There are several major points to note about this program:
[1]It uses the starbar identifier in 3 separate contexts: a function prototype, a function call and a function definition.
{1}Function prototype == tells the compiler what sort of the function is.

{2}Function call == causes the function to be executed.

{3}Function definition == specifies exactly what the function does.

[2]Like variables, functions have types. Any program that uses a function should declare the type for that function before it is used.
For example:
-------------------------------------------------------------------------------------------------------------------
void starbar(void);
-------------------------------------------------------------------------------------------------------------------

This ANSI C prototype precedes the main() function definition. The parentheses indicate that starbar is a function name, the 1st void is a function type; the void type indicates that the function does not return a value. The 2nd void (the one in the parentheses) indicates that the function takes no arguments. The semicolon indicates that you are declaring the function instead of defining it.

!For compilers that do not recognize ANSI C prototyping, just declare the type!
For example:
-------------------------------------------------------------------------------------------------------------------
void starbar();
-------------------------------------------------------------------------------------------------------------------

!Some very old compilers do not recognize the void type, then use type int for function that do not have return values.!

[3]Signature == the type of value a function returns and the types of arguments it expects specified by the prototype of the function.

[4]The program places the starbar() prototype before main(), and you can also go inside main(), at the same location you would place any variable declarations, either way is fine.

[5]The program calls the function from main() by using its name followed by parentheses and a semicolon: starbar();
whenever the computer reaches this statement, it looks for the starbar() function and follows the instructions there, when finished, the computer returns to the next line of the calling function. (main() in this case.)

[6]The program follows the same form in defining starbar() as it does in defining main(). It starts with the type, name, and parentheses. Then it supplies the opening brace, a declaration of variables used, the defining statements of the function, and then the closing brace. If the function, as in this instance of starbar() is not followed by a semicolon, it tells the compiler that you are defining starbar() instead of calling or prototyping it.

[7]The program includes starbar() and main() in the same file, we can also use 2 separate files to place these 2 functions.

[8]Local variable == it is known only to the function where the variable exists.
For example:
The varibale count in starbar() is a local variable and it is known only to starbar(), you can use the name count in other functions, including main, and there will be no conflict.

*A function does not have any input because it does not need to use any information from the calling function, it does not provide (or return) any information to main(), so it does not have any return value, either. In short, the function does not require any communication with the calling function.*

3.Function Arguments
(1)Take a look at the lethead2.c program:
To make the text of the letterhead shown earlier centered, we can print the correct number of leading spaces before printing the text. So we create a new function show_n_char() to displaying a character n times. And instead of using built-in values for the display character and number of repetitions, show_n_char() will use function arguments to convey those values.

4.Defining a Function with an Argument: Formal Parameters
(1)The ANSI C function header of the function definition looks like this:
-------------------------------------------------------------------------------------------------------------------
void show_n_char(char ch, int num)
-------------------------------------------------------------------------------------------------------------------

It informs the compiler that show_n_char() uses 2 arguments called ch and num, and ch is type char, num is type int. Both of them are called formal arguments or formal parameters.

(2)Formal argument == local variables private to the function. And these variables will be assigned values each time the function is called.

(3)The ANSI C form requires that each variable be preceded by its type, which means that you cannot use a list of variables of the same type like regular declarations.
-------------------------------------------------------------------------------------------------------------------
void dibs(int x, y, z)  /* invalid */
void dibs(int x, int y, int z)  /* valid */
-------------------------------------------------------------------------------------------------------------------

(4)ANSI C also recognizes the pre-ANSI C form but characterizes it as obsolescent.
-------------------------------------------------------------------------------------------------------------------
void show_n_char(ch, num)
char ch;
int num;
-------------------------------------------------------------------------------------------------------------------

5.Prototyping a Function with Arguments
(1)Using an ANSI C prototype to declare the function before it is used.
For example:
-------------------------------------------------------------------------------------------------------------------
void show_n_char(char ch, int num);
-------------------------------------------------------------------------------------------------------------------

(2)When a function takes arguments, the prototype indicates their number and type by using a comma-separated list of the types. You can also omit variable names in the prototype if you like.
For example:
-------------------------------------------------------------------------------------------------------------------
void show_n_char(char, int);
-------------------------------------------------------------------------------------------------------------------

(3)Using variable names in a prototype does not actually create variables. It merely clarifies the fact that char means a char variable, and so on.

6.Calling a Function with an Argument: Actual Arguments
(1)Actual argument == the particular value assigned to the function variable by the calling function.

*The formal parameter is a variable in the called function.*

7.The Black-Box Viewpoint
(1)According to the black-box viewpoint, the input of the show_n_char() is the character to be displayed and the number of spaces to be skipped, the resulting action is printing the character the specified number of times.

(2)ch, num and count are local variables private to the show_n_char() fucntion, so if you were to use variables with the same names in main(), they would be separate, independent variables.
For example: if main() had a count variable, changing its value would not change the value of count in show_n_char(), and vice versa.

8.Returing a Value from a Function with return
(1)Take a look at the lesser.c program:
If we want to send information from the called function to the calling function, we use the fucntion return value.

(2)Driver == the program designed to test functions by creating a simple main() whose sole purpose is to check to see whether the function tested works.

(3)The variable min is private to imin(), but the value of min is communicated back to the calling function with return. We can assign the value of min to lesser like the following:
-------------------------------------------------------------------------------------------------------------------
lesser = imin(n, m);
-------------------------------------------------------------------------------------------------------------------

But we cannot say the following instead:
-------------------------------------------------------------------------------------------------------------------
imin(n, m);
lesser = min;
-------------------------------------------------------------------------------------------------------------------

Because the calling function does not even know that min exists. (imin()'s variables are local to imin().)

(4)Not only can the returned value be assigned to a variable, it can also be used as part of an expression.
For example:
-------------------------------------------------------------------------------------------------------------------
answer = 2 * imin(z, zstar) + 25;
printf("%d\n", imin(-32 + answer, LIMIT));
-------------------------------------------------------------------------------------------------------------------

(5)The return value can be supplied by any expression, not just a variable.
-------------------------------------------------------------------------------------------------------------------
/* minimum value function, second version */
imin(int n, int m)
{
	return (n < m) ? n : m;
}
-------------------------------------------------------------------------------------------------------------------

(6)If the function returns a type different from the declared type, the actual return value is what you would get if you assigned the indicated return value to a variable of the declared return type.
For example:
-------------------------------------------------------------------------------------------------------------------
int what_if(int n)
{
	double z = 100.0 / (double) n;
	return z;  // what happens?
}
-------------------------------------------------------------------------------------------------------------------

The net effect of the above program would be the same as if you assigned the value of z to an int variable and then returned that value.
For example:
-------------------------------------------------------------------------------------------------------------------
result = what_if(64);
-------------------------------------------------------------------------------------------------------------------

Then z is assigned 1.5625. The return statement, however, returns the int value 1.

(7)Using return has another effect. It terminates the function and returns control to the next statement in the calling function even if the return statement is not the last in the function.

(8)We can also use a statement like the following:
-------------------------------------------------------------------------------------------------------------------
return;
-------------------------------------------------------------------------------------------------------------------

It causes the function to terminate and return control to the calling function. Because no expression follows return, no value is returned, and this form should be used only in a type void function.

9.Function Types
(1)Functions should be declared by type.

(2)A function with a return value -> declared the same type as the return value.

(3)Functions with no return value -> declared as type void.

(4)If no type is given for a function, older version of C assume that the function is type int. But the C99 standard drops support for this implicit assumption of type int.

(5)A program needs to know the function type before the function is used for the 1st time.
[1]One way to accomplish this is to place the complete function definition ahead of its 1st use, but it can make the program harder to read, also, the functions might be part of the C library or in some other file.

[2]Function declarations can also be placed inside the function.
For example:
-------------------------------------------------------------------------------------------------------------------
#include <stdio.h>
int main(void)
{
	int imin(int, int)  /* imin() declaration */
	int evil1, evil2, lesser;
}
-------------------------------------------------------------------------------------------------------------------

(6)Our chief concern should be that the function declaration appears before the function is used.

(7)In ANSI C standard library, functions are grouped into families, each having its own header file. These header files contain, among other things, the declarations for the functions in the family.

二、ANSI C Function Prototyping
1.The Problem
(1)The traditional, pre-ANSI C scheme for declaring functions was deficient in that it declared a function's return type but not its arguments.
For example:
-------------------------------------------------------------------------------------------------------------------
int imin();
-------------------------------------------------------------------------------------------------------------------

It says nothing about the number or type of imin()'s arguments. So if you use imin() with the wrong number or type of arguments, the compiler DOES NOT catch the error.

(2)Take a look at the misuse.c program:
It declares imax() the old-fashioned way and then uses imax() incorrectly.

[1]Stack == A temporary storage area in which the calling function places its arguments.

[2]The mechanics may differ among systems, but what goes on with a PC or VAX is the calling function places its arguments in the stack and the called function reads those arguments off the stack.

[3]These 2 processes are NOT coordinated with one another.

[4]The calling function decides which type to pass based on the actual arguments in the call, and the called function reads values based on the types of its formal arguments.

[5]The call imax(3) (calling function) places 1 integer on the stack, when the imax() function (called function) starts up, it reads 2 integers off the stack. Only 1 was actually placed on the stack, so the 2nd value read is whatever value happened to be sitting in the stack at the time.

[6]The 2nd time the example uses imax(), it passes float values to imax(). This places 2 double values on the stack. (A float is promoted to double when passed as an argument.) On our system, that is 2 64-bit values, so 128 bits of data are placed on the stack. When imax() reads 2 ints from the stack, it reads the 1st 64 bits on the stack because on our system, each int is 32 bits. These bits happened to correspond to 2 integer values, the larger of which was 3886.

2.The ANSI C Solution
(1)The ANSI C standard's solution to the problems of mismatched arguments is to permit the function declaration to declare the variable types, too.

(2)Function prototype == a declaration that states the return type, the number of arguments, and the types of those arguments.
For example:
-------------------------------------------------------------------------------------------------------------------
int imax(int, int);
-------------------------------------------------------------------------------------------------------------------

It uses a comma-separated list of types, or we can also use this:
-------------------------------------------------------------------------------------------------------------------
int imax(int a, int b);
-------------------------------------------------------------------------------------------------------------------

It adds variable names to the types. (The variable names are dummy names and do not have to match the names used in the function definition.)

(3)If there is a type mismatch and if both types are numbers, the compiler converts the values of the actual arguments to the same type as the formal arguments.

(4)Take a look at the proto.c program:
When we tried to compile this program, our compiler gives an error message stating that the call to imax() has too few parameters.

(5)If we replace imax(3) with imax(3, 5) and tried compilation again, there were no error messages, and we ran the program.

(6)The 3.0 and 5.0 of the 2nd call are converted to 3 and 5 so that the function can handle the input properly.

(7)The difference between an error and a warning:
[1]Error == prevents compilation.

[2]Warning == permits compilation.

3.No Arguments and Unspecified Arguments
(1)Suppose we give a prototype like this:
-------------------------------------------------------------------------------------------------------------------
void print_name();
-------------------------------------------------------------------------------------------------------------------

An ANSI C compiler will assume that you have decided to forego function prototyping, and it will not check arguments.

(2)We can use the void keyword within the parentheses.
For example:
-------------------------------------------------------------------------------------------------------------------
void print_name(void);
-------------------------------------------------------------------------------------------------------------------

This time, ANSI C interprets that print_name() takes no arguments and then CHECKS to see that you do not use arguments when calling this function.

(3)Some functions such as printf() take a variable number of arguments. ANSI C allows partial prototyping for such cases.
For example:
-------------------------------------------------------------------------------------------------------------------
int printf(const char *, ...);
-------------------------------------------------------------------------------------------------------------------

We can use the above prototype for printf().

(4)The C library, through the stdarg.h header file, provides a standard way for defining a function with a variable number of parameters.

4.Hooray for Prototypes
(1)We do not have to use prototypes, instead, we can use the old type of function declaration (the one showing no parameters), or we can omit a prototype yet retain the advantages of it by placing the entire function definition before the 1st use. Then the definition acts as its own prototype.

三、Recursion
1.Recursion Revealed
(1)Recursion == a function calls itself.

(2)A function that calls itself tends to do indefinitely unless the programming includes a conditional test to terminate recursion.

(3)Recursion often can be used where loops can be used, but recursive solutions tend to be more elegant and less efficient than loop solutions.

(4)Take a look at the recur.c program:
[1]The "up_and_down(1)" is the 1st level of recursion. After that, the "up_and_down(n+1)" in up_and_down() function becomes "up_and_down(2)" and it is the 2nd level of recursion. Then the 2nd level of recursion calls "up_and_down(n+1)" in up_and_down() function again, it then becomes "up_and_down(3)" which is the 3rd level of recursion and so on.

[2]When Level 4 is reached, n is 4, so the if test fails. The up_and_down() function is not called again. Instead, the Level 4 call proceeds to print statement #2, which prints LEVEL 4, because n is 4. Then it reaches the return statement. At this point, the Level 4 call ends, and control passes back to the function that called it (the Level 3 call). The last statement executed in the Level 3 call was the call to Level 4 in the if statement. Therefore, Level 3 resumes with the following statement, which is print statement #2. This causes LEVEL 3 to be printed. Then Level 3 ends, passing control to Level 2, which prints LEVEL 2, and so on.

[3]!Each level of recursion uses its own private n variable. The critical point is that the address on the Level 1 line is the same as the address on the LEVEL 1 line, and so on.!

[4]The process of this program is like this:
You have a chain of function calls: fun1 -> fun2 -> fun3 -> fun4 -> fun3 -> fun2 -> fun1.

[5]The recursive case works the same, expect that fun1(), fun2(), fun3() and fun4() are the same function.

2.Recursion Fundamentals
(1)There are some basic points about recursion:
[1]Each level of function call has its own variables.
For example:
In the recur.c program, it creates 4 separate variables, each called n, but each having a distinct value. When the program finally returned to the 1st-level call of up_and_down(), the original n still had the value 1 it started with.

[2]Each function call is balanced with a return. When program flow reaches the return at the end of the last recursion level, control passes to the previous recursion level. The program does not jump all the way back to the original call in main(). Instead, the program must move back through each recursion level, returning from one level of up_and_down() to the level of up_and_down() that called it.

[3]Statements in a recursive function that come before the recursive call are executed in the same order that the functions are called.

[4]Statements in a recursive function that come after the recursive call are executed in the opposite order from which the functions are called. And this feature of recursion is useful for programming problems involving reversals of order.

[5]Although each level of recursion has its own set of variables, the code itself is not dupplicated. Sometimes recursion can be used instead of loops, and vice versa.

[6]It is vital that a recursive function contain something to halt the sequence of recursive calls. Typically, a recursive function uses an if test, or equivalent, to terminate recursion when a function parameter reaches a particular value.

3.Tail Recursion
(1)Tail recursion == end recursion, the recursive call comes at the end, just before the return statement.

(2)Take a look at the factor.c program:
[1]The recursive version of the program produces the same output as the loop version. Although the recursive call to rfact() is not the last line in the function, it is the last statement executed when n > 0, so it is tail recursion.

(3)Normally, the loop is the better choice.
[1]Each recursive call places a new set of variables on the stack and space restrictions in the stack can limit the number of recursive calls.

[2]Recursion is slower because each function call takes time.

4.Recursion and Reversal
(1)Take a look at the binary.c program:
This program is designed to print the binary equivalent of an integer.
[1]Binary notation == represent numbers in terms of powers of 2.

[2]Binary numbers use only the digits 0 and 1.

[3]Odd numbers must have a binary representation ending in 1, even numbers end in 0. In general, if n is a number, the final digit is n % 2, so the 1st digit you find is the last digit you want to print.

[4]We can use a recursive function in which n % 2 is calculated before the recursive call but in which it is printed after the recursive call. That way, the 1st value calculated is the last value printed. To get the next digit, divide the original number by 2. This is the binary equivalent of moving the decimal point one place to the left so that you can examine the next binary digit. If this value is even, the next binary digit is 0. If it is odd, the binary digit is 1.

[5]It stops when the result of dividing by 2 is less than 2 because as long as it is 2 or greater, there is one more binary digit. Each division by 2 lops off one more binary digit until you reach the end.

5.Recursion Pros and Cons
(1)Good point of recursion:
[1]Recursion offers the simplest solution to some programming problems.

(2)Bad points of recursion:
[1]Some recursive algorithms can rapidly exhaust a computer's memory resources.

[2]Recursion can be difficult to document and maintain.

(3)Fibonacci numbers == the 1st Fibonacci number is 1, the 2nd Fibonacci number is 1, and each subsequent Fibonacci number is the sum of the preceding 2.

(4)Double recursion == the function calls itself twice.

(5)Each level requires twice the number of variables as the preceding level, and the number of variables grows exponentially! Exponential growth soon leads to the computer requiring an enormous amount of memory, most likely causing the program to crash.

四、Compiling Programs with Two or More Source Code Files
1.Unix
(1)Assuming that the Unix C compiler cc has been installed.

(2)Suppose that file1.c and file2.c are 2 files containing C functions. Then the following command will compile both files and produce an executable file called a.out:
-------------------------------------------------------------------------------------------------------------------
cc file1.c file2.c
-------------------------------------------------------------------------------------------------------------------

In addition, 2 object files called file1.o and file2.o are produced. If you later change file1.c but not file2.c, you can compile the 1st and combine it with the object code version of the 2nd file by using this command:
-------------------------------------------------------------------------------------------------------------------
cc file1.c file2.c
-------------------------------------------------------------------------------------------------------------------

(3)make command == automate management of multifile programs.

2.Linux
(1)Assuming the Linux system has the GNU C compiler GCC installed.

(2)Suppose that file1.c and file2.c are 2 files containing C functions. Then the following command will compile both files and produce an executable file called a.out:
-------------------------------------------------------------------------------------------------------------------
gcc file1.c file2.c
-------------------------------------------------------------------------------------------------------------------

In addition, 2 object files called file1.o and file2.o are produced. If you later change file1.c but bot file2.c, you can compile the 1st and combine it with the object code version of the 2nd file by using this command:
-------------------------------------------------------------------------------------------------------------------
gcc file1.c file2.o
-------------------------------------------------------------------------------------------------------------------

3.DOS Command-Line Compilers
(1)Most DOS command-line compilers work similarly to the Unix cc command, but using a different name.

(2)Difference
[1]Object files wind up with an .obj extension instead of an .o extension. Some compilers produce intermediate files in assembly language or in some other special code, instead of object code files.

4.Windows and Apple IDE Compilers
(1)Integrated development environment compilers for Windows and Macintosh are PROJECT ORIENTED.

(2)Project == describes the resources a particular program uses, the resources include your source code files.

(3)If you have been using one of these compilers, you have probably had to create projects to run one-file programs. For multiple-file programs, find the menu command that lets you add a source code file to a project.

(4)Make sure all your souce code files (the ones with the .c extension) are listed as part of the project. With many IDEs, you do not list your header files. However, with Xcode, you do add header files to the project.

5.Using Header Files
(1)If you put main() in one file and your function definitions in a 2nd file, the 1st file still needs the function prototypes. You can store the function prototypes in a header file.

(2)Also, you will often use the C preprocessor to define constants used in a program. Such definitions hold only for the file containing the #define directives. If you place the functions of a program into separate files, you also have to make the #define directives available to EACH file.

(3)A better solution is to place the #define directives in a header file and then use the #include directive in each source code file.

(4)Take a look at the usehotel1.c and hotel1.c programs and the hotel.h header file and you will learn how to include the functions and #define directives.

五、Finding Addresses: The & Operator
1.Pointer == a variable used to store an address.

2.Unary & operator == give you the address where a variable is stored.

3.Address == a location in memory.

4.Take a look at the loccheck.c program:
(1)The way that %p represents addresses varies among implementations. Many implementations display the address in hexadecimal form.

(2)?What does the output show?
[1]The 2 poohs have different addresses. The same is true for the 2 bahs. That means the computer considers them to be 4 separate variables.

[2]The call mikado(pooh) did convey the value (2) of the actual argument (pooh of main()) to the formal argument (bah of mikado()). Note that just the value was transferred. The 2 variables involved (pooh of main() and bah of mikado()) retain their distinct identities.

六、Altering Variables in the Calling Function
1.Sometimes you want one function to make changes in the variables of a different function.

2.Take a look at the swap1.c and swap2.c programs:
There is nothing wrong with interchange(), it does swap the values of u and v. The problem is in communicating the results to main(). As we point out, interchange() uses different variables from main(), so interchanging the values of u and v has NO effect on x and y! We can finish interchange() with the line
-------------------------------------------------------------------------------------------------------------------
return(u);
-------------------------------------------------------------------------------------------------------------------

and change the call in main() to this:
-------------------------------------------------------------------------------------------------------------------
x = interchange(x, y);
-------------------------------------------------------------------------------------------------------------------

This change gives x its new value, but it leaves y in the cold. With return, you can send just 1 value back to the calling function, but you need to communicate 2 values. But we need to do this by using pointers.

七、Pointers: A First Look
1.The Indirection Operator: *
(1)Pointer == a variable (or, more generally, a data object) whose value is a memory address, which means the pointer variable has an address as a value.

(2)For example:
-------------------------------------------------------------------------------------------------------------------
ptr = &pooh;  // assign pooh's address to ptr
-------------------------------------------------------------------------------------------------------------------

The difference between ptr and &pooh is that ptr is a variable, and &pooh is a constant. Or, ptr is a modifiable lvalue and &pooh is an rvalue.

(3)To create a pointer variable, you need to be able to declare this type, and you need to use a new operator.

(4)Indirection operator * == dereferencing operator, used to find the value stored in variable.
For example:
-------------------------------------------------------------------------------------------------------------------
val = *ptr;  // finding the value ptr points to, and "ptr" is the name of the pointer
-------------------------------------------------------------------------------------------------------------------

!Do not confuse the unary indirection operator with the binary * operator of multiplication: they have the same symbol but different syntax!

(5)The statement ptr = &bah; and val = *ptr; taken together amount to the following statement: val = bah;

2.Declaring Pointers
(1)How to declare pointers?
We need to specify the kind of variable to which the pointer points because different variable types take up different amounts of storage, and some pointer operations require knowledge of that storage size. Also, the program has to know what kind of data is stored at the address.

(2)We should declare pointers like this:
-------------------------------------------------------------------------------------------------------------------
int * pi;  // pi is a pointer to an integer variable
char * pc;  // pc is a pointer to a character variable
float * pf, * pg;  // pf, pg are pointers to float variables
-------------------------------------------------------------------------------------------------------------------

That means: the type specification identifies the type of variable pointed to, and the asterisk (*) identifies the variable itself as a pointer.

(3)The space between the * and the pointer name is optional. Often, programmers use the space in a declaration and omit it when dereferencing a variable.

3.Using Pointers to Communicate Between Functions
(1)Take a look at the swap3.c program:
After using the pointers and interchange them, we actually get the values exchanged by exchanging their pointers, which means that the function interchange() transmits their addresses instead of transmitting the values of x and y.

(2)u has the value &x (the address of x), v has the value &y (the address of y); which means that *u gives you the value of x and *v gives you the value of y.

(3)We can omit the variable names in the ANSI C prototype. Then the prototype declaration looks like this:
-------------------------------------------------------------------------------------------------------------------
void interchange(int *, int *);
-------------------------------------------------------------------------------------------------------------------

(4)In general, we can communicate 2 kinds of information about a variable to a function.
[1]If we use a call of the form:
-------------------------------------------------------------------------------------------------------------------
function1(x);
-------------------------------------------------------------------------------------------------------------------

We transmit the value of x.

[2]If we use a call of the form:
-------------------------------------------------------------------------------------------------------------------
function2(&x);
-------------------------------------------------------------------------------------------------------------------

We transmit the address of x.

!The 1st form requires that the function definition includes a formal argument of the same type as x!
-------------------------------------------------------------------------------------------------------------------
int function1(int num)
-------------------------------------------------------------------------------------------------------------------

!The 2nd form requires the function definition to include a formal parameter that is a pointer to the right type!
-------------------------------------------------------------------------------------------------------------------
int function2(int * ptr)
-------------------------------------------------------------------------------------------------------------------

We use the 1st form if the function needs a value for some calculation or action. Use the 2nd form if the function needs to alter variables in the calling function.

(5)Pointers enable you to get around the fact that the variables of interchange() are local. They let the function reach out into main() and alter what is stored there.