1.Syntax form of function definition

2.Type of function and return value

The type identifier defines the type of the function, and also the type of the return value of the function. The return value of the function is the result that the function returns to its calling function, which is given by a return statement, such as “return 0”.

The function without a return value has a type identifier of void, and there need not be a return statement in the function.

3.Formal parameters

Here is the form of a formal parameter list:

type1, type2, ..., type n are type identifiers that represent the types of formal parameters, and name1, name2, ..., name n are the names of formal parameters. Formal parameters are used to realize the connection between the called function and the calling function. We often let the data that needs to process, factors that affect the function’s behavior, or the processing results of the function be the function’s formal parameters. Functions without formal parameters should have void on the position of the parameter list.

The main function can also have formal parameters and a return value. The formal parameters of the main function are also called command line parameters, which are initialized by the operating system when starting the program. The return value of the main function is returned to the operating system. The types and number of formal parameters of the main function have a special format. Refer to the experiment instructions in <Student’s Book> to write programs with command line parameters.

A function is only a piece of text before it has been called, and its formal parameters at the time are just symbols, indicating what type of data should appear at the position of the formal parameter. A function starts execution when it is called, and at that time, the calling function assigns the actual parameters to the formal parameters. This is similar to the definition of a function in mathematics:

$f\left(x\right)=x^2+x+1$

The function f will not be calculated until its argument has been assigned a value.

1.Form of function calls

Before calling a function we first need to declare the function prototype. The declaration can be in the calling function or before all the functions, with the following form:

If a function prototype is declared before all the functions, it is effective in the whole program file. That is, we can call the corresponding function anywhere in the file according to the prototype. If a function prototype is declared inside a calling function, it is only effective in this calling function.

After declaring the function prototype, we can make a function call with the following form:

The actual parameter list should provide parameters that accurately match the formal parameters in number and in types. A function call can be used as a statement, where the return value of the function is not needed; a function call can also appear in an expression, where an explicit return value of the function is needed.

Similar to the declaration and definition of variable, declaring a function only tells the compiler its relevant information (function name, parameters, return type, etc.) without generating any codes, while defining a function mainly gives the function code in addition to its relevant information.

Example 3.1: Writing a function to calculate the nth power of x.

Running result:

Example 3.2: Enter an 8-bit binary number, convert it to its decimal form, and then output the result.

Analysis: To convert a binary number to its decimal form, we need to multiply every bit of the binary number with the corresponding weight, and then add them up. For example: 000011012 = 0(27)+0(26)+0(25)+0(24)+1(23)+1(22)+0(21)+1(20) = 1310. So when the input is 1101, the output should be 13.

Here we make a function call on the function power in Example 3.1 to calculate 2n.

Source code:

Running result:

Example 3.3: Write a program to compute the value of π using the following formula.

$\pi \text{=16}\text{arctan}\left(\frac{1}{5}\right)-4\arctan \left(\frac{1}{239}\right)$

Use the following series to calculate the arctangent of a number:

Continue accumulating until the absolute value of one item in the series is less than 10−15. The type of π and x are both double.

$\arctan \left(x\right)=x-\frac{x^3}{3}+\frac{x^5}{5}-\frac{x^7}{7}+\cdots$

Source code:

Running result:

Example 3.4: Find the number m between 11 and 999 where m, m2, and m3 are all palindromes, and then output m.

Palindromes are numbers that have symmetrical number digits. For example: 121, 676, and 94249 are all palindromes. One instance that satisfies this subject’s requirement is: m = 11, m2 = 121, m3 = 1331.

Analysis: To check whether a number is a palindrome or not, we can get every digit of the number by continuously dividing it by 10 and obtaining the remainders. After getting all the digits, we reverse the digit order to get a new number, and compare the new number with the original one. The original number is a palindrome if and only if it is the same as the new number.

Source code:

Running result:

Example 3.5: Compute the value of the following formula and output the result.

