Maximum Size of Recursive Fill

[anup30]

my following program fills continuous elements in 2d array recursively. but it worked only for N<180. why doesn't it work for bigger size?

// Recursive fill
// 30.1.2015
#include<iostream>
#include<array>
const int N = 179;
using namespace std;


void Fill( array<array<bool,N>,N> &arr, int i, int j){
	
	arr[i][j]=1;
	
	if(i+1>=0 && i+1<N &&  arr[i+1][j] == 0 ) {		
		Fill(arr, ++i, j);	
		//--i;
	}
	
	if(j+1>=0 && j+1<N &&  arr[i][j+1] == 0 ) {			
		Fill(arr, i, ++j);
		//--j;	
	}
	
	if(i-1>=0 && i-1<N &&  arr[i-1][j] == 0 ) {	
		Fill(arr, --i, j);	
		//++i;
	}
		
	if(j-1>=0 && j-1<N &&  arr[i][j-1] == 0 ) {			
		Fill(arr, i, --j);		
		//++j;	
	}	
}

int main(){	

	freopen("grun.txt","w",stdout);
	
	array<array<bool,N>,N> arr;
	
	for(auto &R:arr) for(auto &C:R) {
		C=0;
	}	

	int x=0, y=0;
	Fill(arr, x, y); // fill starts from (0,0)
	
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			cout << arr[i][j] << "";
		}
		cout << endl;		
	}

return 0;	
}

[Smac89]

Can't tell you why your code doesn't work, but my guess would probably be that you reached the imposed recursion limit of the program.

Easy fix - don't use recursion and make use of already built in functions:

array<array<bool,N>,N> arr;
for (auto &row: arr) { 
    row.fill(true);
}

[anup30]

i can't use fill()
because, i need to fill continuous only.
for example: x,y is given by user, i.e. x,y = 0,0
then,

00000100
00001000
00001000
00011111

changes to

11111100
11111000
11111000
11111111

it wont change non-connected zeros.
what would be the algorithm?

[ne555]

http://en.wikipedia.org/wiki/Depth-first_search#Pseudocode


