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

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

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

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

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 } 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 boolean skipRecursivePaths = false; private callAgain(){ if(callAgain){ if(getOutCompletely){ skipRecursivePaths = true; } if(skipRecursivePaths){ return; } } 

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

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

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

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

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

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

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

 if(stop[0]) return; 
  • Рекурсивная функция не возвращает указанное значение
  • Как заменить циклы с альтернативным функциональным программированием без оптимизации хвостового вызова?
  • понимание базовой рекурсии
  • Рекурсия хвоста в C ++
  • Я получил «приложение схемы не процедуру» в последнем рекурсивном вызове функции
  • Почему функции в Ocaml / F # не рекурсивны по умолчанию?
  • Рекурсия или итерация?
  • Какие рекурсивные функции нельзя переписать с помощью петель?
  • Что такое нерекурсивное решение для последовательности, подобной Фибоначчи, в Java?
  • Почему максимальная глубина рекурсии я могу достичь недетерминированной?
  • Это бесконечная recursion UB?
  • Давайте будем гением компьютера.