Failure to create C++ arrays recursively

Question

I want to test a recursion method and the following code has a compilation error. I've double checked the subscripts variables, and they should be correct. I really couldn't figure it out, can somebody help me?

#include <iostream>
#include <array>
using namespace std;

template <typename T, size_t Size>
void fn(array<T, Size>& data) { 
   const size_t begin{0};
   const size_t end{Size-1};
   const size_t leftUpper{(begin+end)/2};
   const size_t rightLower{leftUpper+1};

   if (data.size() > 1 ) { 
      array<T, end+1-rightLower> right; 
      cout << "Right: " << end+1-rightLower << endl;   
      fn(right);
   }
}

int main() {
   array<int, 5> test;
   fn(test);
} 

The compilation error is:

$ g++ -std=c++14 GuessNumber.cpp -o test
In file included from GuessNumber.cpp:2:0:
/usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/array: In instantiation of ‘struct std::array<int, 2305843009213693952>’:
GuessNumber.cpp:15:9:   recursively required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 2]’
GuessNumber.cpp:15:9:   required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 5]’
GuessNumber.cpp:21:11:   required from here
/usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/array:94:12: error: size of type ‘std::array<int, 2305843009213693952>’ is too large (‘9223372036854775808’ bytes)
     struct array
            ^~~~~

Answer 1

First of all, let us understand where the problem comes from.

The error you get

/usr/lib/gcc/x86_64-pc-cygwin/7.3.0/include/c++/array: In instantiation of ‘struct std::array<int, 2305843009213693952>’:
GuessNumber.cpp:15:9:   recursively required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 2]’
GuessNumber.cpp:15:9:   required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 5]’

tells you that you first instantiate fn with Size=5 (because you call it in the main), and this recursively instantiates fn with Size=2. Unfortunately the compiler does not show the full recursion, otherwise you would see that the recursion does not end here. If you use in the program an array of size 2

array<int, 2> test;

you will see an additional level of recursion, in the error message:

GuessNumber.cpp:15:9:   recursively required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 1]’
GuessNumber.cpp:15:9:   required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 2]’
GuessNumber.cpp:21:11:   required from here

which again, tells you that the instantiation of fn with Size=2 triggers the intantation of fn with Size=1. But the recursion does not end here. Try with

array<int, 1> test;

and you will finally see what is happpening:

/usr/include/c++/10.1.0/array: In instantiation of ‘struct std::__array_traits<int, 9223372036854775808>’:
/usr/include/c++/10.1.0/array:110:56:   required from ‘struct std::array<int, 9223372036854775808>’
GuessNumber.cpp:13:33:   required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 0]’
GuessNumber.cpp:15:9:   required from ‘void fn(std::array<_Tp, _Nm>&) [with T = int; long unsigned int Size = 1]’
GuessNumber.cpp:21:11:   required from here

When Size=1, the compiler fully generates fn, including the code in the braces if (data.size() > 1). Even if this condition is always false, still the code is parsed and compiled. This means that, inside the never-executed-code, you instantiate fn with Size=0. But then, you have an overflow in the variable end, which attains a large value. Then the code after if instantiates an std::array with the exceedingly large size.

To fix this, you need to stop the compiler from generating code when Size=0. This can be done in several ways.

With c++17 you have a very convenient if constexpr. If the condition of if constexpr is not true, the code is not instatiated at all, ending then the template recursion. So you can substitute

if (data.size() > 1 ) { 

with

if constexpr (Size > 1 ) { 

And compile with std=c++17. Notice that I changed the condition to Size > 1 because the data variable is not constexpr, hence you cannot use it at compile time.

If you do not have c++17, you can use SFINAE instead.

#include <iostream>
#include <array>
#include <type_traits>

using namespace std;

template <typename T, size_t Size>
typename std::enable_if<(Size == 0)>::type fn(array<T, Size>& data) { }

template <typename T, size_t Size>
typename std::enable_if<(Size > 0)>::type fn(array<T, Size>& data) { 
   const size_t begin{0};
   const size_t end{Size-1}; // 1
   const size_t leftUpper{(begin+end)/2}; // 0
   const size_t rightLower{leftUpper+1}; //  1

   if (data.size() > 1 ) { 
     array<T, end+1-rightLower> right; // 1
      cout << "Right: " << end+1-rightLower << endl;   
      fn(right);
   }
}

int main() {
   array<int, 5> test;
   fn(test);
}

The two approaches are perfectly equivalent, see here.

Answer 2

Try this:

#include <iostream>
#include <array>
using namespace std;

// the function contains its body just because looks like 
// you want to implement some other logic there
template <typename T>
void fn(array<T, 2ul>& data) {
      const size_t Size = 2;
      const size_t begin{0};
      const size_t end{Size-1};
      const size_t leftUpper{(begin+end)/2};
      const size_t rightLower{leftUpper+1};
      array<T, end+1-rightLower> right; 
      cout << "Right: " << end+1-rightLower << endl;   
}

template <typename T>
void fn(array<T, 1ul>& data) {
}

template <typename T>
void fn(array<T, 1ul>& data) {
      const size_t Size = 1;
      const size_t begin{0};
      const size_t end{Size-1};
      const size_t leftUpper{(begin+end)/2};
      const size_t rightLower{leftUpper+1};
      array<T, end+1-rightLower> right; 
      cout << "Right: " << end+1-rightLower << endl;   
}

template <typename T, size_t Size>
void fn(array<T, Size>& data) { 
   const size_t begin{0};
   const size_t end{Size-1};
   const size_t leftUpper{(begin+end)/2};
   const size_t rightLower{leftUpper+1};

   if (data.size() > 1 ) { 
      array<T, end+1-rightLower> right; 
      cout << "Right: " << end+1-rightLower << endl;   
      fn(right);
   }
}

int main() {
   array<int, 5> test;
   fn(test);
} 

You code is not compiled conditionally. ifs do not work like you expect when you do template magic. One more example is here