Chapter 34

Understanding Recursion




During your programming career, you've probably heard the words "divide and conquer" quite often. This is because experienced programmers know that writing a large program can be a psychologically draining challenge. When you think about all that goes into a full-length program, it's easy to become overwhelmed by the magnitude of the job. So, just as you read a book page by page or clean a house room by room, you write a program one function at a time. In this way, you can understand a huge task that might otherwise be beyond your abilities to grasp as a whole.

You can adopt the divide-and-conquer strategy in several ways, including object-oriented programming and structured programming. Recursion, the subject of this chapter, is another technique you can use to break complex tasks into their components. Using recursion, you can take a repetitive task and reduce it to a single step that is repeated again and again until you obtain the desired result.

In this chapter, you learn what recursion is and how it can be used to replace complex code with short and elegant functions. You also use recursion in a full-length program (a game!), applying what you've learned to a practical case.

Recursion: Barrels Within Barrels

When I was a kid, one of my favorite toys was a bunch of nested plastic barrels. You'd unscrew the first barrel, only to find a smaller one inside. In that barrel was yet another smaller barrel, and so on. Finally, in the tiniest barrel, was a small plastic rabbit. I spent hours fascinated with those barrels.

Recursion fascinates me in the same way, probably because recursion is a lot like those nested barrels. With recursion, you work your way deeper and deeper into an operation until you finally find that little bunny, the result of the operation you're trying to perform. Using recursion, complex operations can be programmed with only a few lines of code.

But what exactly is recursion? In a program, recursion occurs when a function calls itself. This might sound a little crazy. Why would a function want to call itself? When you called a function in past programs, you expected the function to do its job and to return. With recursion, though, you must think about functions differently. Rather than finishing a job, a recursive function does only a small portion of the task and then passes what's left to another call to itself.

The simplest recursive function looks something like Listing 34.1:

Listing 34.1 lst34_01.cpp The Simplest Recursive Function
void Recursive(void)
{
    Recursive();
}
This function accomplishes nothing. Worse, it's an infinite loop. The Recursive() function is called again and again, until, finally, you run out of stack space. For a recursive function to operate correctly, it needs some way to break out of the recursion. A more useful template for a recursive function is shown in Listing 34.2:

Listing 34.2 lst34_02.cpp A More Useful Recursive-Function Template
void Recursive(void)
{
    if (condition)
        return;
    else
        Recursive();
}
Here, when condition equals true, you return immediately rather than call Recursive() again. After breaking out of the recursion, previous calls to Recursive() all of which have already executed their last statement (the else statement) also return, until you finally return to the original call to Recursive().

This last example function doesn't accomplish much, but it does illustrate the most important elements of a recursive function, as follows:

A Real-World Example of Recursion

Now, how about an example that does something? If you consider those little barrels mentioned in the last section, you might see how recursion can simplify a programming task. To get to the bunny in those barrels, a child must open barrels, one after another, until she or he reaches the last one. Opening a single barrel is only a small part of the entire task. After the first barrel is opened, the same function must be performed on each remaining barrel.

Think of barrel-opening as a function in a program. In fact, you can do more than think about it; you can learn how to write it. Listing 34.3 is a program that simulates the bunny-in-barrels toy.

ON THE WEB

http://www.quecorp.com/semfc The complete source code and executable file for the Barrels application can be found in the CHAP34\Barrels directory of this book's Web site.

Listing 34.3 Barrels.cpp The Bunny-in-Barrels Program
#include <iostream.h>
#include <conio.h>
void OpenBarrel(int num)
{
    if (num == 0)
        cout << "Got the bunny!" << endl;
    else
    {
        cout << "Opening barrel #" << num << endl;
        OpenBarrel(num-1);
    }
}
void main(void)
{
    OpenBarrel(10);
    getch();
}
When you compile and run the program, you see the following output:

Opening barrel #10

Opening barrel #9

Opening barrel #8

Opening barrel #7

Opening barrel #6

Opening barrel #5

Opening barrel #4

Opening barrel #3

Opening barrel #2

Opening barrel #1

Got the bunny!

In the main program, OpenBarrel() is called with a parameter of 10. (This parameter indicates the number of barrels and can be any integer.) In OpenBarrel(), the value of num is first checked to see whether the program has reached the last barrel. If it has, it prints the Got the bunny! message. Otherwise, the program calls OpenBarrel() again with a parameter of num-1. This call invokes OpenBarrel() a second time before the first invocation has ended with a value of 9. This second invocation checks the value of num, finds it to be 9, and calls OpenBarrel() a third time, this time with a value of 8. This process continues until a call to OpenBarrel() gets a value of 0 for num, triggering the program to print Got the bunny!


Note that each invocation of OpenBarrel() has its own num variable. The num variable for the first invocation is not the same num you use in the second invocation. This is important to understand because this series of values eventually breaks the program out of the recursion.

A Power Function Using Recusion

Although the bunny-in-barrels program illustrates recursion well by simulating an easy-to-grasp, real-world problem, it doesn't show how you might use recursion in your programs. It's unlikely that you'll ever need to write programs about bunnies and barrels. So take a look at a recursive function that accomplishes something worthwhile, but that is still as easy to understand as the barrel program.

Consider the value 103. The result of the exponentiation is calculated by multiplying 10 by itself three times: 10*10*10. You can use a for loop to calculate this value, but that's much too pedestrian for power programmers. Instead, you can perform this multiplication operation recursively. Listing 34.4 includes a recursive function, Power(), which calculates the value of any integer raised to a positive integer exponent.

ON THE WEB

http://www.quecorp.com/semfc The complete source code and executable file for the Power application can be found in the CHAP34\Power directory at this book's Web site.