By the way, in line 14 you are modifying the `i' variable, changing the definition of neighbourhood, then you tried to fix it by make the inverse operation on it.
If you don't want to modify a variable, then don't modify it.
Fill(arr, i+1, j);

[dhayden]

I suspect that recursion depth of 180 shouldn't be a problem. I think the real problem here is that you're modifying i and j as you go. Just pass the updated values instead:

void Fill( array<array<bool,N>,N> &arr, int i, int j){
	
	arr[i][j]=1;
	
	if(i+1>=0 && i+1<N &&  arr[i+1][j] == 0 ) {		
		Fill(arr, i+1, j);	
	}
	
	if(j+1>=0 && j+1<N &&  arr[i][j+1] == 0 ) {			
		Fill(arr, i, j+1);
	}
	
	if(i-1>=0 && i-1<N &&  arr[i-1][j] == 0 ) {	
		Fill(arr, i-1, j);	
	}
		
	if(j-1>=0 && j-1<N &&  arr[i][j-1] == 0 ) {			
		Fill(arr, i, j-1);		
	}	
}

The code would be a little slower but a whole lot smaller if you did the checks inside the recursive calls:

void Fill( array<array<bool,N>,N> &arr, int i, int j){
	// If the index is out of bounds then exit
	if (i<0 || i>= N) return;
	if (j<0 || j>= N) return;

	// If the square is already set then exit.
	if (arr[i][j]) return;

	// Set the square and recursively set the neighbors
	arr[i][j]=1;
	Fill(arr, i+1, j);	
	Fill(arr, i, j+1);
	Fill(arr, i-1, j);	
	Fill(arr, i, j-1);		
}

[anup30]

still doesn't work for N>=179 in my gcc 4.8.1, for N>=68 in VS 2012
but worked for N=400 in http://cpp.sh/

// Recursive fill
#include<iostream>
#include<array>
#include<cstdio>
const int N = 200; // maximum ok value, 67 for VS 2012,   178 for GCC 4.8
using namespace std;


void Fill( array<array<bool,N>,N> &arr, int i, int j){
	
	arr[i][j]=1;
	
	if(i+1>=0 && i+1<N &&  arr[i+1][j] == 0) Fill(arr, i+1, j);	
	
	if(j+1>=0 && j+1<N &&  arr[i][j+1] == 0) Fill(arr, i, j+1);	
		
	if(i-1>=0 && i-1<N &&  arr[i-1][j] == 0) Fill(arr, i-1, j);	
			
	if(j-1>=0 && j-1<N &&  arr[i][j-1] == 0) Fill(arr, i, j-1);				
	
}

int main(){	

	//freopen("grun.cpp","w",stdout);
	
	array<array<bool,N>,N> arr;
	
	for(auto &R:arr) for(auto &C:R) {
		C=0; //sel all zero
	}	

	int x=0, y=0;
	Fill(arr, x, y); // fill starts from (0,0)
	
	/* //print
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			cout << arr[i][j] << "";
		}
		cout << endl;		
	}
	*/

return 0;	
}

[anup30]

same result for dhayden's code.

and i don't understand one thing:
if i shorten dhayden's

if (i<0 || i>= N) return;
if (j<0 || j>= N) return;

by if(i<0 || i>=N || j<0 || j>=0) return;

then there is no 1 ?!
whats the difference with the short version?

[dhayden]

I added some code to check the recursion depth. On my PC it died at a depth of 25776 with N=200. So it appears that you get a recursive call depth that basically snakes its way through the whole thing. If you think about this, it makes sense. There are no loops in the code so when you fill the last square, there must be a recursive chain covering all squares - yuck.

I think you're going to have to do more in each call. Maybe fill in everything that's reachable in the 4 directions and then recurse on those squares.

[anup30]

but, what about the 4 comparisons ored together ?
for small N 2 separate line works fine, but for one line all outputs are 0.

[dhayden]

It's failing because you're exceeding the size of the stack. The logic is just fine. Hmm. So I guess the easiest thing to do here is give your program more stack space. This will be an option to the compiler or linker. Try giving it like 10MB.

[Smac89]

#include<iostream>
#include<array>
const int N = 179;
using namespace std;

void fill( array<array<bool,N>,N> &arr, int x, int y) {

    for (int w = x; w < arr.size(); w++) {
        bool value = arr[w][y];
        for (int t = y; t < arr[w].size() && arr[w][t] == value; t++) {
            arr[w][t] = !value;
        }
    }
}

void fill_rec(array<array<bool, N>, N> &arr, int x, int y, bool initvalue) {
    if (x >= arr.size() || y >= arr[x].size())
        return;

    if (arr[x][y] == initvalue) {
        arr[x][y] = !initvalue;
        y++;
    }

    if (y + 1 >= arr[x].size() || arr[x][y] != initvalue) {
        y = 0;
        x++;
    }

    fill_rec(arr, x, y, initvalue);
}

void fill_rec( array<array<bool,N>,N> &arr, int x, int y) {
    fill_rec(arr, x, y, arr[x][y]);
}

[anup30]

seems a complicated matter!
@Smac89: not solved yet :(

i don't understand the thing of maximum memory allocation to your exe.
the following program runs easily consuming 500 MB ram

#include<iostream>
#include<vector>
const int N = 8000; 
using namespace std;

int main(){
	
	vector<pair<int,int>> vect;
	int NN = N*N;
	vect.reserve(NN);
	for(int i=0; i<NN; i++){
		vect.emplace_back(make_pair(0,0));
	}	

	cout << "dd\n";
	
	cin.ignore();

return 0;	
}

[dhayden]

i don't understand the thing of maximum memory allocation to your exe.
the following program runs easily consuming 500 MB ram

Programs use different areas of memory. Your example program consumes of 500MB of heap space, but the stack size is different. The operating system allocates a much smaller amount of memory to the stack.

[ne555]

@Smac89: please comment your code.
¿what's your `fill()' function for?
It seems like a flood_fill, but it ignores the left and upper directions.

¿what does `fill_rec()' do?
¿why does `fill_rec()' reset y to 0? and again what about the left and upper directions


@OP: try a non-recursive approach already.

[anup30]

is there any library facility (container?) which provides random access+modify+ resizable+stored in non-sequence heap memory ?