Остановите рекурсивную функцию, когда она достигнет большой глубины в c

Question

Я хочу остановить рекурсивную функцию, когда она достигнет глубины 3000.как мне это сделать?

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

    }

Когда я добавил счетчик, я попытался вернуть его, когда он был 3000, но я не могу сказать, что я был очень успешным.

У меня есть512 * 512 матрица, и я ищу остров в этой матрице.Рекурсивная функция выдает ошибку, если площадь одного из островов превышает 10000 единиц.

Answer 1

Я хочу остановить рекурсивную функцию, когда она достигнет глубины 3000

Общим решением этого является добавление аргумента "глубины" в функцию и передача depth + 1 вкаждый рекурсивный вызов (или remaining_depth - 1, если вы хотите считать в обратном направлении).Чтобы скрыть это от внешнего API, сделайте открытую функцию - без аргумента глубины - просто вызовите фактическую функцию с начальным значением для depth.

Например:

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

Answer 2

Почему бы не набрать !isSafe() в начале?Вы получите те же результаты, если у вас есть вызовы isSafe() внутри операторов if.Перемещая isSafe () в начале, вы улучшаете читабельность кода, избегая дублирования кода, и вы менее подвержены ошибкам.Таким образом, он будет выполнять только оператор return ничего больше.

Теперь идет часть, которую вы просили глубины.

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

Теперь, когда я думаю, что я согласен с точкой @Tudors относительно for loop, но я оставлю это здесь как способ переписать ваш код, используя гораздо лучший синтаксис.

Answer 3

Прежде всего, for не имеет смысла, если вы нашли время, чтобы написать четыре разных if для соседей.Каждый из них будет выполнен один раз в любом случае.

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

Это должно сработать.Переменная глубины будет подсчитывать количество обращений к DFS, и каждый раз, когда она возвращается, вы уменьшаете значение. Однако это не лучший подход , потому что в некоторых случаях это может вызвать проблемы.Единственное, о чем я могу думать, это когда вы используете исключения.Потому что они выйдут из вашей функции и не уменьшат переменную глубины.

Другой подход - сохранить глубину в качестве параметра, но это делает функцию многословной для вызова.