1 of 112

5

C Functions

1

2 of 112

Form ever follows function.

—Louis Henri Sullivan

E pluribus unum.�(One composed of many.)

—Virgil

O! call back yesterday, bid time return.

—William Shakespeare

Call me Ishmael.

—Herman Melville

2

3 of 112

When you call me that, smile!

—Owen Wister

Answer me in one word.

—William Shakespeare

There is a point at which methods devour themselves.

—Frantz Fanon

Life can only be understood backward; but it must be lived forward.

—Soren Kierkegaard

3

4 of 112

OBJECTIVES

In this chapter you will learn:

To construct programs modularly from small pieces called functions.
The common math functions available in the C Standard Library.
To create new functions.
The mechanisms used to pass information between functions.
Simulation techniques using random number generation.
How to write and use recursive functions, i.e., functions that call themselves.

4

5 of 112

5.1 Introduction

5.2 Program Modules in C

5.3 Math Library Functions

5.4 Functions

5.5 Function Definitions

5.6 Function Prototypes

5.7 Function Call Stack and Activation Records

5.8 Headers

5.9 Calling Functions: Call-by-Value and Call-by- Reference

5

6 of 112

5.10 Random Number Generation

5.11 Example: A Game of Chance

5.12 Storage Classes

5.13 Scope Rules

5.14 Recursion

5.15 Example Using Recursion: Fibonacci Series

5.16 Recursion vs. Iteration

6

7 of 112

5.1 Introduction

Divide and conquer

Construct a program from smaller pieces or components

These smaller pieces are called modules

Each piece more manageable than the original program

7

8 of 112

5.2 Program Modules in C

Functions

Modules in C
Programs combine user-defined functions with library functions

C standard library has a wide variety of functions

Function calls

Invoking functions

Provide function name and arguments (data)
Function performs operations or manipulations
Function returns results

Function call analogy:

Boss asks worker to complete task

Worker gets information, does task, returns result

Information hiding: boss does not know details

8

9 of 112

Good Programming Practice 5.1

Familiarize yourself with the rich collection of functions in the C Standard Library.

9

10 of 112

Software Engineering Observation 5.1

Avoid reinventing the wheel. When possible, use C Standard Library functions instead of writing new functions. This can reduce program development time.

10

11 of 112

Portability Tip 5.1

Using the functions in the C Standard Library helps make programs more portable.

11

12 of 112

12

Fig. 5.1 | Hierarchical boss function/worker function relationship.

13 of 112

5.3 Math Library Functions

Math library functions

perform common mathematical calculations
#include <math.h>

Format for calling functions

FunctionName( argument );

If multiple arguments, use comma-separated list

printf( "%.2f", sqrt( 900.0 ) );

Calls function sqrt, which returns the square root of its argument
All math functions return data type double

Arguments may be constants, variables, or expressions

13

14 of 112

Error-Prevention Tip 5.1

Include the math header by using the preprocessor directive #include <math.h> when using functions in the math library.

14

15 of 112

15

Fig. 5.2 | Commonly used math library functions. (Part 1 of 2.)

16 of 112

16

Fig. 5.2 | Commonly used math library functions. (Part 2 of 2.)

17 of 112

5.4 Functions

Functions

Modularize a program
All variables defined inside functions are local variables

Known only in function defined

Parameters

Communicate information between functions
Local variables

Benefits of functions

Divide and conquer

Manageable program development

Software reusability

Use existing functions as building blocks for new programs
Abstraction - hide internal details (library functions)

Avoid code repetition

17

18 of 112

Software Engineering Observation 5.2

In programs containing many functions, main is often implemented as a group of calls to functions that perform the bulk of the program’s work.

18

19 of 112

Software Engineering Observation 5.3

Each function should be limited to performing a single, well-defined task, and the function name should effectively express that task. This facilitates abstraction and promotes software reusability.

19

20 of 112

Software Engineering Observation 5.4

If you cannot choose a concise name that expresses what the function does, it is possible that your function is attempting to perform too many diverse tasks. It is usually best to break such a function into several smaller functions.

20

21 of 112

5.5 Function Definitions

Function definition format

