How to avoid infinite recursion in C++ class templates

Question

I have a matrix class with the size determined by template parameters.

template <unsigned cRows, unsigned cCols>
class Matrix {
    ...
};

My program uses matrices of a few sizes, typically 2x2, 3x3, and 4x4. By setting the matrix size with template parameters rather than run-time parameters allows the compiler to do a lot of inlining and optimization.

But now I need a member function that returns a new matrix that has one fewer row and one fewer column.

Matrix<cRows - 1, cCols - 1> Reduced(unsigned row, unsigned col) const { ... }

The idea is that that it will return a matrix with the specified row and column deleted. In practice, this will only ever be called with a matrix that has at least three rows and three columns, returning a 2x2 at the smallest.

The compiler doesn't see the lower bound, so it gets stuck in an infinite recursion trying to instantiate the templates with ever decreasing sizes. I tried putting two clues in the function itself that these smaller sizes cannot occur:

Matrix<cRows - 1, cCols - 1> Reduced(unsigned row, unsigned col) const {
    static_assert(cRows > 1 && cCols > 1);
    if (cRows <= 1 || cCols <= 1) throw std::domain_error();
    Matrix<cRows - 1, cCols - 1> r;
    // ... initialize r ...
    return r;
}

Neither the static_assert nor the if-statement seems to be a strong enough clue to the compiler that a 0x0 matrix will never be generated. (Ironically, it does complain about the if-statement having a constant compile-time condition.)

Does anyone have any suggestions on how to avoid this compile-time infinite recursion?

Answer 1

You need to explicitly specify the behaviour for the case where you want the recursion to end. See this DDJ article for more details. Here is a simple example from the article:

template<int n>
class META_FACTORIAL
{
public:
  enum{
    RET = n * META_FACTORIAL<n-1>::RET
  };
};

template<>
class META_FACTORIAL<0>
{
public:
  enum{ RET = 1 };
};

Answer 2

You can specify a template specializations for small values of cRows or cCols which does not include that method.

Answer 3

You seem a bit confused about compile time and run time behaviour, and I'm a bit confused by your code, but I think what you want is a specialisation of the template for the values, 0, 0, which terminates the recursion.

If you haven't already got it, I suggest reading C++ Templates: The Complete Guide by Vandervoorde & Josuttis, which covers this sort of thing in detail.

Answer 4

You need to provide a specialization for a Matrix that has no rows or no columns.

E.g.

template<unsigned cRows>
class Matrix< cRows, 0 >
{
    Matrix<cRows - 1, 0> Reduced() { return Matrix<cRows - 1, 0>(); }
};


template<unsigned cCols>
class Matrix< 0, cCols >
{
    Matrix<0, cCols - 1> Reduced() { return Matrix<0, cCols - 1>(); }
};


template<>
class Matrix< 0, 0 >
{
    Matrix<0, 0> Reduced() { return Matrix<0, 0>(); }
};

The issue you have is that attempting to instantiate the Matrix Reduced function with a particular set of template parameters always required instantiating the Matrix template for a different set of parameters (cRows - 1, cCols -1). This recursion has to be stopped somewhere. If you are only ever dealing with square matrices, then you can get away with fewer specializations.

Also, you can could stop the recursion with a completely empty class if you are never going to use, say, a 1x1 matrix, the result of reduce on a 2x2 matrix.

template<>
class Matrix< 1, 1 > {};

Answer 5

Rather than specializing the entire class to terminate the recursion, another option might be to use boost::enable_if on the function to make it available only when the matrix size is above 2x2.