Нарушение рекурсии в java

Ответ 1

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

Что-то в этом роде.

int foo(bar){
     int to_the_next;

      if (go_recursive){
            to_the_next = foo(whisky_bar);

            if (to_the_next ==DIE) return DIE;
      }

      if (something_unexpected_happened) return DIE;

      process;//may include some other recursive calls, etc etc
}

Ответ 2

Независимо от того, что вы делаете, вам придется раскрутить стек. Это оставляет два варианта:

• Магическое возвращаемое значение (как описано одним из Toms)
• Выбросьте исключение (как упомянуто thaggie)

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

Как оказалось, сегодня я провел оценку библиотеки zxing из кода google. На самом деле они используют исключения для множества управляющих структур. Мое первое впечатление, когда я это увидел, было ужасом. Они буквально вызывали методы десятки тысяч раз с разными параметрами, пока метод не генерирует исключение.

Это, безусловно, выглядело как проблема с производительностью, поэтому я внесла некоторые изменения, чтобы изменить ситуацию до использования возвращаемого значения magic. И знаешь, что? При работе в отладчике код был на 40% быстрее. Но когда я переключился на не-отладки, код был менее чем на 1% быстрее.

Я все еще не сумасшедший о решении использовать исключения для управления потоком в этом случае (я имею в виду, что исключения все время бросаются). Но это, конечно, не стоит моего времени для повторного внедрения, учитывая почти неизмеримую разницу в производительности.

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

Ответ 3

Если один поток выполняет рекурсию, вы можете создать исключение. Бит уродливый, хотя - вид использования исключения как goto.

boolean myPublicWrapperMethod(...) {
    try {
        return myPrivateRecursiveFunction(...);
    } catch (MySpecificException e) {
        return true;
    } 
} 

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

Ответ 4

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

public void outer() {
  try {
    int i = recurse(0);
  } catch (OuchException ouch) {
    // handle the exception here
  }
}

private int recurse(int i) throws OuchException {

    // for tree-like structures
    if (thisIsALeaf) {
       return i;
    }

    // the violation test
    if (itHurts)
       throw new OuchException("That really hurts");

    // we also can encapsulate other exceptions
    try {
       someMethod();
    } catch (Exception oops) {
       throw new OuchException(oops);
    }

    // recurse
    return recurse(i++);
}

Конечно, это нарушает первоначальное требование вернуть "истину" при аборте. Но я предпочитаю чистое разделение возвращаемых значений и уведомление об аномальном поведении.

Ответ 5

Вы можете сделать что-то подобное, сохранив переменную, которая отслеживает, должны ли рекурсии разбиваться или нет. К сожалению, вам придется проверять каждую рекурсию, но вы можете это сделать.

Ответ 6

То, что вы задаете, - это определение рекурсии.

В какой-то момент все рекурсивные пути должны сломаться. В противном случае это будет бесконечная рекурсия и произойдет исключение.

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

BinarySearch(A[0..N-1], value, low, high) {
       if (high < low)
           return -1 // not found
       mid = low + ((high - low) / 2)  // Note: not (low + high) / 2 !!
       if (A[mid] > value)
           return BinarySearch(A, value, low, mid-1)
       else if (A[mid] < value)
           return BinarySearch(A, value, mid+1, high)
       else
           return mid // found
}

Ответ 7

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

boolean skipRecursivePaths = false;
private callAgain(){

if(callAgain){
  if(getOutCompletely){

    skipRecursivePaths = true;
    }
    if(skipRecursivePaths){
    return;
    }
}

Ответ 8

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

public abstract class Tree {

    protected abstract boolean headIsViolation();

    protected abstract boolean isLeaf();

    public Tree getLeft();

    public Tree getRight();

    // Recursive
    public boolean checkViolation() {
        if(this.isLeaf()) {
            return this.headIsViolation();
        }

        // If needed, you could pass some sort of 'calculation state'
        // object through the recursive calls and evaluate the violation
        // through that object if the current node is insufficient
        if(this.headIsViolation()) {
            // Terminate the recursion
            return true;
        }

        // Fortunately, Java short-circuits ||
        // So if the left child is in violation, the right child will
        // not even be checked
        return this.getLeft().checkViolation() || this.getRight().checkViolation();
    }
}

Ответ 9

Лучший способ выйти из рекурсивного цикла при возникновении ошибки - это выбросить исключение во время выполнения.

throw new RuntimeException("Help!  Somebody debug me!  I'm crashing!");

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

getMemoryInfo.availMem().

Скажем, вы используете рекурсию для поиска n!. Ваша функция выглядит примерно так:

`public long fact(int n)
{
long val = 1;
for (int i  = 1, i<=n,i++)
{
return val*=fact(i);

} 

return val;   }

Перед запуском убедитесь, что у вас есть (количество байтов в длинном, 8 в Java) * n байтов в памяти для хранения всего стека. В принципе, при проверке диапазона и ошибок перед рекурсивным методом/функцией вам не нужно выходить из строя. Тем не менее, в зависимости от вашего алгоритма вам может потребоваться сигнал для всего стека, который вам подходит. Если это дело, ответ Том работает.

Ответ 10

Возможно, вы хотите избежать рекурсии и заменить ее на стек. Это дает вам возможность вырваться из операции, имея возможность делать что-то похожее на рекурсивную операцию. На самом деле вы просто эмулируете рекурсию самостоятельно.

Я нашел здесь приятное объяснение: http://haacked.com/archive/2007/03/04/Replacing_Recursion_With_a_Stack.aspx/

Ответ 11

лучше иметь булевский массив

таким образом не существует глобального состояния

if(stop[0]) return;