CODEWITHSUNDEEP
c++templatesrecursionc++11
Stijn Frishert
Stijn Frishert

Reputation: 1573

Calling Templated Function Recursively (C++)

I'm writing a templated mathematical matrix class to get used to some new c++11 features, the basic declaration is as follows:

template <typename Type, int kNumRows, int kNumCols>
class Matrix { ... };

The class has a member function to return one of its minors (which is later used to calculate the determinant of NxN matrices).

Matrix<Type, kNumRows - 1, kNumCols - 1> minor(const int row, const int col) {
  static_assert(kNumRows > 2, "");
  static_assert(kNumCols > 2, "");

  ...
}

I then created a non-member function to calculate the determinant of any square matrix:

template <typename Type, int kSize>
Type determinant(const Matrix<Type, kSize, kSize>& matrix) {
  switch (kSize) {
  case 2:
    return 0; // For now unimportant
  case 3:
    // Recursively call the determinant function on a minor matrix
    return determinant(matrix.minor(0, 0));
  }
  ...
}

In main() I create a 3x3 matrix and call determinant on it. This will not compile. The compiler effectively moves to case 3, creating a minor matrix and calling determinant on it. It then steps into case 3 again, resulting in a static_assert by trying to create a 1x1 minor.

The question is simple: am I missing something here? Is calling a templated function like this recursively simply not allowed? Is this a compiler fault (I doubt it)?

For completeness' sake: I'm using Clang++.

Upvotes: 3

Views: 1974

Answers (3)

aschepler
aschepler

Reputation: 72271

Templates determine what to do at compile time, but a switch statement determines what to do at run time. The compiler generates code, or at least verifies the validity, for all switch cases, even if the correct case is "obvious" at compile time.

Instead of using switch, try overloading determinant:

template <typename Type>
Type determinant(const Matrix<Type, 1, 1>& matrix) {
    return matrix(0,0);
}

template <typename Type>
Type determinant(const Matrix<Type, 2, 2>& matrix) {
    return 0; // (incorrect math)
}

template <typename Type, int kSize>
Type determinant(const Matrix<Type, kSize, kSize>& matrix) {
    return determinant(matrix.minor(0,0)); // (incorrect math)
}

Upvotes: 3

Mankarse
Mankarse

Reputation: 40603

You need to do the switch at compile time using template specialisation:

template <typename Type, int kSize>
struct Determinate {
    Type operator()(const Matrix<Type, kSize, kSize>& matrix) const {
        // Recursively call the determinant function on a minor matrix
        return Determinate<Type, kSize-1>{}(matrix.minor(0, 0));
    }
};
template <typename Type>
struct Determinate<Type, 2> {
    Type operator()(const Matrix<Type, kSize, kSize>& matrix) const {
        return 0; // For now unimportant
    }
};
template <typename Type, int kSize>
Type determinant(const Matrix<Type, kSize, kSize>& matrix) {
    return Determinate<Type, kSize>{}(matrix);
}

Upvotes: 1

Konrad Rudolph
Konrad Rudolph

Reputation: 545588

The compiler generates all code paths, even if those are not all visited during execution (and may actually be removed in an optimisation step). As a consequence, determinant<Type, kSize - 1, kSize - 1> is always instantiated, even for kSize < 3.

You need to partially specialise your function to prevent this, you need to overload your determinant function appropriately:

template <typename Type>
Type determinant(const Matrix<Type, 2, 2>& matrix) {
  ...
}

This makes the switch statement in your function redundant, by the way.

Upvotes: 3

Related Questions