return-value-type function-name( parameter-list )�{� declarations and statements�}

Function-name: any valid identifier
Return-value-type: data type of the result (default int)

void – indicates that the function returns nothing

Parameter-list: comma separated list, declares parameters

A type must be listed explicitly for each parameter unless, the parameter is of type int

21

22 of 112

5.5 Function Definitions

Function definition format (continued)

return-value-type function-name( parameter-list )�{� declarations and statements�}

Definitions and statements: function
n body (block)

Variables can be defined inside blocks (can be nested)
Functions can not be defined inside other functions

Returning control

If nothing returned

return;

or, until reaches right brace

If something returned

return expression;

22

23 of 112

Good Programming Practice 5.2

Place a blank line between function definitions to separate the functions and enhance program readability.

23

24 of 112

24

Outline

fig05_03.c

Function definition

Function prototype indicates function will be defined later in the program

Call to square function

25 of 112

Common Programming Error 5.1

Omitting the return-value-type in a function definition is a syntax error if the function prototype specifies a return type other than int.

25

26 of 112

Common Programming Error 5.2

Forgetting to return a value from a function that is supposed to return a value can lead to unexpected errors. The C standard states that the result of this omission is undefined.

26

27 of 112

Common Programming Error 5.3

Returning a value from a function with a void return type is a syntax error.

27

28 of 112

Good Programming Practice 5.3

Even though an omitted return type defaults to int, always state the return�type explicitly.

28

29 of 112

Common Programming Error 5.4

Specifying function parameters of the same type as double x, y instead of double x, double y might cause errors in your programs. The parameter declaration double x, y would actually make y a parameter of type int because int is the default.

29

30 of 112

Common Programming Error 5.5

Placing a semicolon after the right parenthesis enclosing the parameter list of a function definition is a syntax error.

30

31 of 112

Common Programming Error 5.6

Defining a function parameter again as a local variable within the function is a syntax error.

31

32 of 112

Good Programming Practice 5.4

Include the type of each parameter in the parameter list, even if that parameter is of the default type int.

32

33 of 112

Good Programming Practice 5.5

Although it is not incorrect to do so, do not use the same names for the arguments passed to a function and the corresponding parameters in the function definition. This helps avoid ambiguity.

33

34 of 112

Common Programming Error 5.7

Defining a function inside another function is a syntax error.

34

35 of 112

Good Programming Practice 5.6

Choosing meaningful function names and meaningful parameter names makes programs more readable and helps avoid excessive use of comments.

35

36 of 112

Software Engineering Observation 5.5

A function should generally be no longer than one page. Better yet, functions should generally be no longer than half a page. Small functions promote software reusability.

36

37 of 112

Software Engineering Observation 5.6

Programs should be written as collections of small functions. This makes programs easier to write, debug, maintain and modify.

37

38 of 112

Software Engineering Observation 5.7

A function requiring a large number of parameters may be performing too many tasks. Consider dividing the function into smaller functions that perform the separate tasks. The function header should fit on one line if possible.

38

39 of 112

Software Engineering Observation 5.8

The function prototype, function header and function calls should all agree in the number, type, and order of arguments and parameters, and in the type of return value.

39

40 of 112

40

Outline

fig05_04.c

(1 of 2 )

Function prototype

Function call

41 of 112

41

Outline

fig05_04.c

(2 of 2 )

Function definition

42 of 112

5.6 Function Prototypes

Function prototype

Function name
Parameters – what the function takes in
Return type – data type function returns (default int)
Used to validate functions
Prototype only needed if function definition comes after use in program
The function with the prototype

int maximum( int x, int y, int z );

Takes in 3 ints
Returns an int

Promotion rules and conversions

Converting to lower types can lead to errors

42

43 of 112

Good Programming Practice 5.7

Include function prototypes for all functions to take advantage of C’s type-checking capabilities. Use #include preprocessor directives to obtain function prototypes for the standard library functions from the headers for the appropriate libraries, or to obtain headers containing function prototypes for functions developed by you and/or your group members.

43

44 of 112

Good Programming Practice 5.8

