Выход из рекурсии в Java

Question

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

Answer 1

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

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

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

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

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

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

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

Answer 2

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

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

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
}

Answer 3

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

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

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

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

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

Answer 5

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

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

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

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
}

Answer 6

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

Answer 7

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

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

Answer 8

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

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

if(stop[0]) return;

Answer 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 байтов в памяти для хранения всего стека. По сути, с проверкой диапазона и ошибок перед рекурсивным методом / функцией вам не нужно прерывать работу. Однако, в зависимости от вашего алгоритма, вам может понадобиться сообщить всему стеку, что вы готовы идти. Если это так, то ответ Тома работает.

Answer 10

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

boolean skipRecursivePaths = false;
private callAgain(){

if(callAgain){
  if(getOutCompletely){

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