Мемоизация рекурсивных выражений

#javascript

В книге Девида Фленегана в главе 8.8.4 Мемоизация есть пример кода и комментарий,
на самом комментарии хотел бы остановиться ибо я не понял что автор имел ввиду.
Для начала я вставлю код чтобы была понятна суть:

// Воз­вра­ща­ет ме­мои­зо­ван­ную вер­сию функ­ции f. Ра­бо­та­ет, толь­ко ес­ли
все воз­мож­ные
// ар­гу­мен­ты f име­ют от­ли­чаю­щие­ся стро­ко­вые пред­став­ле­ния.
function memoize(f) {
 var cache = {}; // Кэш зна­че­ний со­хра­ня­ет­ся в за­мы­ка­нии.
 return function() {
 // Соз­дать стро­ко­вую вер­сию мас­си­ва arguments для ис­поль­зо­ва­ния
 // в ка­че­ст­ве клю­ча кэ­ша.
 var key = arguments.length + Array.prototype.join.call(arguments,",");
 if (key in cache) return cache[key];
 else return cache[key] = f.apply(this, arguments);
 };
}
// Воз­вра­ща­ет наи­боль­ший об­щий де­ли­тель двух це­лых чи­сел, ис­поль­зуя
// ал­го­ритм Эвк­ли­да: http://en.wikipedia.org/wiki/Euclidean_algorithm
function gcd(a,b) { // Про­вер­ка ти­пов a и b опу­ще­на
 var t; // Вре­мен­ная пе­ре­мен­ная для об­ме­на
 if (a < b) t=b, b=a, a=t; // Убе­дить­ся, что a >= b
 while(b != 0) t=b, b = a%b, a=t; // Это ал­го­ритм Эвк­ли­да по­ис­ка НОД
 return a;
}
var gcdmemo = memoize(gcd);
gcdmemo(85, 187) // => 17
// Об­ра­ти­те вни­ма­ние, что при ме­мои­за­ции ре­кур­сив­ных функ­ций же­ла­тель­но,
// что­бы ре­кур­сия вы­пол­ня­лась в ме­мои­зо­ван­ной вер­сии, а не в ори­ги­на­ле.
var factorial = memoize(function(n) {
 return (n <= 1) ? 1 : n * factorial(n-1);
 });
factorial(5) // => 120. Так­же по­мес­тит в кэш фак­то­риа­лы для чи­сел 4, 3, 2 и 1.


А теперь не понятный мне комментарий:


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


Что значит выполнение рекурсии в мемоизованной версии? И чем отличается от оригинала?

Возможный вариант понимания:

1. Функция выполняется внутри функции (мемоизованный вариант):


Каждая итерация сохраняется в объекте

2. Функция выполняется внутри функции («не мемоизованный вариант»):


Сохраняется последний результат вызова

P.S Пишите что думаете по данному поводу.
    

Ответы

Ответ 1

В исходном тексте написано более понятно.


  


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

var factorial = memoize(function(n) {
  return (n <= 1) ? 1 : n * factorial(n-1);
});

factorial(5); // => 120.
factorial(4); // посчитается мгновенно так как в кеше уже есть факториал для 4
factorial(6); // посчитается в одну операцию умножения 
              // так как в кеше уже есть факториал для 5
factorial(100); // считаться будет почти полностью
factorial(99);  // посчитается мгновенно - результат есть в кеше