C++ Primer Plus

Both fill() and show() have drawbacks. For show(), the problem is that expenses holds four double values and it’s inefficient to create a new object of that size and to copy the expenses values into it. The problem gets worse if we modify the program to handle expenses on a monthly basis or daily basis and expand expenses accordingly.

The fill() function avoids this inefficiency problem by using a pointer so that the function acts on the original object. But this comes at the cost of notation that makes the programming look more complicated:

fill(&expenses);    // don't forget the &

...

cin >> (*pa)[i];

In the last statement, pa is a pointer to an array object, so *pa is the object, and (*pa)[i] is an element in the object. The parentheses are required because of operator precedence. The logic is straightforward, but results enhance opportunities for making errors.

Using references, as discussed in Chapter 8, helps solve both the efficiency and the notational problems.

Recursion

And now for something completely different. A C++ function has the interesting characteristic that it can call itself. (Unlike C, however, C++ does not let main() call itself.) This ability is termed recursion. Recursion is an important tool in certain types of programming, such as artificial intelligence, but we’ll just take a superficial look (artificial shallowness) at how it works.

Recursion with a Single Recursive Call

If a recursive function calls itself, then the newly called function calls itself, and so on, ad infinitum unless the code includes something to terminate the chain of calls. The usual method is to make the recursive call part of an if statement. For example, a type void recursive function called recurs() can have a form like this:

void recurs(argumentlist)

{

      statements1

      if (test)

            recurs(arguments)

      statements2

}

With luck or foresight, test eventually becomes false, and the chain of calls is broken.

Recursive calls produce an intriguing chain of events. As long as the if statement remains true, each call to recurs() executes statements1 and then invokes a new incarnation of recurs() without reaching statements2. When the if statement becomes false, the current call then proceeds to statements2. Then when the current call terminates, program control returns to the previous version of recurs() that called it. Then, that version of recurs() completes executing its statements2 section and terminates, returning control to the prior call, and so on. Thus, if recurs() undergoes five recursive calls, first the statements1 section is executed five times in the order in which the functions were called, and then the statements2 section is executed five times in the opposite order from the order in which the functions were called. After going into five levels of recursion, the program then has to back out through the same five levels. Listing 7.16 illustrates this behavior.

Listing 7.16. recur.cpp

// recur.cpp -- using recursion

#include

void countdown(int n);

int main()

{

    countdown(4);           // call the recursive function

    return 0;

}

void countdown(int n)

{

    using namespace std;

    cout << "Counting down ... " << n << endl;

    if (n > 0)

        countdown(n-1);     // function calls itself

    cout << n << ": Kaboom!\n";

}

Here’s the annotated output of the program in Listing 7.16:

Counting down ... 4    ‹level 1; adding levels of recursion

Counting down ... 3    ‹level 2

Counting down ... 2    ‹level 3

Counting down ... 1    ‹level 4

Counting down ... 0    ‹level 5; final recursive call

0: Kaboom!             ‹level 5; beginning to back out

1: Kaboom!             ‹level 4

2: Kaboom!             ‹level 3

3: Kaboom!             ‹level 2

4: Kaboom!             ‹level 1

Note that each recursive call creates its own set of variables, so by the time the program reaches the fifth call, it has five separate variables called n, each with a different value. You can verify this for yourself by modifying Listing 7.16 so that it displays the address of n as well as its value:

cout << "Counting down ... " << n << " (n at " << &n << ")" << endl;

...

cout << n << ": Kaboom!"; << "         (n at " << &n << ")" << endl;

Doing so produces output like the following:

Counting down ... 4 (n at 0012FE0C)

Counting down ... 3 (n at 0012FD34)

Counting down ... 2 (n at 0012FC5C)

Counting down ... 1 (n at 0012FB84)

Counting down ... 0 (n at 0012FAAC)

0: Kaboom!          (n at 0012FAAC)

1: Kaboom!          (n at 0012FB84)

2: Kaboom!          (n at 0012FC5C)

3: Kaboom!          (n at 0012FD34)

4: Kaboom!          (n at 0012FE0C)