Listing 34.4 Power.cpp A Recursive Exponentiation Example
#include <iostream.h>
#include <conio.h>
int Power(int num, int exp)
{
    if (exp == 1)
        return num;
    else
        return num * Power(num, exp-1);
}
void main(void)
{
    cout << Power(10,3) << endl;
    getch();
}
Examine this short program carefully. Although the Power() function is only a few lines long, a lot more is going on than might at first be apparent. Basically, this function calls itself repeatedly with smaller and smaller values of exp, until exp equals 1. At this point, instead of calling itself again, Power() simply returns the value num. (In the 103 example, num equals 10.) Notice that no calculations are performed until the recursion has occurred as many times as possible. Then it returns 10 to the previous invocation of Power(), which multiplies that return value by 10. The result (100) is passed on to the first invocation, which also multiplies it by 10, giving the final result of 1000.

Confused? Figure 34.1 will help dispel the mystery. Starting at the top of the figure, Power() is called with the parameters 10 and 3. In the first call to Power(), the if statement examines exp and finds it to be 3, so the else statement executes. In the else statement, num is multiplied by the value returned from Power(num, exp-1).

The function can't perform the multiplication until it gets a return value from Power(), however, so it drops down to the second call to Power(), which gets the parameters 10 and 2. Again, the if statement is evaluated and program execution drops down to the else statement, which multiplies num by yet another call to Power(), this time with the parameters 10 and 1.

This brings the program to the third call to Power(), shown in the bottom box. This call gets the parameters 10 and 1. This time the if statement finds that exp is 1, so it immediately returns the value of num, which in this case is 10.


Figure 34.1 

Here's how 10^3 is solved recursively.

Notice that the program has performed no multiplication operations, because it has had no result from Power(). Instead, it has simply called Power() exp times. The multiplication takes place as the program works its way back out of the recursions. The third recursion returns 10 to the second recursion, where this 10 is multiplied by num. The result of 100 is returned to the first call to Power(), which also multiplies the result by num. The result of 1000 is finally returned to your original call.

Recursion and the Stack

As you shall soon see, recursion is useful for more than solving simple mathematical problems. Recursion is also used in sorting, tree-traversal, parsing and solving complex mathematical expressions, managing disk directories, and much more. In this chapter, you examine a tree-traversal routine. But first you have to know how recursive routines affect the stack and how this can get you into trouble.

Earlier in this chapter, in the section "Recursion: Barrels Within Barrels," you looked at a simple recursive function that ran endlessly because there was no way to break out of the recursion. This function called itself repeatedly until it ran out of stack space. What does the stack have to do with recursion?

Every time a function is called, certain values are placed on the stack. These values are part of something called a stack frame. They include the parameters being passed to the particular function and the address to which the program should return after the function ends. The stack has only a limited amount of space, so it can hold only so many stack frames. When a recursive function calls itself too often, the stack fills with stack frames, until no space is left. And when the stack overflows, the program drops dead.

Listing 34.5 is a program that calls a recursive function containing no conditional with which it can break out of the recursion. Each invocation of the Recursive() function prints the call number on-screen, so you can see that the program is actually doing something.

ON THE WEB

http://www.quecorp.com/semfc The complete source code and executable file for the Stack1 application can be found in the CHAP34\Stack1 directory at this book's Web site.

