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

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

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

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

В случае, если Вы интересуетесь нерекурсивной версией Башен 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;

var memoizer = function (fund, memo) {
    var shell = function (arg) {
        if (typeof memo[arg] !== 'number') {
            memo[arg] = fund(shell, arg);
        }
        return memo[arg];
    };
    return shell;
};

var fibonacci = memoizer(function (recur, n) { return recur(n - 1) + recur(n - 2); }, [0, 1]);

используйте обоих!

В обычном случае Вы сталкиваетесь с двумя критериями, которые помогают с Вашим решением:

• Время выполнения
• Удобочитаемость

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

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

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

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

Это зависит от того, для чего Вы идете. динамическое программирование (memoization) почти всегда быстрее. Часто МНОГО. (т.е., кубический к в квадрате, или экспоненциальный к poly), но по моему опыту, рекурсию легче считать и отладить.

С другой стороны много людей избегает рекурсии как чумы, таким образом, им не легко читать...

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

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

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

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

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

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

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

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

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

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

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

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

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

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