Recursion! do you use it? how can I introduce it gradualy into my code?

[S G H]

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.

[Disch]

To add on to what EssGeEich is saying:

Stack space is free until you run out.

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).

[D80DSL3A]

@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!

[tition]

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));
  }
}

[chrisname]

tition wrote:

No, it wasn't, what is a recursive descent parser?

It's a type of LL(k) parser that uses mutual recursion (f calls g calls h calls f). A recursive version of an LALR parser would be similar.

[D80DSL3A]

@ 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