Listing 34.5 STACK1.CPP Version 1 of the Stack Overflow Program
#include <iostream.h>
void Recursive(int c)
{
    cout << c << ' ';
    Recursive(c+1);
}
void main(void)
{
    Recursive(1);
}
If you run this program under DOS, you see that it calls Recursive() approximately 8000 times before it runs out of stack space. (If you run the program in a DOS box under Windows 95, it'll go a long, long time before it runs out of stack place, thanks to the huge amount of virtual memory Windows 95 allots a running program.)

Listing 34.6 is the same program, only this time the Recursive() function takes three parameters instead of one. By having more parameters, a call to Recursive() generates larger stack frames. Each call uses more stack space, so this program can call the function only about 5000 times (when running under DOS) before it runs out of stack space.

ON THE WEB

http://www.quecorp.com/semfc The complete source code and executable file for the Stack2 application can be found in the CHAP34\Stack2 directory at this book'sWeb site.

Listing 34.6 STACK2.CPP Version 2 of the Stack Overflow Program
#include <iostream.h>
void Recursive(int c, int c2, int c3)
{
    cout << c << ' ';
    Recursive(c+1, c2, c3);
}
void main(void)
{
    Recursive(1, 1, 1);
}
As you already know, every recursive function needs a conditional statement that eventually ends the recursion, something Listings 34.5 and 34.6 are missing. Listing 34.7 adds such a conditional statement that allows only 5000 recursions.

ON THE WEB

http://www.quecorp.com/semfc The complete source code and executable file for the Stack3 application can be found in the CHAP34\Stack3 directory at this book's Web site.

Listing 34.7 STACK3.CPP Version 3 of the Stack Overflow Program
#include <iostream.h>
void Recursive(int c, int c2, int c3)
{
    cout << c << ' ';
    if (c==5000)
        return;
    Recursive(c+1, c2, c3);
}
void main(void)
{
    Recursive(1, 1, 1);
}
Does this solve your stack problem? Yes and no. As long as you don't change the size of the stack or add additional parameters to the Recursive() function, you should have no trouble with the stack. Listing 34.8 shows that adding even a single integer parameter can get you into trouble, by overflowing the stack.

ON THE WEB

http://www.quecorp.com/semfc The complete source code and executable file for the Stack4 application can be found in the CHAP34\Stack4 directory at this book's Web site.

Listing 34.8 STACK4.CPP Version 4 of the Stack Overflow Program
#include <iostream.h>
void Recursive(int c, int c2, int c3, int c4)
{
    cout << c << ' ';
    if (c>5000)
        return;
    Recursive(c+1, c2, c3, c4);
}
void main(void)
{
    Recursive(1, 1, 1, 1);
}


Always be aware that you place a lot of data on the stack when using recursive routines. Moreover, the more parameters required by the recursive routines, the fewer number of stack frames that fit on the stack, limiting even further the number of recursive calls you can make. To avoid stack problems, recursive functions should use as few parameters as possible. Be especially careful of passing large data structures such as arrays as parameters in a recursive function. If you need to use a large data structure as a parameter to a recursive function, pass it by reference (which passes only the data's address) not by value (which passes the contents of the entire data structure).

An Example Application: Trap Hunt

That takes care of all the work. Now you can have a little fun. Listings 34.9 and 34.10 show the source code (only the application and main-window classes) for a puzzle game called Trap Hunt. When you compile and run the program, the main window appears. Choose the File, Start command to start a new game. When you do, the game screen appears with 400 buttons in a 25x16 grid (see Figure 34.2). To win the game, you must find the 60 traps hidden under these buttons.


FIG. 34.2 

The game board contains 400 buttons.

Each square on the game board contains one of three things: a trap, a number, or a blank. To start, click a button on the game board with your left mouse button (not the right button). If the button you choose reveals a trap, you lose the game (whew, that was fast!), and the entire game board is revealed (see Figure 34.3).


FIG. 34.3 

Clicking on a trap ends the game and displays the entire game board.

If the button reveals a blank square, every blank square connected to it is shown, up to and including bordering number squares (Figure 34.4). If a button reveals a number, it informs you of the number of traps adjacent to the selected button.


FIG. 34.4 

Clicking a button that hides a blank square clears a chunk of the board and gives you a lot of additional number clues.

Try to locate all of the traps by using the number clues. When you locate a trapped button, click it with the right mouse button (not the left button). This marks the button with a blue X and locks the button so it can no longer be clicked (see Figure 34.5). You are apportioned only 60 markers, exactly enough for the traps, so you can't waste even one. If you use your markers before you've located all the traps, the game ends. Figure 34.6 shows the game board after the player has located all the traps.


FIG. 34.5 

Right-clicking a button locks it with a blue X. Right-click only the buttons that you know hide traps.

ON THE WEB

http://www.quecorp.com/semfc The complete source code and executable file for the TrapHunt application can be found in the CHAP34\TrapHunt directory at this book's Web site.

Listing 34.9 trapapp.cpp The Program's Application Class, CTrapApp
///////////////////////////////////////////////////////////
// TRAPAPP.CPP: Implementation file for the CTrapApp,
//              class, which represents the application
//              object.
///////////////////////////////////////////////////////////
#include <afxwin.h>
#include "trapapp.h"
#include "mainfrm.h"
// Global application object.
CTrapApp TrapApp;
///////////////////////////////////////////////////////////
// Construction/Destruction.
///////////////////////////////////////////////////////////
CTrapApp::CTrapApp()
{
}
///////////////////////////////////////////////////////////
// Overrides
///////////////////////////////////////////////////////////
BOOL CTrapApp::InitInstance()
{
    m_pMainWnd = new CMainFrame();
    m_pMainWnd->ShowWindow(m_nCmdShow);
    m_pMainWnd->UpdateWindow();
    return TRUE;
}
Listing 34.10 mainfrm.cpp The Program's Main Window Class, CMainFrame
///////////////////////////////////////////////////////////
// MAINFRM.CPP: Implementation file for the CMainFrame
//              class, which represents the application's
//              main window.
///////////////////////////////////////////////////////////
#include <afxwin.h>
#include "resource.h"
#include "mainfrm.h"
BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
    ON_WM_CREATE()
    ON_WM_PAINT()
    ON_WM_LBUTTONDOWN()
    ON_WM_RBUTTONDOWN()
    ON_COMMAND(ID_FILE_START, OnFileStart)
    ON_COMMAND(ID_HELP_ABOUTTRAPHUNT, OnHelpAbouttraphunt)
END_MESSAGE_MAP()
///////////////////////////////////////////////////////////
// CMainFrame: Construction and destruction.
///////////////////////////////////////////////////////////
CMainFrame::CMainFrame()
{
    // Create the main window.
    Create(NULL, "Trap Hunt",
        WS_OVERLAPPED | WS_SYSMENU | WS_CLIPCHILDREN,
        rectDefault, NULL, MAKEINTRESOURCE(IDR_MENU1));
}
CMainFrame::~CMainFrame()
{
    // Delete the bitmap from memory.
    delete m_pBitmap;
}
///////////////////////////////////////////////////////////
// Overrides.
///////////////////////////////////////////////////////////
BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)
{
    // Set size of the main window.
    cs.cx = 610;
    cs.cy = 432;
    // Call the base class's version.
    BOOL returnCode = CFrameWnd::PreCreateWindow(cs);
    return returnCode;
}
///////////////////////////////////////////////////////////
// System message map functions.
///////////////////////////////////////////////////////////
int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
    // Call base class's OnCreate() to be sure
    // the window's default initialization is performed.
    CFrameWnd::OnCreate(lpCreateStruct);
    
    // Get a device context for the window.    
    CClientDC clientDC(this);
    // Create a bitmap compatible with the window DC.
    m_pBitmap = new CBitmap;
    m_pBitmap->CreateCompatibleBitmap(&clientDC, 640, 480);
    // Clear the contents of the bitmap.
    ClearBitmap();
    // Set the game-over flag.
    m_gameOver = TRUE;
    return 0;
}
void CMainFrame::OnPaint()
{
    // Get a paint DC for the screen and bitmap.
    CPaintDC paintDC(this);
    CDC memDC;
    memDC.CreateCompatibleDC(&paintDC);
    // Select the bitmap into the memory DC.
    memDC.SelectObject(m_pBitmap);
    // Blit the bitmap onto the screen.
    paintDC.BitBlt(0, 0, 640, 480, &memDC, 0, 0, SRCCOPY);
}
void CMainFrame::OnLButtonDown(UINT nFlags, CPoint point) 
{
    // Translate mouse-button coords to column and
    // row coords for the playing board.
    int x = (point.x - XOFF) / SQUARESIZE;
    int y = (point.y - YOFF) / SQUARESIZE;
    // If the game is over, or the button is already pressed
    // or marked, ignore the mouse message.
    if ((m_gameOver) || (m_butn_stat[y][x] == STAT_PRESSED) ||
          (m_butn_stat[y][x] == STAT_MARKED))
        return;
    // If the button hides no trap, show the square.
    if (!(m_board[y][x] == TRAP))
        ShowSquare(x, y);
    // Check to see whether the game is over.
    m_gameOver = CheckForGameOver(x, y, TRUE);
}
void CMainFrame::OnRButtonDown(UINT nFlags, CPoint point) 
{
    // Translate mouse-button coords to column and
    // row coords for the playing board.
    int x = (point.x - XOFF) / SQUARESIZE;
    int y = (point.y - YOFF) / SQUARESIZE;
    // If the game is over, or the button is already pressed
    // or marked, ignore the mouse message.
    if ((m_gameOver) || (m_butn_stat[y][x] == STAT_PRESSED) ||
          (m_butn_stat[y][x] == STAT_MARKED))
        return;
    // Mark the selected button.
    MarkButton(x, y);
    // Check whether the game is over.
    m_gameOver = CheckForGameOver(x, y, FALSE);
}
///////////////////////////////////////////////////////////
// Command message map functions.
///////////////////////////////////////////////////////////
void CMainFrame::OnFileStart()
{
    // Initialize the random number generator.
    srand((unsigned)time(NULL));
    // Set the entire game board to blanks and set the
    // button-status array to indicate no buttons are pressed.
    for (int col=0; col<MAXCOLS; ++col)
        for (int row=0; row<MAXROWS; ++row)
    {
            m_board[row][col] = BLANK;
            m_butn_stat[row][col] = STAT_NOTPRESSED;
    }
    // Place traps and numbers on game board.
    PlaceTraps();
    PlaceCounts();
    // Draw game screen and init some variables.
    DrawScreen();
    m_buttonsLeft = MAXCOLS * MAXROWS;
    m_markCnt = m_goodMarks = 0;
    m_gameOver = FALSE;
}
void CMainFrame::OnHelpAbouttraphunt()
{
    // Display the About dialog box.
    CDialog dialog(MAKEINTRESOURCE(IDD_ABOUTDIALOG), this);
    dialog.DoModal();
}
///////////////////////////////////////////////////////////
// Protected member functions.
///////////////////////////////////////////////////////////
void CMainFrame::ClearBitmap()
{
    // Get a client-window DC.
    CClientDC dc(this);
    // Create a memory DC compatible with the window DC.
    CDC memDC;
    memDC.CreateCompatibleDC(&dc);
    // Select the bitmap into the memory DC.
    memDC.SelectObject(m_pBitmap);
    // Clear the bitmap to light blue.
    CBrush brush(RGB(0,200,200));
    memDC.FillRect(CRect(0, 0, 639, 479), &brush);
}
void CMainFrame::DrawButton(UINT col, UINT row)
{
    // Create a DC for the window and a memory
    // DC compatible with the window DC.
    CClientDC clientDC(this);
    CDC memDC;
    memDC.CreateCompatibleDC(&clientDC);
    // Select the bitmap into the memory DC.
    memDC.SelectObject(m_pBitmap);
    // Create a pen and brush.
    CPen* pPen = new CPen(PS_SOLID, 2, RGB(255,180,180));
    CBrush* pBrush = new CBrush(RGB(128,128,128));
    // Select the pen and brush into both DCs.
    CPen* pOldPen = memDC.SelectObject(pPen);
    clientDC.SelectObject(pPen);
    CBrush* pOldBrush = memDC.SelectObject(pBrush);
    clientDC.SelectObject(pBrush);
    // Calculate the drawing coordinates.
    UINT drawCol = col * SQUARESIZE + XOFF;
    UINT drawRow = row * SQUARESIZE + YOFF;
    // Draw the button rectangle in both DCs.
    memDC.Rectangle(drawCol, drawRow,
        drawCol + SQUARESIZE - 1, drawRow + SQUARESIZE - 1);
    clientDC.Rectangle(drawCol, drawRow,
        drawCol + SQUARESIZE - 1, drawRow + SQUARESIZE - 1);
    // Draw the highlighted button edges.
    memDC.SelectObject(pOldPen);
    clientDC.SelectObject(pOldPen);
    delete pPen;
    pPen = new CPen(PS_SOLID, 2, RGB(200,200,200));
    memDC.SelectObject(pPen);
    clientDC.SelectObject(pPen);
    clientDC.MoveTo(drawCol, drawRow+SQUARESIZE-2);
    clientDC.LineTo(drawCol, drawRow);
    clientDC.LineTo(drawCol+SQUARESIZE-2, drawRow);
    memDC.MoveTo(drawCol, drawRow+SQUARESIZE-2);
    memDC.LineTo(drawCol, drawRow);
    memDC.LineTo(drawCol+SQUARESIZE-2, drawRow);
    // Draw the shadowed button edges.
    memDC.SelectObject(pOldPen);
    clientDC.SelectObject(pOldPen);
    delete pPen;
    pPen = new CPen(PS_SOLID, 2, RGB(50,50,50));
    memDC.SelectObject(pPen);
    clientDC.SelectObject(pPen);
    clientDC.MoveTo(drawCol, drawRow+SQUARESIZE-2);
    clientDC.LineTo(drawCol+SQUARESIZE-2, drawRow+SQUARESIZE-2);
    clientDC.LineTo(drawCol+SQUARESIZE-2, drawRow);
    memDC.MoveTo(drawCol, drawRow+SQUARESIZE-2);
    memDC.LineTo(drawCol+SQUARESIZE-2, drawRow+SQUARESIZE-2);
    memDC.LineTo(drawCol+SQUARESIZE-2, drawRow);
    // Restore DCs and delete the pen and brush.
    memDC.SelectObject(pOldPen);
    clientDC.SelectObject(pOldPen);
    memDC.SelectObject(pOldBrush);
    clientDC.SelectObject(pOldBrush);
    delete pPen;
    delete pBrush;
}
void CMainFrame::DrawPressedButton(UINT col, UINT row)
{
    // Create a DC for the window and a memory
    // DC compatible with the window DC.
    CClientDC clientDC(this);
    CDC memDC;
    memDC.CreateCompatibleDC(&clientDC);
    // Select the bitmap into the memory DC.
    memDC.SelectObject(m_pBitmap);
    // Create a pen and brush.
    CPen* pPen = new CPen(PS_SOLID, 2, RGB(0,200,200));
    CBrush* pBrush = new CBrush(RGB(0,200,200));
    // Select the pen and brush into both DCs.
    CPen* pOldPen = memDC.SelectObject(pPen);
    clientDC.SelectObject(pPen);
    CBrush* pOldBrush = memDC.SelectObject(pBrush);
    clientDC.SelectObject(pBrush);
    // Calculate the drawing coordinates.
    UINT drawCol = col * SQUARESIZE + XOFF;
    UINT drawRow = row * SQUARESIZE + YOFF;
    // Draw the rectangle in both DCs.
    memDC.Rectangle(drawCol, drawRow,
        drawCol + SQUARESIZE - 1, drawRow + SQUARESIZE - 1);
    clientDC.Rectangle(drawCol, drawRow,
        drawCol + SQUARESIZE - 1, drawRow + SQUARESIZE - 1);
    // Restore DCs and delete the pen and brush.
    memDC.SelectObject(pOldPen);
    clientDC.SelectObject(pOldPen);
    memDC.SelectObject(pOldBrush);
    clientDC.SelectObject(pOldBrush);
    delete pPen;
    delete pBrush;
}
void CMainFrame::PlaceTraps(void)
{
    // Loop for each trap on the board.
    for (int z=0; z<TRAP_CNT; ++z)
    {
        int okay = FALSE;
        // The while loop will repeat until the
        // trap is properly placed.
        while (!okay)
        {
            // Get a random column and row for the trap.
            int c = rand() % MAXCOLS;
            int r = rand() % MAXROWS;
            // If there isn't already a trap at this
            // location, calculate the maximum and minimum
            // coordinates for every square adjacent to
            // this one.
            if (m_board[r][c] != TRAP)
            {
                int yl = r - 1;
                int yh = r + 1;
                int xl = c - 1;
                int xh = c + 1;
                if (xl == -1)
                    xl = 0;
                if (xh == MAXCOLS)
                    xh = MAXCOLS-1;
                if (yl == -1)
                    yl = 0;
                if (yh == MAXROWS)
                    yh = MAXROWS-1;
                okay = TRUE;
                // Count the traps surrounding every adjacent
                // square to be sure that no trap count goes
                // over four.
                for (int y=yl; y<yh+1; ++y )
                    for (int x=xl; x<xh+1; ++x )
                    {
                        int n = CountTraps(x, y);
                        if (n > 3)
                            okay = FALSE;
                    }
                // If all trap counts are low enough,
                // place the trap.
                if (okay)
                    m_board[r][c] = TRAP;
            }
        }
    }
}
void CMainFrame::PlaceCounts(void)
{
     // Cycle through every square on the board,
     // counting adjacent traps.
     for (int row=0; row<MAXROWS; ++row)
        for (int col=0; col<MAXCOLS; ++col)
            if (m_board[row][col] != TRAP)
                m_board[row][col] = CountTraps(col, row);
}
int CMainFrame::CountTraps(int c, int r)
{
    // Calculate the minimum and maximum coords
    // for every square adjacent to the one we're
    // checking.
    int yl = r - 1;
    int yh = r + 1;
    int xl = c - 1;
    int xh = c + 1;
    if (xl == -1)
        xl = 0;
    if (xh == MAXCOLS)
        xh = MAXCOLS-1;
    if (yl == -1)
        yl = 0;
    if (yh == MAXROWS)
        yh = MAXROWS-1;
    // Count all traps in adjacent squares.
    int count = 0;
    for (int y=yl; y<yh+1; ++y)
        for (int x=xl; x<xh+1; ++x)
            if (((x != c) || (y != r)) &&
                  (m_board[y][x] == TRAP))
                ++count;
    return count;
}
void CMainFrame::DrawScreen(void)
{
    // Create and display all the game-board buttons.
    int butn_num = 0;
    for (int y=0; y<MAXROWS; ++y)
    {
        for (int x=0; x<MAXCOLS; ++x)
            DrawButton(x, y);
    }
}
void CMainFrame::ShowSquare (int x, int y)
{
    // Get the square's contents.
    int b = m_board[y][x];
    // If the square contains a blank, call the
    // function to show all connecting blanks.
    if (b == BLANK)
        DoBlanks(x, y);
    // Otherwise show the square's number.
    else DrawNumbers(x, y);
}
void CMainFrame::DoBlanks (int x, int y)
{
    // Press the button.
    DrawPressedButton(x, y);
    m_butn_stat[y][x] = STAT_PRESSED;
    m_buttonsLeft -= 1;
    // Move one square up.
    if (y != 0)
        Check4Blank(x, y-1);
    // Move one square up and to the right.
    if ((y != 0) && (x != MAXCOLS-1))
        Check4Blank(x+1, y-1);
    // Move one square right.
    if (x != MAXCOLS-1)
        Check4Blank(x+1, y);
    // Move one square down and to the right.
    if ((y != MAXROWS-1) && (x != MAXCOLS-1))
        Check4Blank(x+1, y+1);
    // Move one square down.
    if (y != MAXROWS-1)
        Check4Blank(x, y+1);
    // Move one square down and to the left.
    if ((y != MAXROWS-1) && (x != 0))
        Check4Blank(x-1, y+1);
    // Move one square left.
    if (x != 0)
        Check4Blank(x-1, y);
    // Move one square up and to the left.
    if ((y != 0) && (x != 0))
        Check4Blank(x-1, y-1);
}
void CMainFrame::Check4Blank(int x, int y)
{
    // If the button hides a blank and has not been pressed,
    // call DoBlanks() recursively for the button.
    if ((m_board[y][x] == BLANK) &&
          (m_butn_stat[y][x] == STAT_NOTPRESSED))
        DoBlanks (x, y);
    // ...else if the button isn't marked or pressed,
    // display the number clue.
    else if (!(m_butn_stat[y][x] == STAT_MARKED) &&
        !(m_butn_stat[y][x] == STAT_PRESSED))
        DrawNumbers (x, y);
}
void CMainFrame::DrawNumbers (int x, int y)
{
    // Press the button.
    DrawPressedButton(x, y);
    m_butn_stat[y][x] = STAT_PRESSED;
    m_buttonsLeft -= 1;
    // Create a DC for the window and a memory
    // DC compatible with the window DC.
    CClientDC clientDC(this);
    CDC memDC;
    memDC.CreateCompatibleDC(&clientDC);
    // Select the bitmap into the memory DC.
    memDC.SelectObject(m_pBitmap);
    // Get the number clue,
    // and calculate the drawing coordinates.
    int n = m_board[y][x];
    int sx = x*SQUARESIZE+XOFF;
    int sy = y*SQUARESIZE+YOFF;
    // Convert the number to a string.
    CString str;
    if (n == 1)
        str = "1";
    else if (n == 2)
        str = "2";
    else if (n == 3)
        str = "3";
    else
        str = "4";
    // Set the text background to transparent.
    memDC.SetBkMode(TRANSPARENT);
    clientDC.SetBkMode(TRANSPARENT);
    // Draw the number clue.
    memDC.TextOut(sx+7, sy+3, str);
    clientDC.TextOut(sx+7, sy+3, str);
}
void CMainFrame::ShowBoard()
{
    // Cycle through all the buttons on the board.
    for (int c=0; c<MAXCOLS; ++c)
    {
        for (int r=0; r<MAXROWS; ++r)
        {
            // If the square contains a trap and the
            // button was not marked, show the trap.
            if ((m_board[r][c] == TRAP) && (!(m_butn_stat[r][c] == STAT_MARKED)))
                DrawTrap(c, r);
            // If the button is marked, but the square doesn't
            // actually contain a trap, display the error symbol.
            else if ((m_butn_stat[r][c] == STAT_MARKED) &&
                     (m_board[r][c] != TRAP))
                DrawNoTrap(c, r);
            // If the square contains a number, show it.
            else if (m_board[r][c] > 0)
                DrawNumbers(c, r);
            // If the square contains a blank, show it.
            else if (m_board[r][c] == BLANK)
                DrawPressedButton(c, r);
        }
    }
}
void CMainFrame::DrawTrap(int x, int y)
{
    // Get client-window and memory DCs.
    CClientDC clientDC(this);
    CDC memDC;
    memDC.CreateCompatibleDC(&clientDC);
    // Select the bitmap into the memory DC.
    memDC.SelectObject(m_pBitmap);
    // Create and select a new brush into both DCs.
    CBrush newBrush(RGB(255, 0, 0));
    CBrush* oldBrush = clientDC.SelectObject(&newBrush);
    memDC.SelectObject(&newBrush);
    // Calculate the drawing coordinates.
    int sx = x*SQUARESIZE+XOFF;
    int sy = y*SQUARESIZE+YOFF;
    // Draw a red rectangle on the screen and on the bitmap.
    clientDC.Rectangle(sx+4, sy+4, sx+18, sy+18);
    memDC.Rectangle(sx+4, sy+4, sx+18, sy+18);
    // Restore the DCs.
    clientDC.SelectObject(oldBrush);
    memDC.SelectObject(oldBrush);
}
void CMainFrame::DrawNoTrap(int x, int y)
{
    // Get client-window and memory DCs.
    CClientDC clientDC(this);
    CDC memDC;
    memDC.CreateCompatibleDC(&clientDC);
    // Select the bitmap into the memory DC.
    memDC.SelectObject(m_pBitmap);
    // Calculate the drawing coordinates.
    int sx = x*SQUARESIZE+XOFF;
    int sy = y*SQUARESIZE+YOFF;
    // Draw a rectangle on the screen and on the bitmap.
    clientDC.Rectangle(sx+7, sy+7, sx+15, sy+15);
    memDC.Rectangle(sx+7, sy+7, sx+15, sy+15);
}
void CMainFrame::MarkButton(int x, int y)
{
    // Register the button as marked.
    m_butn_stat[y][x] = STAT_MARKED;
    m_buttonsLeft -= 1;
    m_markCnt += 1;
    if (m_board[y][x] == TRAP)
      m_goodMarks += 1;
    // Get client-window and memory DCs.
    CClientDC clientDC(this);
    CDC memDC;
    memDC.CreateCompatibleDC(&clientDC);
    // Select the bitmap into the memory DC.
    memDC.SelectObject(m_pBitmap);
    // Create and select a new pen into both DCs.
    CPen newPen(PS_SOLID, 2, RGB(0,0,255));
    CPen* oldPen = clientDC.SelectObject(&newPen);
    memDC.SelectObject(&newPen);
    // Calculate the drawing coordinates.
    int sx = x * SQUARESIZE + XOFF;
    int sy = y * SQUARESIZE + YOFF;
    // Draw an X on the button, both on the
    // screen and on the bitmap in memory.
    clientDC.MoveTo(sx+2, sy+2);
    clientDC.LineTo(sx+SQUARESIZE-4, sy+SQUARESIZE-4);
    clientDC.MoveTo(sx+SQUARESIZE-4, sy+2);
    clientDC.LineTo(sx+2, sy+SQUARESIZE-4);
    memDC.MoveTo(sx+2, sy+2);
    memDC.LineTo(sx+SQUARESIZE-4, sy+SQUARESIZE-4);
    memDC.MoveTo(sx+SQUARESIZE-4, sy+2);
    memDC.LineTo(sx+2, sy+SQUARESIZE-4);
    // Restore the DCs.
    clientDC.SelectObject(oldPen);
    memDC.SelectObject(oldPen);
}
BOOL CMainFrame::CheckForGameOver(int x, int y, BOOL checkForTrap)
{
    // If there are no buttons left or all the traps
    // have been marked, tell the player he won.
    if ((m_buttonsLeft == 0) || (m_goodMarks == TRAP_CNT))
    {
        MessageBox("You found all the traps.", "You Win!");
        return TRUE;
    }
    // ...else if the player has selected a button hiding a
    // trap, tell the player he lost the game.
    else if ((m_board[y][x] == TRAP) && (checkForTrap == TRUE))
    {
        DrawTrap(x, y);
        MessageBox("You fell into a trap.", "You Lose");
        ShowBoard();
        return TRUE;
    }
    // ...else if the player has used up all his
    // marks, tell the player he lost the game.
    else if (m_markCnt == TRAP_CNT)
    {
        MessageBox("You've used up your button marks.", "You Lose");
        ShowBoard();
        return TRUE;
    }
    return FALSE;
}

