Рекурсия или повторение?

Исключение нулевого указателя генерируется, когда приложение пытается использовать null в случае, когда требуется объект. К ним относятся:

  1. Вызов метода экземпляра объекта null.
  2. Доступ или изменение поля объекта null.
  3. Принимая длину null, как если бы это был массив.
  4. Доступ или изменение слотов null, как если бы это был массив.
  5. Бросок null как будто это было значение Throwable.

Приложения должны бросать экземпляры этого класса, чтобы указать на другие незаконные использования объекта null.

Ссылка: http://docs.oracle.com/javase/8/docs/api/java/lang/NullPointerException.html

215
задан OmG 14 May 2019 в 15:46
поделиться

13 ответов

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

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

177
ответ дан OmG 23 November 2019 в 04:19
поделиться

Насколько я знаю, Perl не оптимизирует рекурсивные вызовы хвоста, но можно фальсифицировать его.

sub f{
  my($l,$r) = @_;

  if( $l >= $r ){
    return $l;
  } else {

    # return f( $l+1, $r );

    @_ = ( $l+1, $r );
    goto &f;

  }
}

, Когда сначала названный им выделит место на стеке. Тогда это изменит свои аргументы и перезапустит подпрограмму, не добавляя ничего больше к стеку. Это поэтому притворится, что никогда не называло сам, изменяя его в итеративный процесс.

Примечание, что нет никакой" my @_;" или" local @_;", если Вы, это больше не будет работать.

0
ответ дан Brad Gilbert 23 November 2019 в 04:19
поделиться

Mike корректен. Хвостовая рекурсия не оптимизирована компилятором Java или JVM. Вы будете всегда получать переполнение стека с чем-то вроде этого:

int count(int i) {
  return i >= 100000000 ? i : count(i+1);
}
1
ответ дан noah 23 November 2019 в 04:19
поделиться

это зависит от "глубины рекурсии". это зависит от того, насколько вызов функции наверху будет влиять на общее время выполнения.

, Например, вычисляя классический факториал рекурсивным способом очень неэффективно из-за: - риск переполнения данных - риск переполнения стека - вызов функции наверху занимает 80% времени выполнения

при разработке алгоритма минимакса для анализа положения в игре шахмат, которые проанализируют последующие перемещения N, может быть реализован в рекурсии по "аналитической глубине" (поскольку я делаю ^_^)

2
ответ дан ugasoft 23 November 2019 в 04:19
поделиться

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

2
ответ дан metadave 23 November 2019 в 04:19
поделиться

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

4
ответ дан Warrior 23 November 2019 в 04:19
поделиться

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

4
ответ дан MovEaxEsp 23 November 2019 в 04:19
поделиться

Я полагаю, что хвостовая рекурсия в Java в настоящее время не оптимизируется. Детали опрыснуты повсюду этот обсуждение LtU и связанных ссылок. Это может быть функцией в следующей версии 7, но по-видимому это представляет определенные трудности, когда объединено с Контролем Стека, так как определенные кадры отсутствовали бы. Контроль стека использовался для реализации их мелкомодульной модели обеспечения безопасности начиная с Java 2.

http://lambda-the-ultimate.org/node/1333

6
ответ дан 23 November 2019 в 04:19
поделиться

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

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

7
ответ дан entzik 23 November 2019 в 04:19
поделиться

Это зависит от языка. В Java необходимо использовать циклы. Функциональные языки оптимизируют рекурсию.

4
ответ дан Alex Riley 23 November 2019 в 04:19
поделиться

Как правило, можно было бы ожидать, что потеря производительности ляжет в другом направлении. Рекурсивные вызовы могут привести к конструкции дополнительных стековых фреймов; штраф за это варьируется. Кроме того, на некоторых языках как Python (более правильно, в некоторых реализациях некоторых языков...), можно столкнуться с пределами стека скорее легко для задач, которые Вы могли бы определить рекурсивно, такие как нахождение максимального значения в древовидной структуре данных. В этих случаях Вы действительно хотите придерживаться циклов.

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

Кроме "граничных" случаев (высокопроизводительное вычисление, очень большая глубина рекурсии, и т.д.), предпочтительно принять подход, который наиболее ясно выражает Ваше намерение, хорошо разработан и удобен в сопровождении. Оптимизируйте только после идентификации потребности.

11
ответ дан zweiterlinde 23 November 2019 в 04:19
поделиться

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

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

16
ответ дан Doron Yaacoby 23 November 2019 в 04:19
поделиться

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

318
ответ дан Meng-Yuan Huang 23 November 2019 в 04:19
поделиться
Другие вопросы по тегам:

Похожие вопросы: