Add infinite template recursion example

[nicovank]

Impressive snippet: I originally forgot to pass the vector size M * N when constructing the vector (std::vector<std::uint64_t> v;, which doesn't generate a compiler diagnostic at all, would SIGSEV), and GPT reported it.

[...]

Also, in main function:

```cpp
std::vector<std::uint64_t> v(M * N);

This will allocates memory needed for the vector v. Without this, your current program is accessing out-of-bounds memory in line v[i] = i;, which also causes a runtime error.

For this example, it sometimes recommends a `constexpr if` before instantiating the subclass, sometimes suggests a base case with `M` equal to zero, both of which fix the issue. From manual observation it seems to give a "satisfactory" explanation / suggestion most of the time, maybe 80-90%.

Compiler diagnostic (Apple Clang 15.0.0):

fatal error: recursive template instantiation exceeded maximum depth of 1024 tests/c++/template-recursion.cpp:11:51: note: while substituting deduced template arguments into function template 'span' [with _Range = std::span &] Matrix(std::span underlying) : underlying(underlying) { ^ tests/c++/template-recursion.cpp:19:32: note: in instantiation of member function 'Matrix<4294966373, 10>::Matrix' requested here const auto subMatrix = Matrix<M - 1, N>(underlying.subspan(N)); ^ tests/c++/template-recursion.cpp:20:48: note: in instantiation of member function 'Matrix<4294966374, 10>::lowestRowSum' requested here return std::min(firstRowSum, subMatrix.lowestRowSum()); ^ tests/c++/template-recursion.cpp:20:48: note: in instantiation of member function 'Matrix<4294966375, 10>::lowestRowSum' requested here tests/c++/template-recursion.cpp:20:48: note: in instantiation of member function 'Matrix<4294966376, 10>::lowestRowSum' requested here tests/c++/template-recursion.cpp:20:48: note: (skipping 1015 contexts in backtrace; use -ftemplate-backtrace-limit=0 to see all) tests/c++/template-recursion.cpp:20:48: note: in instantiation of member function 'Matrix<96, 10>::lowestRowSum' requested here tests/c++/template-recursion.cpp:20:48: note: in instantiation of member function 'Matrix<97, 10>::lowestRowSum' requested here tests/c++/template-recursion.cpp:20:48: note: in instantiation of member function 'Matrix<98, 10>::lowestRowSum' requested here tests/c++/template-recursion.cpp:20:48: note: in instantiation of member function 'Matrix<99, 10>::lowestRowSum' requested here tests/c++/template-recursion.cpp:36:47: note: in instantiation of member function 'Matrix<100, 10>::lowestRowSum' requested here const auto lowestRowSum = Matrix<M, N>(v).lowestRowSum(); ^ 1 error generated.

Sample CWhy suggestion:

Your issue originates from the fact that when the Matrix<M, N> template is instantiated, it recursively creates a new Matrix<M - 1, N> object in the lowestRowSum method (at line 19). This recursion has no base case, meaning that it continues infinitely (until the compiler puts a stop to it after 1024 iterations).

For a recursive template, you have to provide a base case to terminate the recursion. Something like this:

template <std::uint32_t M, std::uint32_t N>
struct Matrix {
    // ...
    std::uint64_t lowestRowSum() const {
        const auto firstRowSum = 
            std::accumulate(underlying.begin(), std::next(underlying.begin(), N), std::uint64_t(0));

        if constexpr(M > 1) {
            const auto subMatrix = Matrix<M - 1, N>(underlying.subspan(N));
            return std::min(firstRowSum, subMatrix.lowestRowSum());
        } else {
            return firstRowSum;
        }
    }
    // ...
};

In the code above, the if statement with the constexpr keyword creates a compile-time if statement, meaning that if the condition is false, the branch is not even compiled. Effectively, the lowestRowSum method will have different implementations based on the value of M.

If M > 1, the method does its normal work of comparing the current row's sum with the submatrix's lowest row sum. If M is 1, then the method simply returns the sum of the current row, which stops the recursion.

[nicovank]

The example is a bit silly, but this is the first thing I could think of for a infinite recursive template.

[emeryberger]

LGTM. Nit: GPT produced an English syntax error?!?

This will allocates memory needed for the vector v.

[nicovank]

Didn't event notice, seems so, I copy-pasted from the output 🤷