Запоминаемая, рекурсивная факториальная функция?

Ну, самый изящный способ, который я могу придумать, чтобы сделать это на C++, вероятно, использовать объект функции для хранения запомненных значений. Я предполагаю, что это, вероятно, немного похоже на ваш декоратор Python, хотя я никогда не делал никакого Python. Код будет выглядеть примерно так:

template <typename T, T (*calc)(T)>
class mem {
  std::map<T,T> mem_map;

public:
  T operator()(T input) {
    typename std::map<T,T>::iterator it;

    it = mem_map.find(input);
    if (it != mem_map.end()) {
      return it->second;
    } else {
      T output = calc(input);
      mem_map[input] = output;
      return output;
    }
  }
};

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

Итак, если вы определяете некоторую функцию обработки, например:

int unity(int in) { return in; }

Вы бы использовали такой код:

mem<int, unity> mem_unity;
int y;
y = mem_unity(10);

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

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

template <template <typename...> class Container, typename...> struct Memo;

template <typename R, typename... Args, template <typename...> class Container>
struct Memo<Container, R, std::tuple<Args...>>
{
  Memo(std::function<R(Args...)> f) : func(f) { }

  R operator()(Args && ...args)
  {
    const auto arg = std::make_tuple(args...);
    typename CacheContainer::const_iterator it = cache.find(arg);

    if (it == cache.cend())
    {
      it = cache.insert(typename CacheContainer::value_type(arg, func(std::forward<Args>(args)...))).first;
      std::cout << "New call, memoizing..." << std::endl;
    }
    else
    {
      std::cout << "Found it in the cache!" << std::endl;
    }

    return it->second;
  }

private:

  typedef Container<typename std::tuple<Args...>, R> CacheContainer;

  std::function<R(Args...)> func;
  CacheContainer cache;
};


template <typename R, typename... Args>
Memo<std::map, R, std::tuple<Args...>> OMapMemoize(R(&f)(Args...))
{
  return Memo<std::map, R, std::tuple<Args...>>(f);
}
template <typename R, typename... Args>
Memo<std::unordered_map, R, std::tuple<Args...>> UMapMemoize(R(&f)(Args...))
{
  return Memo<std::unordered_map, R, std::tuple<Args...>>(f);
}

Я не совсем уверен, правильно ли я понял rvalue-forwardiness, так как написал это давным-давно. В любом случае, вот тестовый пример:

int foo(double, char) { return 5; }

int main()
{
  auto f = OMapMemoize(foo);
  auto g = UMapMemoize(foo);

  int a, b;

  a = f(1.0, 'a');
  a = f(1.0, 'a');
  a = f(1.0, 'a');
  a = f(1.0, 'a');

  b = g(1.0, 'a');
  b = g(1.0, 'a');
  b = g(1.0, 'a');
  b = g(1.0, 'a');

  return a;
}

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

Мемоизация — очень хорошая идея, особенно если вы собираетесь многократно вызывать метод. Зачем выбрасывать хорошую работу?

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

Но, во что бы то ни стало, запомните любую реализацию, которую вы используете. Если вы пишете его на C++, я бы рекомендовал использовать std:map с аргументом x в качестве ключа и ln(gamma(x)) в качестве значения.

Извините, я слишком давно не писал C++ и STL. Я бы предпочел использовать хэш-карту с временем доступа для чтения O(1), чем перебирать ключи в O(n).

Мне нравится полагаться на захват лямбда, как в (использует std=c++14)

template<typename R, typename... Args>
auto memoize(std::function<R(Args...)>&& f)
{
  using F = std::function<R(Args...)>;
  std::map<std::tuple<Args...>,R> cache;
  return ([cache = std::map<std::tuple<Args...>,R>{}, 
           f = std::forward<F>(f)](Args&&... args) mutable
    {
      std::tuple<Args...> t(args...);
      if (cache.find(t) == cache.end())
        {
          R r = f(std::forward<Args...>(args)...);
          cache[t] = r;
        }
      return cache[t];
    });
}