c++templatesrecursionc++20

C++ template function recursive


I have a function which calculates the determinant of a matrix. My matrix class looks like this:

template <int Col, int Row, typename T>
class Matrix;

I have implemented three specific functions for Mat<1, 1, T>, Mat<2, 2, T> and Mat<3, 3, T>:

template <typename T>
float Determinant(const Matrix<1, 1, T>& mat);

template <typename T>
float Determinant(const Matrix<2, 2, T>& mat);

template <typename T>
float Determinant(const Matrix<3, 3, T>& mat);

And now I want to have a function which calculates the determinant of matrices with dimensions higher than 3x3. I have tried to implement it like this:

template <int Dim, typename T>
float Determinant(const Matrix<Dim, Dim, T>& mat)
{
  float result = 0;
  for (int i = 0; i < Dim; ++i)
  {
    // This function returns a minor matrix of `mat`
    Matrix<Dim - 1, Dim - 1, T> minor = mat.GetMinorMatrix(i, 0);
    result += (i & 1 ? -1 : 1) * mat(i, 0) * Determinant(minor); 
  }
}

// I try to use the function
Matrix<1, 1, float> mat { 1.0f };
Determinant(mat); // Error occurs here

But somehow my compiler keeps crashing when I try to build that code. And my IDE reports this error: In template: recursive template instantiation exceeded maximum depth of 1024. The error disappears when I delete the function template <int Dim, typename T> float Determinant(const Matrix<Dim, Dim, T>& mat). Why does that error occur, and how can I fix it?


Solution

  • Imagine you instantiate Determinant with Dim = 0. Your compiler will try to instantiate Determinant<-1>, which will then again instantiate Determinant<-2>, and so on. At some point you will reach the maximum 1024. A minimal reproducible example could look like:

    template <int I>
    void foo() {
      foo<I - 1>();
    }
    
    int main() {
      foo<5>();
    }
    

    You can fix this is in different ways. The more modern approach would check for the final recursive call:

    template <int I>
    void foo() {
      if constexpr (I > 0) {
        foo<I - 1>();
      } else {
        // however you want to deal with I = 0
      }
    }
    

    Or by using template pattern matching:

    template <int I>
    void foo() {
      foo<I - 1>();
    }
    
    template <>
    void foo<0>() {
       // however you want to deal with I = 0
    }