$k=\{\begin{array}{c}\sqrt{{\text{sin}}^2\left(r\right)+{\text{sin}}^2\left(s\right)}\\ \frac{1}{2}\text{sin}\left(r\times s\right)\end{array}\begin{array}{c}\text{when}\\ \text{when}\end{array}\begin{array}{c}{r}^2\le s^2\\ r^2>s^2\end{array}$

Here the values of r and s are input from the keyboard. The approximate value of sin x is calculated using following formula:

$\text{sin }x=\frac{x}{1!}-\frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots ={\displaystyle \sum _{n=1}^{\infty }{\left(-1\right)}^{n-1}}\frac{x^{2n-1}}{\left(2n-1\right)!}$

The precision of the calculation is 10−6. Stop accumulating when the absolute value of one item is less than the precision, and the accumulated value is the approximate value of sin x.

Source code:

Running result:

Example 3.6: Game of casting dice.

Game rules: Dice has six faces – counting by the points, they are 1, 2, 3, 4, 5, and 6. The player inputs an unsigned integer, which is used as the seed to generate a random number at the beginning of the program.

In each turn the dice is casted twice, and we can get the total number of points. In the first turn, if the total number of points is 7 or 11, the player wins and the game is over; if the point total is 2, 3, or 12, the player loses and the game is over; otherwise the player records the point total as his point. In the following turns, if the point total is equal to the player’s point, the player wins and the game is over; if the point total is 7, the player loses and the game is over; otherwise, it goes on to the next round.

The function rolldice is used to simulate rolling the dice, getting the point total, and outputting it.

Note: The system function int rand( void) generates a pseudorandom number. The pseudorandom number is not really random. When we call this function continuously in a program in the hope that it will generate a sequence of random numbers, we may discover that it will generate the same sequence each time we run the program. This sequence is called a pseudorandom number sequence. It is because rand needs an initial number called “seed”, and different seeds will generate different sequences. Thus, if we give the program a different seed in each run, continuously calling rand will generate a different random number sequence. If the seed is not set, rand will use the default value 1 as the seed. Note that the method for setting the seed is somewhat special: it is not through the parameters of rand, but by calling another function void srand(unsigned int seed) to set the seed before calling rand, and the parameter seed in the function srand is the seed of rand.

Source code:

Running result 1:

Running result 2:

2.Procedure of calling a function

The compiler compiles a C++ program and outputs a piece of executable code, which is then stored as a file suffixed with exe in the external storage. When the program is started, the computer first loads the executable code from the external storage into the code area of the memory, and then executes the code from the entry address (the beginning of the main function). During the execution, the computer will stop executing the current function when a function call occurs. It will then save the address of the next instruction (return address is used as the entry point of execution when returned from the called function), save the execution scene, jump to the entry address of the called function, and execute the called function. When meeting a return statement or reaching the end of the called function, the computer will restore the scene previously stored, jump back to the return address, and continue the execution. Figure 3.1 shows the procedure of calling a function and returning from the call. The labels in the figure indicate the order of execution.

3.Nested function call

A nested call is allowed in a function. For example, function A calls function B, then function B calls function C, and this forms a nested call.

Example 3.7: Input two integers and compute the sum of their squares.

Analysis: Although the problem is easy, we design two functions to show how a nested call works: The function named fun1 is used to compute the sum of squares, and the function named fun2 is used to compute the square of an integer. The main function calls fun1, and fun1 calls fun2.

Source code:

Running result:

Figure 3.2 shows the order of function calls in Example 3.7. The labels in the figure indicate the executing order.

4.Recursive call

A function can call itself directly or indirectly. This kind of function call is called a recursive call.

Calling oneself directly means that the body of a function contains a function call to itself, for example:

And here is another example of a function indirectly calling itself:

Here fun1 calls fun2 and fun2 in turn calls fun1. These two calls constitute an indirect recursive call.

The essence of recursion is that it decomposes the original problem into a new problem, which may use the solution of the original problem. Continue the decomposition according to this principle, and each new problem emerged is a simplified subset of the original problem. The ultimately decomposed problem should be one whose solution is already known. The procedure above is a finite recursive call. Only a finite recursive call makes sense; an infinite recursive call will not get any results and it makes no sense.

The procedure of a recursive call consists of two parts:

First stage: Recurrence. Decompose the original problem continuously into new subproblems until we reach a known situation, at which point the recurrence ends.

For example, to calculate 5!, we can make a decomposition as follows:

Second stage: Regression. Starting from the known situation, use the result of the decomposed problem to solve the previous (more complex) problem. Repeat this process regressively according to the reversed order of the recurrence stage, until we reach the start of the recurrence. The regression then ends and the whole recursion finishes.

The regression procedure of calculating 5! is:

Example 3.8: Compute n!.

Analysis: The formula for calculating n! is:

$n!=\{\begin{array}{c}1\\ n\left(n-1\right)!\end{array}\begin{array}{c}\left(n=0\right)\\ \left(n>0\right)\end{array}$

This formula is recursive, since it calculates a factorial by using another factorial. Thus the program uses a recursive call. The ending condition of the recursion is n=0.

Source code:

Running result:

Example 3.9: Calculate the number of possible combinations (i.e., the combinatorial number) of selecting k person(s) out of n person(s) to form a committee.

Analysis: The combinatorial number of selecting k person(s) out of n person(s)

= The combinatorial number of selecting k person(s) out of n − 1 person(s)

+ The combinatorial number of selecting k − 1 person(s) out of n − 1 person(s)

Since the formula is recursive, it is easy to write a recursive function to implement the calculation. The ending condition of the recursion is n==k||k==0, at which time the combinatorial number is 1. Then the regression may start.

Source code:

Running result:

Example 3.10: Hanoi Tower Game.

There are three pillars A, B, and C. N plates of different sizes have been piled on pillar A, with larger plates being under smaller plates, as shown in Figure 3.3. The procedure of the game is to move the plates from pillar A to pillar C. The player can use pillar B during the game, though he can only move one plate at a time, and larger plates should always be under smaller plates during the movement.

Analysis: We could compress the procedure of moving n plates from pillar A to pillar C into three steps:

Actually, the three steps contain two kinds of operations:

The following program uses two functions to implement the two kinds of operations above – function hanoi for the first operation and function move for the second.

Source code:

Running result:

1.Call-by-Value

The procedure of Call-by-Value consists of two steps: allocating memory space for a formal parameter, and using the actual parameter to initialize the formal parameter (assigning the actual parameter to the formal parameter). This procedure just passes the value of the actual parameter to the formal parameter. The formal parameter does not have any relation to the actual parameter once it has been initialized, and any change of the formal parameters afterwards cannot affect the actual parameter.

Example 3.11: Swap and output two integers.

Running result:

Analysis: From the running result we can see that the values of variable x and y have not been swapped. It’s because in the function call above we use Call-by-Value to pass parameters, only where the values of the actual parameters are passed to the formal parameters. Thus the change of the formal parameters afterwards will not affect the actual parameters. Figure 3.4 shows the status of the variables when the program is running.

2.Call-by-Reference

We have seen that passing parameters through Call-by-Value is unidirectional. So how can changes made in the called function on formal parameters affect the actual parameters in the calling function? We can use Call-by-Reference to achieve this.

Reference is a special type of variable; it can be viewed as an alias of another variable. Accessing the reference of a variable is the same as accessing the variable itself. Here is an example:

The following rules must be followed when using references:

The rules above indicate that a reference should be fixed to refer to an object in its whole life, from its definition to its end.

Formal parameters can also be references. When a formal parameter is a reference, the situation is a bit different: the formal parameter of the reference type is not initialized during its type declaration, and it is only when the function is called that the computer allocates memory space for the formal parameter and initializes it to the actual parameter. In this way, the formal parameter of the reference type becomes an alias of the actual parameter, and every operation on the formal parameter directly affects the actual parameters.

The function call that uses references as formal parameters is called Call-by-Reference.

Example 3.12: Rewrite the program of Example 3.11, using Call-by-Reference to make the two integers swap correctly.

Running result:

Analysis: We can see from the running result that the swap is successful when the program uses Call-by-Reference to pass parameters. The only difference between Call-by-Value and Call-by-Reference lies in the declaration of the formal parameters, while the function call statements in the calling function are the same. Figure 3.5 shows the status of variables when the program is running.

Example 3.13: An example of Call-by-Reference.

Running result:

Analysis: The first parameter in1 of function fiddle has type int, and is assigned the value of the actual parameter count when the function is called. The second parameter in2 is a reference, and is initialized by the actual parameter index to an alias of index. Thus, the change on in1 in the called function has no effect on the actual parameter count, while the change on in2 in the called function is in fact the change on the variable index in the main function. When returned back to the main function, the value of count has not been changed, while the value of index has been changed.