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 <initializer_list>#include <vector>template<typename T>types_t;template<typename Derived>class RecursionArray{    public:        using value_type = typename types_t<Derived>::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<value_type> 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() <= n)            {                // Compute and add the values to the vector                _values.emplace_back(function(size()));            }            return _values[n];        }        /**         * @brief Returns the number of computed elements         * @return Number of computed elements in the vector         */        constexpr auto size() const            -> std::size_t        {            return _values.size();        }        /**         * @brief User-defined function whose results are stored         *         * This is the core of the class. A RecursionArray is just         * meant to store the results of function are reuse them         * instead of computing them another time. That is why a         * RecursionArray function can only accept unsigned integers         * as parameters.         *         * @param n Index of the element         * @return See user-defined function         */        auto function(std::size_t n)            -> value_type        {            return static_cast<Derived&>(*this).function(n);        }    private:        // Member data        std::vector<value_type> _values;  /**< Computed results of function */};It is a base class that uses static polymorphism. Here is an example of a user-defined derived class:class MemoizedFibonacci;/* * We need to tell to the RecursionArray which * kind of data it has to store. */template<>struct types_t<MemoizedFibonacci>{    using value_type = unsigned int;};/** * @brief Fibonacci function class * * A way to implement the Fibonacci function and to force it * to store its results in order to gain some speed with the * following calls to the function. */struct MemoizedFibonacci:    RecursionArray<MemoizedFibonacci>{    using super = RecursionArray<MemoizedFibonacci>;    using typename super::value_type;    /**     * @brief Default constructor     *     * To use a Fibonacci function, we need to know at least     * its first two values (for 0 and 1) which are 0 and 1.     * We pass those values to the RecursionArray constructor.     */    MemoizedFibonacci():        super( { 0, 1 } )    {}    /**     * @brief Fibonacci function     *     * Fibonacci function considering that the first values are     * already known. Also, self will call function and     * memoize its results.     *     * @param n Wanted Fibonacci number     * @return nth Fibonacci number     */    auto function(std::size_t n)        -> value_type    {        return self(n-1) + self(n-2);    }};And finally, here is how we can use the user-defined class:int main(){    MemoizedFibonacci fibonacci;    // The Fibonacci numbers up to the nth are computed    // and stored into the RecursionArray    std::cout << fibonacci(12) << std::endl;    // 144    std::cout << fibonacci(0) << std::endl;     // 0    std::cout << fibonacci(1) << std::endl;     // 1    std::cout << fibonacci(25) << std::endl;    // 75025}The problem is that I want to keep the user side simple, but also to avoid virtual (hence the static polymorphism). There are three main functions in the class:* function: the recursive formula.* operator(): so that the end user can use the final instances as functions.* self: helper function (same as operator()) so that the recursive formula is easier to write.It would be great if the user did not have to specialize types_t and could just give MemoizedFibonacci, but I can't seem to find a way to do so. Do you whether there would be some way to ease the functor writer work?
Optimize RecursionArray interface
c++;c++11;recursion;cache;fibonacci sequence