Parameter names are sometimes included in function prototypes (our preference) for documentation purposes. The compiler ignores these names.

44

45 of 112

Common Programming Error 5.8

Forgetting the semicolon at the end of a function prototype is a syntax error.

45

46 of 112

46

Fig. 5.5 | Promotion hierarchy for data types.

47 of 112

Common Programming Error 5.9

Converting from a higher data type in the promotion hierarchy to a lower type can change the data value.

47

48 of 112

Common Programming Error 5.10

Forgetting a function prototype causes a syntax error if the return type of the function is not int and the function definition appears after the function call in the program. Otherwise, forgetting a function prototype may cause a runtime error or an unexpected result.

48

49 of 112

Software Engineering Observation 5.9

A function prototype placed outside any function definition applies to all calls to the function appearing after the function prototype in the file. A function prototype placed in a function applies only to calls made in that function.

49

50 of 112

5.7 Function Call Stack and Activation Records

Program execution stack

A stack is a last-in, first-out (LIFO) data structure

Anything put into the stack is placed “on top”
The only data that can be taken out is the data on top

C uses a program execution stack to keep track of which functions have been called

When a function is called, it is placed on top of the stack
When a function ends, it is taken off the stack and control returns to the function immediately below it

Calling more functions than C can handle at once is known as a “stack overflow error”

50

51 of 112

5.8 Headers

Header files

Contain function prototypes for library functions
<stdlib.h> , <math.h> , etc
Load with #include <filename>

#include <math.h>

Custom header files

Create file with functions
Save as filename.h
Load in other files with #include "filename.h"
Reuse functions

51

52 of 112

52

Fig. 5.6 | Some of the standard library headers. (Part 1 of 3.)

53 of 112

53

Fig. 5.6 | Some of the standard library headers. (Part 2 of 3.)

54 of 112

54

Fig. 5.6 | Some of the standard library headers. (Part 3 of 3.)

55 of 112

5.9 Calling Functions: Call-by-Value and Call-by-Reference

Call by value

Copy of argument passed to function
Changes in function do not effect original
Use when function does not need to modify argument

Avoids accidental changes

Call by reference

Passes original argument
Changes in function effect original
Only used with trusted functions

For now, we focus on call by value

55

56 of 112

5.10 Random Number Generation

rand function

Load <stdlib.h>
Returns "random" number between 0 and RAND_MAX (at least 32767)

i = rand();

Pseudorandom

Preset sequence of "random" numbers
Same sequence for every function call

Scaling

To get a random number between 1 and n

1 + ( rand() % n )

rand() % n returns a number between 0 and n - 1
Add 1 to make random number between 1 and n

1 + ( rand() % 6)

number between 1 and 6

56

57 of 112

57

Outline

fig05_07.c

Generates a random number between 1 and 6

58 of 112

58

Outline

fig05_08.c

(1 of 3 )

59 of 112

59

Outline

fig05_08.c

(2 of 3 )

60 of 112

60

Outline

fig05_08.c

(3 of 3 )

61 of 112

5.10 Random Number Generation

srand function

<stdlib.h>
Takes an integer seed and jumps to that location in its "random" sequence

srand( seed );

srand( time( NULL ) );/*load <time.h> */

time( NULL )

Returns the number of seconds that have passed since January 1, 1970

“Randomizes" the seed

61

62 of 112

62

Outline

fig05_09.c

(1 of 2 )

Seeds the rand function

63 of 112

63

Outline

fig05_09.c

(2 of 2 )

64 of 112

Common Programming Error 5.11

Using srand in place of rand to generate random numbers.

64

65 of 112

5.11 Example: A Game of Chance

Craps simulator
Rules

Roll two dice

7 or 11 on first throw, player wins
2, 3, or 12 on first throw, player loses
4, 5, 6, 8, 9, 10 - value becomes player's "point"

Player must roll his point before rolling 7 to win

65

66 of 112

66

Outline

fig05_10.c

(1 of 4 )

enum (enumeration) assigns numerical values to CONTINUE, WON and LOST

67 of 112

67

Outline

fig05_10.c

(2 of 4 )

68 of 112

68

Outline

fig05_10.c

