Как обнаружить бесконечный цикл в рекурсивном вызове?
-
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;
}
}
Вот как я решил эту проблему. Надеюсь, это поможет. :) Р>