Programming with Trees

The Trap Hunt program contains an excellent example of recursion that you can study to get further insight into this handy and interesting programming technique. In a previous discussion of ways to use recursion, tree-traversal routines were mentioned. This is the type of recursion used in Trap Hunt.

What's a tree? A tree is a data structure that connects a collection of items, called nodes. A tree starts with a root node. Connected to the root are any number of child nodes. Each child node, too, can have any number of its own child nodes. This hierarchy continues down the tree until a child node has no children of its own.

Figure 34.6 shows a general binary tree (that is, this tree has nothing to do with the TrapHunt program), which is a special type of tree that has left and right children for every node except the base nodes. Node A is the root node. Nodes B and C, which are called siblings because they are on the same level of the tree, are A's child nodes. Nodes B and C also have two child nodes each, the base nodes D, E, F, and G.


FIG. 34.6 

Each node of a binary tree has exactly two child nodes.

Recursion is particularly useful for traversing trees that is, for following every path in the tree from the root to the base nodes. Listing 34.11 is a DOS program that creates and traverses the binary tree shown in Figure 34.6. The program's output follows:
At node A
At node B
At node D
At node E
At node C
At node F
At node G
ON THE WEB

http://www.quecorp.com/semfc The complete source code and executable file for the Tree application can be found in the CHAP34\Tree directory at this book's Web site.

