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.
-
Learn how recursion can simplify programming problems
Recursion enables you to take a complex, repetitive task and break it into
simple steps.
-
Study useful examples of recursion
Recursion can be used in many ways traversing data trees, parsing text,
solving mathematical problems, and more.
-
Discover how to avoid stack problems when using recursion
Because recursion involves calling a function from itself again and again,
you have to consider how much space is available on the stack.
-
Learn about trees and tree traversals
Trees are a great way to organize certain types of data. To use trees,
however, you need to understand new programming techniques.
-
Use recursion to write a familiar game program
Trap Hunt, a game you'll program in this chapter, not only illustrates
recursive tree traversal, but also answers the question "How the heck
do they do that?"
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 recursive function calls itself.
-
A recursive function must contain a conditional statement that breaks
the recursive cycle.
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.