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

Question

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

Answer 1

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]);

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

Answer 2

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

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

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

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

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

Answer 3

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

Answer 4

Объедините оба. Оптимизируйте рекурсивное решение, используя памятку. Вот для чего предназначены памятные записки. Для использования пространства памяти для ускорения рекурсии.