Listing 34.11 TREE.CPP Creating the Binary Tree Shown in Figure 34.6
#include <stdlib.h>
#include <iostream.h>
#include <conio.h>
struct Node
{
    char name;
    Node *left, *right;
};
Node *tree;
void AddNodes(Node *node, char c1, char c2);
void TraverseTree(Node *n);
void main(void)
{
    tree = new Node;
    tree->name = 'A';
    AddNodes(tree, 'B', 'C');
    AddNodes(tree->left, 'D', 'E');
    AddNodes(tree->right, 'F', 'G');
    TraverseTree(tree);
    delete tree;
    getch();
}
void AddNodes(Node *node, char c1, char c2)
{
    Node *n = new Node;
    n->name = c1;
    n->left = NULL;
    n->right = NULL;
    node->left = n;
    n = new Node;
    n->name = c2;
    n->left = NULL;
    n->right = NULL;
    node->right = n;
}
void TraverseTree(Node *n)
{
    cout << "At node " << n->name << endl;
    if (n->left)
    {
        TraverseTree(n->left);
        delete n->left;
    }
    if (n->right)
    {
        TraverseTree(n->right);
        delete n->right;
    }
}
The program implements a node as a struct containing the node's label and pointers to the node's left and right children. In main(), the program first creates the tree's root node, which is appropriately named tree. Then it calls the AddNodes() function to create two child nodes for tree. The program also calls AddNodes() (indirectly by way of the tree->left and tree->right pointers) for each of tree's child nodes to create their own child nodes. The operations here are similar to those you learned when studying linked lists.


