Должен ли я использовать рекурсию или памятку для алгоритма?

Question

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

Answer 1

Они не являются взаимоисключающими. Вы можете использовать их обоих.

Лично я сначала построю базовую рекурсивную функцию, а затем добавлю памятку в качестве шага оптимизации.

Answer 2

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

Например, чтобы вычислить F (4), мне нужно знать F (3) и F (2), поэтому я вычисляю F (3), вычисляя F (2) и F (1), и так далее. Если я использовал рекурсию, я просто вычислял F (2) и большинство других F (n) дважды. Если я использую памятку, я могу просто посмотреть значение.

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

Answer 3

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

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

Answer 4

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

Answer 5

Не уверен, что могу сказать, не зная проблемы. Часто вы хотите использовать памятку с рекурсией. Тем не менее, запоминание, вероятно, будет значительно быстрее, чем рекурсия, если вы на самом деле можете использовать его в качестве альтернативного решения. У них обоих есть проблемы с производительностью, но они различаются в зависимости от характера проблемы / размера ввода.

Answer 6

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

Answer 7

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

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

Answer 8

Если ваша проблема рекурсивная, какой у вас есть выбор, кроме как рекурсировать?

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

Answer 9

Это зависит от того, что вы собираетесь. динамическое программирование (запоминание) почти всегда быстрее. Часто ЛОТОМ. (то есть кубический в квадрат или экспоненциальный в поли), но по моему опыту, рекурсию легче читать и отлаживать.

Опять же, многие люди избегают рекурсии, как чума, поэтому им нелегко читать ...

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

Я не уверен, что мне помогло, но вот, пожалуйста. Как и во многих случаях выбора алгоритма, YMMV.

Answer 10

Я не согласен с утверждением Томалака о том, что с рекурсивной проблемой у вас нет иного выбора, кроме как рекурсировать?

Лучший пример - вышеупомянутая серия Фибоначчи. На моем компьютере рекурсивная версия F (45) (F для Фибоначчи) занимает 15 секунд для 2269806339 сложений, итерационная версия занимает 43 сложения и выполняется за несколько микросекунд.

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

Если вам интересна нерекурсивная версия Towers of Hamoi, вот исходный код Delphi:

procedure TForm1.TowersOfHanoi(Ndisks: Word);
var
  I: LongWord;
begin
  for I := 1 to (1 shl Ndisks) do
    Memo1.Lines.Add(Format('%4d: move from pole %d to pole %d',
      [I, (I and (I - 1)) mod 3, (I or (I - 1) + 1) mod 3]));
  Memo1.Lines.Add('done')
end;