Not necessarily true @ being faster, especially if you have large or shared vars.
Note that you are also limited by the stack size.
On VS, it is by default 64kb.
My program used to crash in recursive folder traversal, since I stored their path in a 4kb var on the stack.
Each call required more stack space, and once it got filled, it caused a crash.
Recursive approaches can be dangerous because there isn't really a good way to tell how much stack space you're using, and so you won't know if you've going over your limit until it's too late.
It's much harder to run out of heap space, and when you do, behavior is clearly defined (throw an exception) so it can be worked with.
So on extremely large scale algorithms, I would shy away from recursive approaches.
That said... they would have to be extremely large scale for it to make a difference (or you'd have to be wastefully burning stack space as per EssGeEich's 4K on the stack example).
@Disch.
I added the int fillOrigin member to the underlying boardSpace class and gave it an initial value of 1 (it looked like it just needed to be >0) then tested your iterative clearSpace function.
It works!
Nice job nailing it in one shot and with no way of testing it!
Here's how I'd unfold the recursion so that the corresponding algorithm does the same but only in a slightly different order. Of course, I am simply manually "unfolding the stack". In this case, the stack is called squares. Note that the resulting code is of equal length (this is often the case with recursions with only few local variables).
The code hasn't been tested so please take it with a grain of salt.
#include <iostream>
#include <vector>
int main()
{ return 0;
}
struct Square
{ int cnt;
bool revealed;
bool isMined;
};
std::vector<std::vector<Square> > ppField;
int rows, cols;
struct coordinates
{ int row;
int column;
coordinates(int i, int j):row(i), column(j) {}
};
void clearSpace(int r, int c)
{ std::vector<coordinates> squares;
squares.push_back(coordinates(r,c));
for (unsigned i=0; i<squares.size(); i++)
{ int currentRow= squares[i].row;
int currentColumn=squares[i].column;
if (ppField[currentRow][currentColumn].revealed)
continue;
ppField[currentRow][currentColumn].revealed=true;
// was a space with zero mines around it hit?
if(ppField[currentRow][currentColumn].cnt != '0' )
continue;
// clear the 8 spaces around this space
if( currentRow>0 )// 3 across the top
{ if( currentColumn>0 )//left-top
squares.push_back(coordinates(currentRow-1, currentColumn-1));
if (currentColumn< cols-1)//right-top
squares.push_back(coordinates(currentRow-1, currentColumn+1));
//top
squares.push_back(coordinates(currentRow-1, currentColumn));
}
if( currentRow<rows-1 )// 3 across the bottom
{ if( currentColumn>0 )//bottom-left
squares.push_back(coordinates(currentRow+1, currentColumn-1));
if( currentColumn<cols-1 ) //bottom-right
squares.push_back(coordinates(currentRow+1, currentColumn+1));
//bottom
squares.push_back(coordinates(currentRow+1, currentColumn));
}
// same row
if( c>0 )//left
squares.push_back(coordinates(currentRow, currentColumn-1));
if( c<cols-1 )//right
squares.push_back(coordinates(currentRow, currentColumn+1));
}
}
@ tition.
Your solution works fine. It didn't fit my code so I wrote a separate test program.
See here which includes some test output:
http://codepad.org/dyh9JWJK