Previous Table of Contents Next


Functions may be defined and manipulated with fair (though not ultimate) flexibility. It is possible to define and manipulate pointers to functions, and to call functions via pointers, as discussed in section 3.6.7. It is perfectly acceptable for a function to call itself, either directly or indirectly; C explicitly supports recursion. All functions have their non-static local variables allocated using a stack discipline, so multiple invocations of a function can coexist. Functions cannot be nested, however, and there is no mechanism (e.g., along the lines of Lisp’s lambda) for generating functions at runtime.

We will close this section with three more examples, all of which happen to be recursive. Here is the digit-printing example of section 3.4.6, written recursively:

void printdigs(int n)
{
       if(n == 0)
               return;
       printdigs(n / 10);
       putdigit(n % 10);
}

(Because this function calls itself recursively before outputting a digit, it generates the digits in the correct, left-to-right order. This function, however, does not have the desirable property of section 3.4.6’s do/while loop; it prints nothing for the number zero.)

Here is a recursive implementation of the gcd function of section 3.5.1:

int gcd(int a, int b)
{
       if(b == 0)
              return a;
       else   return gcd(b, a % b);
}

Finally, here is the fib function from section 3.1.1 written recursively. To avoid the notorious recursive explosion that a naïve recursive Fibonacci function exhibits, this implementation maintains an array of the Fibonacci numbers it has already computed so that it can return them immediately, without recursive calls. This technique also provides a good example of the use of local, static variables:

int fib(int n)
{
       static int fibs[24] = {0, 1};
       if(n < 0 || n >= 24)
               return -1;
       if(fibs[n] == 0 && n > 0)
               fibs[n] = fib(n-1) + fib(n-2);
       return fibs[n];
}

The array is prefilled with 0 and 1; all other elements are initialized by default to 0 and computed by the function when needed. An array of size 24 (0–23) suffices, because the 24th Fibonacci number, 46,368, cannot portably be represented in a plain int.

3.5.4. Global Variables and External Declarations

We have seen (in section 3.2.6) that the placement of the declaration of a variable, either within or without a function, determines whether the variable is local or global. We have also discussed a distinction between a defining instance (of a variable or function) and an external declaration. Finally, we have mentioned that C is arranged to support separate compilation: The various functions and global variables making up a program may be placed in separate source files, compiled individually, and then linked together. The linker (which may or may not be a part of the C compiler proper) takes care of resolving functions and variables defined in one module and referenced in another, as long as the programmer has arranged the declarations and definitions correctly. When a function or variable is global (and, in C, all functions are global), it may be necessary to refer to that function or variable from within a source file other than the one in which the function or variable is defined. Because C compilers typically take the notion of separate compilation quite literally (that is, each source file is compiled in isolation, with no knowledge of the others), it is necessary, within each source file, to give the compiler sufficient information about functions and variables that are referred to but defined elsewhere. This information is provided in the form of external declarations.

Syntactically, a C program consists at the top level of nothing but declarations, of functions and global variables. We can speak of two subsets of declarations:

  A defining instance is a declaration that actually “creates” the declared function or variable. The defining instance of a global variable allocates space for the variable and may supply an initial value. The defining instance of a function supplies the function’s body.
  An external declaration refers to a variable or function that has been defined (that is, has its defining instance) elsewhere.

Before accessing a global variable, one of these declarations (a defining instance or an external declaration) must have been seen by the compiler. Before calling a function, a declaration may have been seen by the compiler; declarations are required under some circumstances and recommended in others, as discussed in section 3.5.3.

The exact scope of a declaration extends from its appearance in the source file onward, either to the end of the function or block (for local variables) or to the end of the source file (for globals). The placement of declarations is therefore significant: In order to refer to a global variable or call a function with its prototype in effect, the relevant declaration must already have been seen by the compiler—that is, must appear earlier in the source file than the reference—and must still be in scope.


Previous Table of Contents Next