CODEWITHSUNDEEP
crecursion
XLVII
XLVII

Reputation: 141

Stop the recursive function when it reaches high depth in c

I want to stop the recursive function when it reaches 3000 depth. how do I do it?

 void DFS(bool M[][COL], int row, int col) 
    { 
        short k;

        M[row][col] = 0; 

        for (k = 0; k < 4; k++){
            if(k==0){
                if (isSafe(M, row , col - 1) ){
                    DFS(M, row , col - 1);
                }
            }
            if(k==1){
                if (isSafe(M, row , col + 1) ){         

                   DFS(M, row , col + 1);
                }
            }
            if(k==2){
                if (isSafe(M, row + 1, col) ){          
                    DFS(M, row + 1, col);
                }
            }
            if(k==3){
                if (isSafe(M, row - 1 , col) ){         
                    DFS(M, row - 1, col);
                }
            }
        }

    }

When I added the counter, I tried to return it when it was 3000, but I can't say I was very successful.

I have 512 * 512 matrix and I am looking for an island in this matrix. The recursive function gives the error if one of the island's area is more than 10000 units.

Upvotes: 1

Views: 829

Answers (3)

user5550963
user5550963

Reputation:

Why not have !isSafe() call at the beginning? You will get same results, if you have with calls to isSafe() inside if statements. By moving isSafe () at the beginning you improve code readability by avoiding duplicate code, and you are less prone to errors. This way it will execute only return statement nothing else.

Now comes the part you were asking for depth.

void DFS(bool M[][COL], int row, int col)  {
    static int depth = 0;

    if ( !isSafe(M, row , col) || depth > 3000)
        return;

    depth++;

    short k;

    M[row][col] = 0; 

    for (k = 0; k < 4; k++)
        switch (k)
            case 0 :
                DFS(M, row , col - 1);
                break;
            case 1 :
               DFS(M, row , col + 1);
               break;
            case 2 :
                DFS(M, row + 1, col);
                break;
            case 3 :
                DFS(M, row - 1, col);
                break;
            default :
                return;
}

Now that I think I do agree with @Tudors point about for loop, but I will leave this here as a way to rewrite your code using much better syntax.

Upvotes: 1

Arkku
Arkku

Reputation: 42149

I want to stop the recursive function when it reaches 3000 depth

A general solution to this is to add a "depth" argument to the function, and pass depth + 1 to each recursive call (or remaining_depth - 1 if you want to count backwards). To hide this from an outward-facing API, make the public function – without the depth argument – simply call the actual function with the initial value for depth.

For example:

#define MAX_DEPTH 3000

static void dfs_(bool M[][COL], int row, int col, int depth) {
    if (!isSafe(M, row, col)) { return; }
    M[row][col] = 0;
    if (depth >= MAX_DEPTH) { return; }
    dfs_(M, row, col - 1, depth + 1);
    dfs_(M, row, col + 1, depth + 1);
    dfs_(M, row - 1, col, depth + 1);
    dfs_(M, row + 1, col, depth + 1);
}

void DFS(bool M[][COL], int row, int col) {
    dfs_(M, row, col, 1);
}

Upvotes: 6

Tudor Versoiu
Tudor Versoiu

Reputation: 122

First of all, the for is pointless if you took the time to write four different if's for the neighbours. They will each execute once anyways.

void DFS(bool M[][COL], int row, int col) 
{ 
    static int depth = 0;
    ++depth;
    if (depth > 3000)
    {
        --depth;
        return;
    }

    M[row][col] = 0; 
    if (isSafe(M, row , col - 1) )
        DFS(M, row , col - 1);

    if (isSafe(M, row , col + 1) )       
       DFS(M, row , col + 1);

    if (isSafe(M, row + 1, col) )     
        DFS(M, row + 1, col);

    if (isSafe(M, row - 1 , col) )        
        DFS(M, row - 1, col);

    --depth;
    return;
}

This should work. The depth variable will count the number of calls to DFS, and everytime it returns, you decrement the value. However this is not be the best approach because there are cases where it may cause problems. The only one I can think of is when you use exceptions. Because they will exit your function and not decrement the depth variable.

Another approach is keeping the depth as a parameter, but it makes the function verbose to call.

Upvotes: 2

Related Questions