(3 of 4 )

69 of 112

69

Outline

fig05_10.c

(4 of 4 )

70 of 112

70

Outline

fig05_11.c

71 of 112

Common Programming Error 5.12

Assigning a value to an enumeration constant after it has been defined is a syntax error.

71

72 of 112

Good Programming Practice 5.9

Use only uppercase letters in the names of enumeration constants to make these constants stand out in a program and to indicate that enumeration constants are not variables.

72

73 of 112

5.12 Storage Classes

Storage class specifiers

Storage duration – how long an object exists in memory
Scope – where object can be referenced in program
Linkage – specifies the files in which an identifier is known (more in Chapter 14)

Automatic storage

Object created and destroyed within its block
auto: default for local variables

auto double x, y;

register: tries to put variable into high-speed registers

Can only be used for automatic variables

register int counter = 1;

73

74 of 112

Performance Tip 5.1

Automatic storage is a means of conserving memory, because automatic variables exist only when they are needed. They are created when the function in which they are defined is entered and they are destroyed when the function is exited.

74

75 of 112

Software Engineering Observation 5.10

Automatic storage is an example of the principle of least privilege—allowing access to data only when it is absolutely needed. Why have variables stored in memory and accessible when in fact they are not needed?

75

76 of 112

Performance Tip 5.2

The storage-class specifier register can be placed before an automatic variable declaration to suggest that the compiler maintain the variable in one of the computer’s high-speed hardware registers. If intensely used variables such as counters or totals can be maintained in hardware registers, the overhead of repeatedly loading the variables from memory into the registers and storing the results back into memory can be eliminated.

76

77 of 112

Performance Tip 5.3

Often, register declarations are unnecessary. Today’s optimizing compilers�are capable of recognizing frequently used variables and can decide to place them in registers without the need for a register declaration.

77

78 of 112

5.12 Storage Classes

Static storage

Variables exist for entire program execution
Default value of zero
static: local variables defined in functions.

Keep value after function ends
Only known in their own function

extern: default for global variables and functions

Known in any function

78

79 of 112

Software Engineering Observation 5.11

Defining a variable as global rather than local allows unintended side effects to occur when a function that does not need access to the variable accidentally or maliciously modifies it. In general, use of global variables should be avoided except in certain situations with unique performance requirements (as discussed in Chapter 14).

79

80 of 112

Software Engineering Observation 5.12

Variables used only in a particular function should be defined as local variables in that function rather than as external variables.

80

81 of 112

Common Programming Error 5.13

Using multiple storage-class specifiers for an identifier. Only one storage-class specifier can be applied to an identifier.

81

82 of 112

5.13 Scope Rules

File scope

Identifier defined outside function, known in all functions
Used for global variables, function definitions, function prototypes

Function scope

Can only be referenced inside a function body
Used only for labels (start:, case: , etc.)

82

83 of 112

5.13 Scope Rules

Block scope

Identifier declared inside a block

Block scope begins at definition, ends at right brace

Used for variables, function parameters (local variables of function)
Outer blocks "hidden" from inner blocks if there is a variable with the same name in the inner block

Function prototype scope

Used for identifiers in parameter list

83

84 of 112

Common Programming Error 5.14

Accidentally using the same name for an identifier in an inner block as is used for an identifier in an outer block, when in fact you want the identifier in the outer block to be active for the duration of the inner block.

84

85 of 112

Error-Prevention Tip 5.2

Avoid variable names that hide names in outer scopes. This can be accomplished simply by avoiding the use of duplicate identifiers in a program.

85

86 of 112

86

Outline

fig05_12.c

(1 of 4 )

Global variable with file scope

Variable with block scope

87 of 112

87

Outline

fig05_12.c

(2 of 4 )

Variable with block scope

88 of 112

88

Outline

fig05_12.c

(3 of 4 )

Static variable with block scope

Global variable

89 of 112

89

Outline

fig05_12.c

(4 of 4 )

90 of 112

5.14 Recursion

Recursive functions

Functions that call themselves
Can only solve a base case
Divide a problem up into

What it can do
What it cannot do

What it cannot do resembles original problem