See ?Linked Lists,? (ch. 30)

There should be no need to go into the details of the tree construction. What you must examine closely, though, is the recursive procedure that traverses the tree structure. In Listing 34.11, that function is TraverseTree().

Here's how the recursion works:
1. The program calls TraverseTree() from main() with tree, which is a pointer to the tree's root node.

2. In TraverseTree(), the function first prints a message, showing which node it's currently examining. In this case, the node is A.

3. Then the function checks node A's left pointer. If it's not NULL, A has a left child, so the function calls TraverseTree() recursively to check that left child, which is B.

4. This call initiates a second invocation of TraverseTree(), in which a message for node B is printed and node B's left pointer is checked.

5. Because node B also has a left child, the program calls TraverseTree() yet again, this time for node D. In this third invocation of TraverseTree(), the program prints D's message and checks its left pointer.

6. D has no left child, so the program drops out of the first if and checks D's right pointer. D has no right child either. So, the third invocation of TraverseTree() ends, and the program is back to the second, where it last checked B's left pointer.

7. The program is now finished with B's left child, D, so it deletes it and checks B's right pointer, only to discover that it has a right child, E. This means the program must call TraverseTree() to examine node E.

8. Because node E, like node D, has no left or right children, the program promptly returns to B, where it deletes E and steps back to the first invocation of TraverseTree().

