Optimize RecursionArray interface

I created a class a while ago that I named a "Recursion Array". It is a way to create dynamically memoized sequences such as the Fibonacci sequence or the factorial numbers sequences. The concept is to create mathematic sequences defined by recursion by only providing the first values and the recursive formula; all the computed results are internally stored into a vector. That allows to create mathematic formula in a recursive way, without having to care about the access time; each result is only computed once. Here is the base class:

```
#include
#include

template
types_t;

template
class RecursionArray
{
public:

using value_type = typename types_t::value_type;

// A RecursionArray is not copyable
RecursionArray(const RecursionArray&) = delete;
RecursionArray& operator=(const RecursionArray&) = delete;

/**
* @brief Calls "function" and applies memoization
* @see value_type self(size_t n)
*/
inline auto operator()(std::size_t n)
-> value_type
{
return self(n);
}

protected:

RecursionArray() = default;

/**
* @brief Initializer-list constructor
*
* This should be the one and only way to instance a
* RecursionArray.
*
* @param vals Results of "function" for the first values
*/
RecursionArray(std::initializer_list vals):
_values(vals.begin(), vals.end())
{}

/**
* @brief Calls "function" and applies memoization
*
* @param n Index of the value to [compute, memoize and] return
* @return Value of "function" for n
*/
auto self(std::size_t n)
-> value_type
{
while (size() std::size_t
{
return _values.size();
}

/**
* @brief User-defined function whose results are stored
*
* This is the c

There's a (slight) typo in what you've posted - the forward declaration of types_t:

template
   types_t;
// ^^^^^^^^
// Should be struct types_t;

Similarly, you've forward defined class MemoizedFibonacci and then defined it as struct MemoizedFibonacci (this isn't really a problem, but clang will complain about it with warnings enabled).

It'd be nice to not have to specialise a struct with a value_type. Often, decltype can help you get around this, however, in this case, since you're using CRTP and static polymorphism, it's unfortunately not going to work. I actually agree that using another template parameter is potentially a better solution here than to force specialisation of a template.

To me, the largest shortcoming here is that this only works with functions that take a single std::size_t parameter. Perhaps this is fine for your uses (calculating mathematical sequences that depend only on 1 variable). Using variadic templates, you can lift this restriction (at the expense of imposing another). Something like the following (incomplete, but hopefully gives you the idea):

#include 
#include 

template
class RecursionArray
{

public:
    using argument_type = std::tuple;

    inline auto operator()(Args&&... args)
        -> value_type
    {
        return self(std::forward(args)...);
    }

    auto self(Args&&... args)
        -> value_type
    {
        auto tup = argument_type(args...);
        auto it = values_.find(tup);
        if(it != values_.end()) {
            return it->second;
        }
        auto p = values_.emplace(std::make_pair(std::move(tup), function(std::forward(args)...));
        return p.first->second;
    }

private:
    std::unordered_map values_;

};

This lifts the restriction that you need to have a single std::size_t parameter, at the expense of extra complexity, and the ability to easily enforce computation up to a given size. Whether the trade-off is worth it is up to you, but it is something to think about.

StackExchange Code Review Q#34022, answer score: 6