2.1 How to Write a Function

In this section, we write a function that returns the Fibonacci element at a position specified by the user. For example, if the user asks, "What is the eighth Fibonacci element?" our function answers, "21." How do we go about defining this function?

We must define the following four parts to our function:

Before a function can be called within our program, it must be declared. A function declaration allows the compiler to verify the correctness of its use ?whether there are enough parameters, whether they are of the correct type, and so on. The function declaration specifies the return type, the name, and the parameter list but not the function body. This is called the function prototype.

// a declaration of our function 


int fibon_elem( int pos ); 

A function definition consists of the function prototype plus the function body. Given an element's position, fibon_elem() must calculate its value. Here is one possible implementation. (The /*,*/ pair is a multiline form of comment. Everything from the /* up to and including the matching */ is treated as a comment.)

/* A second form of comment delimiter 


 * 


 * 1st and 2nd elements of the Fibonacci Sequence 


 * are 1; each subsequent element is the sum of 


 * the preceding two elements 


 * 


 * elem: holds value to be returned 


 * n_2, n_1: holds preceding values 


 * pos: element position user requested 


 */ 





int elem = 1; // holds return value 


int n_2 = 1, n_1 = 1; 


for ( int ix = 3; ix <= pos; ++ix ) 


{ 


      elem = n_2 + n_1; 


      n_2 = n_1; n_1 = elem; 


} 

If the user asks for the first or second element, the body of the for loop is never executed. elem is initialized to 1, which is the correct value to return. If the user asks for the third or subsequent position, the loop calculates each value until ix exceeds pos. elem contains the value of the element at pos.

To return a value from a function, we use the return statement. For our function, the return statement looks like this:

return elem; 

If we are willing to trust that our user never makes a mistake and if we are willing to calculate any Fibonacci position, however large, then we are finished. Unfortunately, if we ignore both of these issues, our function is likely to fail at one time or another.

What are the mistakes a user might make? The user might enter an invalid position ?perhaps a value of 0 or a negative number. If the user does that, fibon_elem() returns 1, and that is wrong. So we check for that possibility:

// check for invalid position 


if ( pos <= 0 ) 


     // ok, now what? 

What should we do if the user requests an invalid position? The most extreme thing we can do is terminate the program. The standard library exit() function does just that. We pass it a value, and that value becomes the exit status of the program:

// terminate program with exit status of -1 


if ( pos <= 0 ) 


     exit( -1 ); 

To use exit(), we must include the cstdlib header file:

#include <cstdlib> 

Having our small function terminate an entire program is probably too severe. One alternative is to throw an exception indicating that fibon_elem() has received an invalid position. Unfortunately, exception handling is not discussed until Chapter 7, so that solution isn't an option just now.

We could return 0 and trust that the user recognizes that zero is an invalid value within the Fibonacci sequence. In general, however, trust is not a sound engineering principle. A more reasonable choice is to change our return value to indicate whether fibon_elem() is able to calculate the value:

// revised function prototype 


bool fibon_elem( int pos, int &elem ); 

A function can return only one value. In this case, the value returned is either true or false based on whether fibon_elem() can calculate the element's value. That leaves us with the problem of returning the element's actual value. In our revised function prototype, we solve that problem by adding a second parameter of type reference to int. This allows us in effect to have two values returned from the function. I explain the difference in behavior between the parameters pos and elem in the next section. It's a somewhat complicated idea that is best treated in a section of its own.

What happens if the user asks for the element value at position 5,000? That's a large number. When I tried to calculate it, I received the following answer:

element # 5000 is -1846256875 

That's not correct. What happened? I call it the ineluctable modality of the computer. Each arithmetic type can represent only a minimum and a maximum value of all possible domain values. ^[1] int, for example, is a signed type. The result of fibon_elem() overflowed the maximum positive value it can represent. When I changed elem to be of type unsigned int, the answer became

