Как обнаружить бесконечный цикл в рекурсивном вызове?

Question

У меня есть функция, которая рекурсивно вызывает себя, и я хочу обнаружить и завершить ее, если перейдет в бесконечный цикл, то есть снова вызову той же проблемы. Какой самый простой способ сделать это?

РЕДАКТИРОВАТЬ: это функция, и она будет вызываться рекурсивно с различными значениями х и у. я хочу завершить, если в рекурсивном вызове значение пары (x, y) повторяется.

int fromPos(int [] arr, int x, int y)

Answer 1

Один из способов - передать переменную depth от одного вызова к другому, увеличивая ее каждый раз, когда ваша функция вызывает себя. Убедитесь, что depth не становится больше определенного порога. Пример:

int fromPos(int [] arr, int x, int y)
{
    return fromPos(arr, x, y, 0);
}

int fromPos(int [] arr, int x, int y, int depth)
{
    assert(depth < 10000);

    // Do stuff

    if (condition)
        return fromPos(arr, x+1, y+1, depth + 1);
    else
        return 0;
}

Answer 2

Если функция является чисто функциональной, то есть не имеет состояний или побочных эффектов, тогда вы можете сохранить Set аргументов (правка: видя ваши изменения, вы сохраните набор пар (x, y) ) что он был вызван, и каждый раз просто проверяйте, есть ли текущий аргумент в наборе. Таким образом, вы можете обнаружить цикл, если столкнетесь с ним довольно быстро. Но если пространство аргументов велико и повторение занимает много времени, вам может не хватить памяти, прежде чем вы обнаружите цикл. В общем, конечно, вы не можете сделать это, потому что это проблема остановки.

Answer 3

Вам нужно будет найти обходной путь, потому что, как вы и просили, общего решения не существует. См. Проблема остановки для получения дополнительной информации.

Answer 4

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

Answer 5

Простой способ - реализовать одно из следующих действий:

Передайте предыдущее значение и новое значение рекурсивному вызову и сделайте ваш первый шаг проверкой, чтобы убедиться, что они одинаковы - возможно, это ваш рекурсивный случай.

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

Answer 6

Вы можете использовать перегрузку для непротиворечивой подписи (это лучший метод) или статическую переменную:

int someFunc(int foo)
{
    static recursionDepth = 0;
    recursionDepth++;
    if (recursionDepth > 10000)
    {
        recurisonDepth = 0;
        return -1;
    }
    if (foo < 1000)
        someFunc(foo + 3);
    recursionDepth = 0;
    return foo;
}

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

Billy3

Answer 7

Сначала используйте mvn findbugs: gui, чтобы открыть графический интерфейс, указывающий на строку, где присутствует эта ошибка.

Я также столкнулся с той же проблемой и решил ее, добавив логическую переменную в проверку цикла.

Код до ->

for (local = 0; local < heightOfDiv; local = local + 200) { // Line under Error
          tileInfo = appender.append(tileInfo).append(local).toString();
          while (true) {
            try {
              tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
              incr++;
            } catch (Exception e) {
              incr = 1;
              tileInfo = appender.append(tileInfo).append("/n").toString();
            }
          }

Чтобы решить эту проблему, я просто добавил логическую переменную и установил ее в false в блоке catch. Проверь это

for (local = 0; local < heightOfDiv; local = local + 200) {
          tileInfo = appender.append(tileInfo).append(local).toString();
          boolean terminationStatus = true;
          while (terminationStatus) {
            try {
              tileInfo = appender.append(tileInfo).append(getTheTextOfTheElement(getTheXpathOfTile(incr))).toString();
              incr++;
            } catch (Exception e) {
              incr = 1;
              tileInfo = appender.append(tileInfo).append("/n").toString();
              terminationStatus = false;
            }
          }

Вот как я решил эту проблему. Надеюсь, это поможет. :)

Answer 8

Рекурсивная функция завершается в случае выполнения условия.

Примеры:

• Результат функции 0 или 1
• Достигнуто максимальное количество звонков
• Результат меньше / больше входного значения

В вашем случае условие ([x0,y0] == [xN,yN]) OR ([x1,y1] == [xN,yN]) OR ([xN-1,yN-1] == [xN,yN])

0, 1, ...N - индексы пар

Таким образом, вам нужен контейнер (вектор, список, карта) для хранения всех предыдущих пар и сравнения их с текущей парой.

Answer 9

ИМХО Только петли могут входить в бесконечный цикл.

Если у вашего метода слишком много уровней рекурсии, JVM выдаст ошибку StackOverflowError. Вы можете перехватить эту ошибку с помощью блока try / catch и делать все, что вы планируете делать при возникновении этого условия.

Answer 10

Похоже, вы работаете с 2D-массивом. Если у вас есть лишний бит в значениях массива, вы можете использовать его как флаг. Проверьте это и завершите рекурсию, если флаг был установлен. Затем установите его, прежде чем продолжить.

Если у вас нет лишних слов в значениях, вы всегда можете вместо этого сделать массив объектов.