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

StackOverflow https://stackoverflow.com/questions/1030527

  •  06-07-2019
  •  | 
  •  

Вопрос

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

Редактировать:Это функция, и она будет вызываться рекурсивно с разными значениями x и y.я хочу завершить, если при рекурсивном вызове значение пары (x, y) повторяется. 

int fromPos(int [] arr, int x, int y)
Это было полезно?

Решение

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

Другие советы

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

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

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

Простым способом было бы реализовать одно из следующего:

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

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

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

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

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

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

Билли3

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

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

Если вы хотите сохранить сигнатуру вашего метода, вы можете оставить пару наборов для записи старых значений x и y. 

static Set<Integer> xs;
static Set<Integer> ys;//Initialize this!
static int n=0;//keeps the count function calls.

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

 int newX= getX(x);
 int newY= getY(y);
 n++; 
 if ((!xs.add(Integer.valueOf(newX)) && !ys.add(Integer.valueOf(newY))){

   assert(n<threshold); //threshold defined elsewhere.
   fromPos(arr,newx,newy);
 }
}

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

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

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

Примеры:

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

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

0, 1, ...N являются индексами пар

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

Сначала используйте 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;
            }
          }

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top