^[1] To determine the minimum and maximum values for a particular type, we can query the standard library numeric_limits class (for more details, see [STROUSTRUP97):

#include <limits> 


int max_int = numeric_limits<int>::max(); 


double min_dbl = numeric_limits<double>::min(); 

element # 5000 is 2448710421 

What would happen if the user asked for the 10,000th position? The 100,000th? The millionth? There is no end to the Fibonacci sequence. Our implementation, however, must impose an endpoint to the position value we are willing to support. How do we decide on that endpoint? Ultimately, that depends on the requirements of our users. For my purposes here, I've imposed an arbitrary but sufficient upward limit of 1,024 (it allows elem to remain an ordinary int).

Here is the final implementation of fibon_elem():

bool fibon_elem( int pos, int &elem ) 


{ 


   // check if invalid position ... 


   if ( pos <= 0 || pos > 1024 ) 


      { elem = 0; return false; } 





   // elem is 1 for positions 1 and 2 


   elem = 1; 


   int n_2 = 1, n_1 = 1; 





   for ( int ix = 3; ix <= pos; ++ix ) 


   { 


         elem = n_2 + n_1; 


         n_2 = n_1; n_1 = elem; 


   } 





   return true; 


} 

The following small program exercises fibon_elem():

#include <iostream> 


using namespace std; 





// forward declaration of fibon_elem() 


// makes function known to compiler ... 


bool fibon_elem( int, int& ); 





int main() 


{ 


   int pos; 


   cout << "Please enter a position: "; 


   cin >> pos; 





   int elem; 


   if ( fibon_elem( pos, elem )) 


        cout << "element # " << pos 


             << " is " << elem << endl; 


   else cout << "Sorry. Could not calculate element # " 


             << pos << endl; 


 } 

In our example, the declaration of fibon_elem() does not provide names for its two parameters. This is OK. The name of a parameter is necessary only if we need access to the parameter within the function. Some authors recommend always specifying the parameter names as a form of documentation. In a small program such as this, there seems little real benefit in doing so.

When the program is compiled and executed, the output looks like this (my input is highlighted in bold):

Please enter a position: 12 


element # 12 is 144 

A function that declares a non-void return type must return a value at each of its exit points. Each return statement within a function represents an explicit exit point. An implicit exit point follows the last statement within the function body if it is not a return statement. The following definition of print_sequence(), for example, fails to compile because its implicit exit point does not return a value.

bool print_sequence( int pos ) 


{ 


   if ( pos <= 0 || pos > 1024 ) 


   { 


        cerr << "invalid position: " << pos 


             << " -- cannot handle request!\n"; 





        return false; 


   } 


   cout << "The Fibonacci Sequence for " 


        << pos << " positions: \n\t"; 





   // prints 1 1 for all values except pos == 1 


   switch ( pos ) 


   { 


       default: 


       case 2: 


          cout << "1 "; 


          // no break; 


       case 1: 


          cout << "1 "; 


          break; 


   } 





   int elem; 


   int n_2 = 1, n_1 = 1; 


   for ( int ix = 3; ix <= pos; ++ix ) 


   { 


       elem = n_2 + n_1; 


       n_2 = n_1; n_1 = elem; 





       // print 10 elements to a line 


       cout << elem << ( !( ix % 10 ) ? "\n\t" : " " ); 


   } 


   cout << endl; 





   // compiler error is generated here: 


   // implicit exit point ... no return statement! 


} 

print_sequence() contains two exit points, but we have specified only one return statement. An implicit exit point occurs following the last statement. Our implementation returns a value only for an invalid position! Oops. Luckily, the compiler catches this and flags it as an error. We need to add a return true; as the last statement.

To exercise this implementation, I added a call to print_sequence() following the call to fibon_elem() in the earlier main() program. When compiled and executed, our main() program now generates the following output:

Please enter a position: 12 


element # 12 is 144 


The Fibonacci Sequence for 12 positions: 


        1 1 2 3 5 8 13 21 34 55 


        89 144 

A second form of the return statement does not return a value. It is used only in functions with a void return type. It is used to terminate a function prematurely.

void print_msg( ostream &os, const string &msg ) 


{ 


   if ( msg.empty() ) 


        // nothing to print; terminate function ... 


        return; 





   os << msg; 


} 

In this example, a final return statement is unnecessary because no value is being returned. The implicit exit point is sufficient.

Exercise 2.1

main(), presented earlier, allows the user to enter only one position value and then terminates. If a user wishes to ask for two or more positions, she must execute the program two or more times. Modify main() to allow the user to keep entering positions until she indicates she wishes to stop.