The function launches a new copy of itself (recursion step) to solve what it cannot do

Eventually base case gets solved

Gets plugged in, works its way up and solves whole problem

90

91 of 112

5.14 Recursion

Example: factorials

5! = 5 * 4 * 3 * 2 * 1
Notice that

5! = 5 * 4!
4! = 4 * 3! ...

Can compute factorials recursively
Solve base case (1! = 0! = 1) then plug in

2! = 2 * 1! = 2 * 1 = 2;
3! = 3 * 2! = 3 * 2 = 6;

91

92 of 112

92

Fig. 5.13 | Recursive evaluation of 5!.

93 of 112

93

Outline

fig05_14.c

(1 of 2 )

94 of 112

94

Outline

fig05_14.c

(2 of 2 )

95 of 112

Common Programming Error 5.15

Forgetting to return a value from a recursive function when one is needed.

95

96 of 112

Common Programming Error 5.16

Either omitting the base case, or writing the recursion step incorrectly so that it does not converge on the base case, will cause infinite recursion, eventually exhausting memory. This is analogous to the problem of an infinite loop in an iterative (nonrecursive) solution. Infinite recursion can also be caused by providing an unexpected input.

96

97 of 112

5.15 Example Using Recursion: Fibonacci Series

Fibonacci series: 0, 1, 1, 2, 3, 5, 8...

Each number is the sum of the previous two
Can be solved recursively:

fib( n ) = fib( n - 1 ) + fib( n – 2 )

Code for the fibonacci function

long fibonacci( long n )

{

if (n == 0 || n == 1) // base case

return n;

else

return fibonacci( n - 1) +� fibonacci( n – 2 );

}

97

98 of 112

98

Outline

fig05_15.c

(1 of 4 )

99 of 112

99

Outline

fig05_15.c

(2 of 4 )

100 of 112

100

Outline

fig05_15.c

(3 of 4 )

101 of 112

101

Outline

fig05_15.c

(4 of 4 )

102 of 112

102

Fig. 5.16 | Set of recursive calls for fibonacci(3).

103 of 112

Common Programming Error 5.17

Writing programs that depend on the order of evaluation of the operands of operators other than &&, ||, ?:, and the comma (,) operator can lead to errors because compilers may not necessarily evaluate the operands in the order you expect.

103

104 of 112

Portability Tip 5.2

Programs that depend on the order of evaluation of the operands of operators other than &&, ||, ?:, and the comma (,) operator can function differently on systems with different compilers.

104

105 of 112

Performance Tip 5.4

Avoid Fibonacci-style recursive programs which result in an exponential “explosion” of calls.

105

106 of 112

5.16 Recursion vs. Iteration

Repetition

Iteration: explicit loop
Recursion: repeated function calls

Termination

Iteration: loop condition fails
Recursion: base case recognized

Both can have infinite loops
Balance

Choice between performance (iteration) and good software engineering (recursion)

106

107 of 112

Software Engineering Observation 5.13

Any problem that can be solved recursively can also be solved iteratively (nonrecursively). A recursive approach is normally chosen in preference to an iterative approach when the recursive approach more naturally mirrors the problem and results in a program that is easier to understand and debug. Another reason to choose a recursive solution is that an iterative solution may not be apparent.

107

108 of 112

Performance Tip 5.5

Avoid using recursion in performance situations. Recursive calls take time and consume additional memory.

108

109 of 112

Common Programming Error 5.18

Accidentally having a nonrecursive function call itself either directly, or indirectly through another function.

109

110 of 112

Performance Tip 5.6

Functionalizing programs in a neat, hierarchical manner promotes good software engineering. But it has a price. A heavily functionalized program—as compared to a monolithic (i.e., one-piece) program without functions—makes potentially large numbers of function calls, and these consume execution time on a computer’s processor(s). So, although monolithic programs may perform better, they are more difficult to program, test, debug, maintain, and evolve.

110

111 of 112

111

Fig. 5.17 | Recursion examples and exercises in the text. (Part 1 of 2.)

112 of 112

112

Fig. 5.17 | Recursion examples and exercises in the text. (Part 2 of 2.)