Эффективно ли Throwing Exception для принудительного выхода из рекурсии? - PullRequest
Новая
       16

Эффективно ли Throwing Exception для принудительного выхода из рекурсии?

4 голосов
/ 31 марта 2019

Ниже приведен только псевдокод. 

  function x(node){
    if(node.val == 42) 
       return true; // What if I throw an exception here ?
    val1 = node.left ? x(node.left) : false ;
    val2 = node.right ? x(node.right): false; 
    return val1 || val2 ;
 }

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

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

Это хорошая практика - просто генерировать исключение, чтобы разорвать всю цепочку.Потому что, скажем, на line 4, он нашел 42 в каком-то вложенном стеке, и все равно будет продолжать рекурсию на line 5.Если я просто сгенерирую исключение на line 3, мы сможем избежать этого ненужного вычисления.

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

1 Ответ

4 голосов
/ 31 марта 2019

Я бы не рекомендовал создавать исключения для разрыва цепочки рекурсии по нескольким причинам.

  • Эффективность . Вызов исключения, вообще говоря, намного медленнее, чем возврат из функции. В частности, когда выбрасывается исключение, среда выполнения должна заполнить исключение текущей трассировкой стека, должна посмотреть, какой обработчик вызывать, нужно выполнить поиск блоков finally или операторов try -with-resources отслеживание ссылок на объекты для целей сборки мусора и т. д. Это все еще требует обхода стека вызовов, так же, как при возврате значения в цепочку вызовов, и это почти наверняка не будет быстрее, чем при более стандартном подходе.

  • Юзабилити . Если вы генерируете исключение для прерывания рекурсивной цепочки, то всякий, кто вызывает вашу функцию, должен написать код, который реагирует на это исключение. Это означает, что вместо того, чтобы что-то наподобие написания if (myCall()) {...}, им нужно иметь отдельные ветви: одну для того, где вызов возвращает значение нормально, а другую для случая, когда он выбрасывает. Если они забудут это сделать, код во время выполнения может показаться сбойным из-за исключения, когда на самом деле он ведет себя так, как ожидалось. Хуже того, вы на самом деле инвертируете обычное использование исключений. Если ваш код выдает исключение, когда он завершается успешно и возвращает значение, когда он завершается с ошибкой , то, кто бы ни читал ваш код, вероятно, пойдет "да?" по крайней мере, один раз, прежде чем понять, что вы имели в виду.

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

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

...