9. The program had last checked A's left pointer, so it can delete that left child and move to A's right child, C.

10. The right side of the tree is traversed the same way that the left side was, by visiting C, F, and finally G.

11. At the end of the traversal, the program returns to A with all nodes examined and all nodes deleted, except the root node. The root node, tree, is deleted in main().

Trap Hunt's Trees

Trap Hunt uses trees. How? When the player selects a blank square, the program must reveal all blank squares connected to it, as well as any number squares adjacent to blank squares. It does this by forming a tree and traversing the tree recursively.

The first step in forming the tree is to select the tree's root. Trap Hunt makes the square selected by the player the root of the tree. When the program has selected this root node, all other squares on the board fall logically into a tree pattern (not a binary tree), as you'll soon see. No matter which square the user selects, the remaining squares can be thought of as a tree structure with the selected square as the root.

The program then calls a recursive routine to traverse the tree, starting at the root. Any node in the tree can have as many as seven child nodes. A child node, in this case, is an unpressed button covering either another blank square or a number. Number squares are the tree's base nodes that is, the traversal never goes past a number square.

This tree traversal is more complex than the first example. In the binary tree, the program had to examine only left and right pointers for each node in a tree. In the game-board tree, the program must examine nodes in eight directions: up, up-right, right, right-down, down, left-down, left, and left-up. Still, except for extra recursive calls to the additional directions, the process is identical to the one you used for binary trees.

