Убегая из рекурсии в Java

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

1. Магическое возвращаемое значение (как описано одним из Томов)
2. Вызвать исключение (как упомянул Тагги)

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

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

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

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

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

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

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

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

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

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

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

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

Вы спрашиваете об определении рекурсии.

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

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

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
}

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

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