Two functions in the Trap Hunt program accomplish the tree traversal. They are DoBlanks() and Check4Blank(), shown in Listing 34.12:

Listing 34.12 lst34_12.cpp The Functions that Perform Trap Hunt's Recursive Tree Traversal
void CMainFrame::DoBlanks (int x, int y)
{
    // Press the button.
    DrawPressedButton(x, y);
    m_butn_stat[y][x] = STAT_PRESSED;
    m_buttonsLeft -= 1;
    // Move one square up.
    if (y != 0)
        Check4Blank(x, y-1);
    // Move one square up and to the right.
    if ((y != 0) && (x != MAXCOLS-1))
        Check4Blank(x+1, y-1);
    // Move one square right.
    if (x != MAXCOLS-1)
        Check4Blank(x+1, y);
    // Move one square down and to the right.
    if ((y != MAXROWS-1) && (x != MAXCOLS-1))
        Check4Blank(x+1, y+1);
    // Move one square down.
    if (y != MAXROWS-1)
        Check4Blank(x, y+1);
    // Move one square down and to the left.
    if ((y != MAXROWS-1) && (x != 0))
        Check4Blank(x-1, y+1);
    // Move one square left.
    if (x != 0)
        Check4Blank(x-1, y);
    // Move one square up and to the left.
    if ((y != 0) && (x != 0))
        Check4Blank(x-1, y-1);
}
void CMainFrame::Check4Blank(int x, int y)
{
    // If the button hides a blank and has not been pressed,
    // call DoBlanks() recursively for the button.
    if ((m_board[y][x] == BLANK) &&
          (m_butn_stat[y][x] == STAT_NOTPRESSED))
        DoBlanks (x, y);
    // ...else if the button isn't marked or pressed,
    // display the number clue.
    else if (!(m_butn_stat[y][x] == STAT_MARKED) &&
        !(m_butn_stat[y][x] == STAT_PRESSED))
        DrawNumbers (x, y);
}
Although the code in Listing 34.12 performs a recursive traversal of your game board's tree, there are no calls to DoBlanks() inside DoBlanks() and no calls to Check4Blank() inside Check4Blank(). How, then, is this routine recursive? Easy! DoBlanks() calls Check4Blank(), which then calls DoBlanks(). This circular pattern is recursive because new calls to DoBlanks() are made before previous invocations of DoBlanks() have ended. Neither of these functions is recursive, but together they form a recursive routine.

The if statements in the DoBlanks() function check that the recursion doesn't overrun the boundary of the game board. DoBlanks() also makes sure that all eight directions are checked. DoBlanks() selects the next square in the traversal and passes it to Check4Blank(), which decides what to do with the square. If the square is a blank and its button hasn't been pressed, Check4Blank() calls DoBlanks() recursively for the new blank square. Otherwise, if the square's button hasn't been pressed or marked, Check4Blank() calls DrawNumbers() to reveal the square's number.

This is probably very confusing, not because the concept is difficult to understand, but because it is difficult to follow the many recursions needed to traverse the tree. To help you understand Trap Hunt's tree-traversal routine, try the exercise in Figure 34.7, which shows a Trap Hunt grid of buttons immediately after the player has selected a blank square.


FIG. 34.7 

See if you can solve this tree traversal exercise.

At the point shown in the figure, the program has traversed the game-board tree, revealing blank squares and bordering number squares. The large black rectangle is the square that the player originally chose. (During the game, there is no black rectangle. It was added to the figure for the exercise.) Get a pencil and draw the path that the traversal took to reveal the squares, using the source code for the DoBlanks() and Check4Blank() functions.


Start the traversal by moving upward from the selected square. If you run into a numbered square, back up and try the next direction. Every new blank square you run into starts the process over again, because it results in a recursive call to DoBlanks().

To get you started, Figure 34.8 shows the first 14 squares in the traversal. The entire traversal is shown in Figure 34.9.


Figure 34.8 

Here are the first fourteen steps in the tree traversal.


Figure 34.9 

Here is the complete tree traversal.

The exercise in Figure 34.7 might look like an immense task, but after you get the hang of it, you will be able to trace the traversal without even looking at the source code. When you can do that, you will have a good understanding of how recursive tree-traversal works (which is the whole point). And when you have that understanding, you'll be ready to use recursion, where applicable, to solve your own programming problems.