Why this template recursion won't compile?

Question

I am attempting to print out the numbers from 1 to 1000 in C++ without any control statements or conditionals. I have found this question + answer on SO, but I cannot compile it on Linux with gcc 4.8. Any ideas why this is not working?

This is the code I'm trying:

#include <iostream>
template<int N>
struct NumberGeneration{
  static void out(std::ostream& os)
  {
    NumberGeneration<N-1>::out(os);
    os << N << std::endl;
  }
};
template<>
struct NumberGeneration<1>{
  static void out(std::ostream& os)
  {
    os << 1 << std::endl;
  }
};
int main(){
   NumberGeneration<1000>::out(std::cout);
}

The error I get is this:

main2.cpp:9:34: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘struct NumberGeneration<100>’
     NumberGeneration<N-1>::out(os);
                                  ^
main2.cpp:9:34:   recursively required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 999; std::ostream = std::basic_ostream<char>]’
main2.cpp:9:34:   required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 1000; std::ostream = std::basic_ostream<char>]’
main2.cpp:21:28:   required from here

main2.cpp:9:34: error: incomplete type ‘NumberGeneration<100>’ used in nested name specifier
main2.cpp:10:8: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char) [with _CharT = char; _Traits = std::char_traits<char>]’
     os << N << std::endl;
        ^
main2.cpp:9:34:   recursively required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 999; std::ostream = std::basic_ostream<char>]’
main2.cpp:9:34:   required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 1000; std::ostream = std::basic_ostream<char>]’
main2.cpp:21:28:   required from here

main2.cpp:10:8: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char) [with _Traits = std::char_traits<char>]’
main2.cpp:9:34:   recursively required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 999; std::ostream = std::basic_ostream<char>]’
main2.cpp:9:34:   required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 1000; std::ostream = std::basic_ostream<char>]’
main2.cpp:21:28:   required from here

main2.cpp:10:8: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char) [with _Traits = std::char_traits<char>]’
main2.cpp:9:34:   recursively required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 999; std::ostream = std::basic_ostream<char>]’
main2.cpp:9:34:   required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 1000; std::ostream = std::basic_ostream<char>]’
main2.cpp:21:28:   required from here

main2.cpp:10:8: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char) [with _Traits = std::char_traits<char>]’
main2.cpp:9:34:   recursively required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 999; std::ostream = std::basic_ostream<char>]’
main2.cpp:9:34:   required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 1000; std::ostream = std::basic_ostream<char>]’
main2.cpp:21:28:   required from here

main2.cpp:10:13: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, _CharT) [with _CharT = char; _Traits = std::char_traits<char>]’
     os << N << std::endl;
             ^
main2.cpp:9:34:   recursively required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 999; std::ostream = std::basic_ostream<char>]’
main2.cpp:9:34:   required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 1000; std::ostream = std::basic_ostream<char>]’
main2.cpp:21:28:   required from here

main2.cpp:10:13: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const _CharT*) [with _CharT = char; _Traits = std::char_traits<char>]’
main2.cpp:9:34:   recursively required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 999; std::ostream = std::basic_ostream<char>]’
main2.cpp:9:34:   required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 1000; std::ostream = std::basic_ostream<char>]’
main2.cpp:21:28:   required from here

main2.cpp:10:13: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) substituting ‘template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::endl(std::basic_ostream<_CharT, _Traits>&) [with _CharT = char; _Traits = std::char_traits<char>]’
main2.cpp:9:34:   recursively required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 999; std::ostream = std::basic_ostream<char>]’
main2.cpp:9:34:   required from ‘static void NumberGeneration<N>::out(std::ostream&) [with int N = 1000; std::ostream = std::basic_ostream<char>]’
main2.cpp:21:28:   required from here

main2.cpp:10:13: error: no match for ‘operator<<’ (operand types are ‘std::basic_ostream<char>’ and ‘<unresolved overloaded function type>’)
main2.cpp:10:13: note: candidates are:
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:108:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_CharT, _Traits>::__ostream_type& (*)(std::basic_ostream<_CharT, _Traits>::__ostream_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(__ostream_type& (*__pf)(__ostream_type&))
       ^
/usr/include/c++/4.8/ostream:108:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘std::basic_ostream<char>::__ostream_type& (*)(std::basic_ostream<char>::__ostream_type&) {aka std::basic_ostream<char>& (*)(std::basic_ostream<char>&)}’
/usr/include/c++/4.8/ostream:117:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_CharT, _Traits>::__ios_type& (*)(std::basic_ostream<_CharT, _Traits>::__ios_type&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>; std::basic_ostream<_CharT, _Traits>::__ios_type = std::basic_ios<char>]
       operator<<(__ios_type& (*__pf)(__ios_type&))
       ^
/usr/include/c++/4.8/ostream:117:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘std::basic_ostream<char>::__ios_type& (*)(std::basic_ostream<char>::__ios_type&) {aka std::basic_ios<char>& (*)(std::basic_ios<char>&)}’
/usr/include/c++/4.8/ostream:127:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(std::ios_base& (*)(std::ios_base&)) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(ios_base& (*__pf) (ios_base&))
       ^
/usr/include/c++/4.8/ostream:127:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘std::ios_base& (*)(std::ios_base&)’
/usr/include/c++/4.8/ostream:166:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(long __n)
       ^
/usr/include/c++/4.8/ostream:166:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘long int’
/usr/include/c++/4.8/ostream:170:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(unsigned long __n)
       ^
/usr/include/c++/4.8/ostream:170:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘long unsigned int’
/usr/include/c++/4.8/ostream:174:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(bool) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(bool __n)
       ^
/usr/include/c++/4.8/ostream:174:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘bool’
In file included from /usr/include/c++/4.8/ostream:609:0,
                 from /usr/include/c++/4.8/iostream:39,
                 from main2.cpp:1:
/usr/include/c++/4.8/bits/ostream.tcc:91:5: note: std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(short int) [with _CharT = char; _Traits = std::char_traits<char>]
     basic_ostream<_CharT, _Traits>::
     ^
/usr/include/c++/4.8/bits/ostream.tcc:91:5: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘short int’
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:181:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(short unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(unsigned short __n)
       ^
/usr/include/c++/4.8/ostream:181:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘short unsigned int’
In file included from /usr/include/c++/4.8/ostream:609:0,
                 from /usr/include/c++/4.8/iostream:39,
                 from main2.cpp:1:
/usr/include/c++/4.8/bits/ostream.tcc:105:5: note: std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(int) [with _CharT = char; _Traits = std::char_traits<char>]
     basic_ostream<_CharT, _Traits>::
     ^
/usr/include/c++/4.8/bits/ostream.tcc:105:5: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘int’
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:192:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(unsigned int __n)
       ^
/usr/include/c++/4.8/ostream:192:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘unsigned int’
/usr/include/c++/4.8/ostream:201:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(long long __n)
       ^
/usr/include/c++/4.8/ostream:201:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘long long int’
/usr/include/c++/4.8/ostream:205:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long long unsigned int) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(unsigned long long __n)
       ^
/usr/include/c++/4.8/ostream:205:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘long long unsigned int’
/usr/include/c++/4.8/ostream:220:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(double __f)
       ^
/usr/include/c++/4.8/ostream:220:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘double’
/usr/include/c++/4.8/ostream:224:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(float) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(float __f)
       ^
/usr/include/c++/4.8/ostream:224:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘float’
/usr/include/c++/4.8/ostream:232:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(long double) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(long double __f)
       ^
/usr/include/c++/4.8/ostream:232:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘long double’
/usr/include/c++/4.8/ostream:245:7: note: std::basic_ostream<_CharT, _Traits>::__ostream_type& std::basic_ostream<_CharT, _Traits>::operator<<(const void*) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__ostream_type = std::basic_ostream<char>]
       operator<<(const void* __p)
       ^
/usr/include/c++/4.8/ostream:245:7: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘const void*’
In file included from /usr/include/c++/4.8/ostream:609:0,
                 from /usr/include/c++/4.8/iostream:39,
                 from main2.cpp:1:
/usr/include/c++/4.8/bits/ostream.tcc:119:5: note: std::basic_ostream<_CharT, _Traits>& std::basic_ostream<_CharT, _Traits>::operator<<(std::basic_ostream<_CharT, _Traits>::__streambuf_type*) [with _CharT = char; _Traits = std::char_traits<char>; std::basic_ostream<_CharT, _Traits>::__streambuf_type = std::basic_streambuf<char>]
     basic_ostream<_CharT, _Traits>::
     ^
/usr/include/c++/4.8/bits/ostream.tcc:119:5: note:   no known conversion for argument 1 from ‘<unresolved overloaded function type>’ to ‘std::basic_ostream<char>::__streambuf_type* {aka std::basic_streambuf<char>*}’
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:548:5: note: template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const unsigned char*)
     operator<<(basic_ostream<char, _Traits>& __out, const unsigned char* __s)
     ^
/usr/include/c++/4.8/ostream:548:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   cannot convert ‘std::endl’ (type ‘<unresolved overloaded function type>’) to type ‘const unsigned char*’
     os << N << std::endl;
             ^
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:543:5: note: template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const signed char*)
     operator<<(basic_ostream<char, _Traits>& __out, const signed char* __s)
     ^
/usr/include/c++/4.8/ostream:543:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   cannot convert ‘std::endl’ (type ‘<unresolved overloaded function type>’) to type ‘const signed char*’
     os << N << std::endl;
             ^
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:530:5: note: template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, const char*)
     operator<<(basic_ostream<char, _Traits>& __out, const char* __s)
     ^
/usr/include/c++/4.8/ostream:530:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   cannot convert ‘std::endl’ (type ‘<unresolved overloaded function type>’) to type ‘const char*’
     os << N << std::endl;
             ^
In file included from /usr/include/c++/4.8/ostream:609:0,
                 from /usr/include/c++/4.8/iostream:39,
                 from main2.cpp:1:
/usr/include/c++/4.8/bits/ostream.tcc:321:5: note: template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const char*)
     operator<<(basic_ostream<_CharT, _Traits>& __out, const char* __s)
     ^
/usr/include/c++/4.8/bits/ostream.tcc:321:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   cannot convert ‘std::endl’ (type ‘<unresolved overloaded function type>’) to type ‘const char*’
     os << N << std::endl;
             ^
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:513:5: note: template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const _CharT*)
     operator<<(basic_ostream<_CharT, _Traits>& __out, const _CharT* __s)
     ^
/usr/include/c++/4.8/ostream:513:5: note:   substitution of deduced template arguments resulted in errors seen above
/usr/include/c++/4.8/ostream:493:5: note: template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, unsigned char)
     operator<<(basic_ostream<char, _Traits>& __out, unsigned char __c)
     ^
/usr/include/c++/4.8/ostream:493:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   cannot convert ‘std::endl’ (type ‘<unresolved overloaded function type>’) to type ‘unsigned char’
     os << N << std::endl;
             ^
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:488:5: note: template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, signed char)
     operator<<(basic_ostream<char, _Traits>& __out, signed char __c)
     ^
/usr/include/c++/4.8/ostream:488:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   cannot convert ‘std::endl’ (type ‘<unresolved overloaded function type>’) to type ‘signed char’
     os << N << std::endl;
             ^
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:482:5: note: template<class _Traits> std::basic_ostream<char, _Traits>& std::operator<<(std::basic_ostream<char, _Traits>&, char)
     operator<<(basic_ostream<char, _Traits>& __out, char __c)
     ^
/usr/include/c++/4.8/ostream:482:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   cannot convert ‘std::endl’ (type ‘<unresolved overloaded function type>’) to type ‘char’
     os << N << std::endl;
             ^
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:476:5: note: template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, char)
     operator<<(basic_ostream<_CharT, _Traits>& __out, char __c)
     ^
/usr/include/c++/4.8/ostream:476:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   cannot convert ‘std::endl’ (type ‘<unresolved overloaded function type>’) to type ‘char’
     os << N << std::endl;
             ^
In file included from /usr/include/c++/4.8/iostream:39:0,
                 from main2.cpp:1:
/usr/include/c++/4.8/ostream:471:5: note: template<class _CharT, class _Traits> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, _CharT)
     operator<<(basic_ostream<_CharT, _Traits>& __out, _CharT __c)
     ^
/usr/include/c++/4.8/ostream:471:5: note:   substitution of deduced template arguments resulted in errors seen above
In file included from /usr/include/c++/4.8/string:52:0,
                 from /usr/include/c++/4.8/bits/locale_classes.h:40,
                 from /usr/include/c++/4.8/bits/ios_base.h:41,
                 from /usr/include/c++/4.8/ios:42,
                 from /usr/include/c++/4.8/ostream:38,
                 from /usr/include/c++/4.8/iostream:39,
                 from main2.cpp:1:
/usr/include/c++/4.8/bits/basic_string.h:2753:5: note: template<class _CharT, class _Traits, class _Alloc> std::basic_ostream<_CharT, _Traits>& std::operator<<(std::basic_ostream<_CharT, _Traits>&, const std::basic_string<_CharT, _Traits, _Alloc>&)
     operator<<(basic_ostream<_CharT, _Traits>& __os,
     ^
/usr/include/c++/4.8/bits/basic_string.h:2753:5: note:   template argument deduction/substitution failed:
main2.cpp:10:13: note:   couldn't deduce template parameter ‘_Alloc’
     os << N << std::endl;
             ^

And when I increase template instantiation depth I get :

$ gcc -Wall -ftemplate-depth=1100  -omain2 main2.cpp
/tmp/ccI81cmF.o: In function `main':
main2.cpp:(.text+0x5): undefined reference to `std::cout'
/tmp/ccI81cmF.o: In function `__static_initialization_and_destruction_0(int, int)':
main2.cpp:(.text+0x38): undefined reference to `std::ios_base::Init::Init()'
main2.cpp:(.text+0x47): undefined reference to `std::ios_base::Init::~Init()'
/tmp/ccI81cmF.o: In function `NumberGeneration<1>::out(std::ostream&)':
main2.cpp:(.text._ZN16NumberGenerationILi1EE3outERSo[_ZN16NumberGenerationILi1EE3outERSo]+0x19): undefined reference to `std::ostream::operator<<(int)'
main2.cpp:(.text._ZN16NumberGenerationILi1EE3outERSo[_ZN16NumberGenerationILi1EE3outERSo]+0x1e): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)'
main2.cpp:(.text._ZN16NumberGenerationILi1EE3outERSo[_ZN16NumberGenerationILi1EE3outERSo]+0x26): undefined reference to `std::ostream::operator<<(std::ostream& (*)(std::ostream&))'
/tmp/ccI81cmF.o: In function `NumberGeneration<1000>::out(std::ostream&)':
main2.cpp:(.text._ZN16NumberGenerationILi1000EE3outERSo[_ZN16NumberGenerationILi1000EE3outERSo]+0x25): undefined reference to `std::ostream::operator<<(int)'
main2.cpp:(.text._ZN16NumberGenerationILi1000EE3outERSo[_ZN16NumberGenerationILi1000EE3outERSo]+0x2a): undefined reference to `std::basic_ostream<char, std::char_traits<char> >& std::endl<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&)'
main2.cpp:(.text._ZN16NumberGenerationILi1000EE3outERSo[_ZN16NumberGenerationILi1000EE3outERSo]+0x32): undefined reference to `std::ostream::operator<<(std::ostream& (*)(std::ostream&))'

You probably have to increase your template instantiation depth limit. — David G, Aug 27 '14 at 17:29
@0x499602D2 I have updated my question with the error I get (I rushed a little bit :( ... ) — Patryk, Aug 27 '14 at 17:41
Heh, the first line of the error is "`main2.cpp:9:34: error: template instantiation depth exceeds maximum of 900 (use -ftemplate-depth= to increase the maximum) instantiating ‘struct NumberGeneration<100>’`". Seems straightforward to me. — Mooing Duck, Aug 27 '14 at 17:43
Referring to the errors you got after increasing the limit: Do you still get those errors when you remove the code all together? — David G, Aug 27 '14 at 17:43
@0x499602D2 What do you mean 'remove the code all together' ? — Patryk, Aug 27 '14 at 17:44
Nevermind. You need to use `g++` because this is C++ code. `gcc` is for C. — David G, Aug 27 '14 at 17:45
@0x499602D2 That was the issue :) I can also do: `gcc .... -lstdc++` — Patryk, Aug 27 '14 at 17:47

Jarod42 · Accepted Answer · 2014-08-29T17:44:48.687

As state in the comment, you reach the template depth limit, and use the wrong compiler: so use a C++ compiler as g++

And then you may pass this argument to increase depth limit -depth=1000

or you may instantiate intermediate template as

template struct NumberGeneration<500>;

or rewrite your template to not use a depth linear with N something like the following

// index_sequence and make_index_sequence available in C++14, but not in C++11
template <std::size_t...> struct index_sequence {};

namespace detail
{
template <typename, typename> struct concat;

template <std::size_t... Is1, std::size_t... Is2>
struct concat<index_sequence<Is1...>, index_sequence<Is2...>> :
    index_sequence<Is1..., (sizeof...(Is1) + Is2)...>
{
    using type = index_sequence<Is1..., (sizeof...(Is1) + Is2)...>;
};

}

template <std::size_t N>
struct make_index_sequence :
    detail::concat<typename make_index_sequence<N / 2>::type,
    typename make_index_sequence<N - N / 2>::type>::type
{
    using type = typename
        detail::concat<typename make_index_sequence<N / 2>::type,
                       typename make_index_sequence<N - N / 2>::type>::type;
};

template <>
struct make_index_sequence<1u> : index_sequence<0u> {
    using type = index_sequence<0u>;
};

template <>
struct make_index_sequence<0u> : index_sequence<> {
    using type = index_sequence<>;
};

And then with variadic template:

template<int N>
struct NumberGeneration{
  static void out(std::ostream& os)
  {
    out(make_index_sequence<N>(), os);
  }
private:
    template<std::size_t ...Is>
    static void out(index_sequence<Is...>, std::ostream& os)
    {
        std::initializer_list<int>{ ((os << (1 + Is) << std::endl), void(), 0)...};
    }
};

Live example

A cute trick: `template struct index_sequence { using type = index_sequence; };` (new `using` in it) at the top, and you remove the code duplication in `make_index_sequence` and elsewhere, including the typo in `make_index_sequence<0>`, `concat`, etc. — Yakk - Adam Nevraumont, Aug 29 '14 at 17:40

Yakk - Adam Nevraumont · Answer 2 · 2014-08-29T14:52:05.273

The big problem is that it is really bad C++. It has a 1000 deep template instantiation depth, and the C++11 standard only advises 900. What more, there is little to no need for something that deep to do such a simple task.

Most compilers have template instantiation depth modification flags that make it larger. That is, however, a patch over the problem. The right way to fix that code is to either not write it, or decrease the depth.

#include <iostream>
template<int Max, unsigned Count=Max>
struct NumberGeneration{
  void operator()(std::ostream& os) const
  {
    NumberGeneration<Max, (Count+1)/2>()(os);
    NumberGeneration<Max-(Count+1)/2, (Count)/2>()(os);
  }
};
template<int Max>
struct NumberGeneration<Max, 1>{
  void operator()(std::ostream& os) const
  {
    os << Max << std::endl;
  }
};
// not required:
template<int Max>
struct NumberGeneration<Max, 0>{
  void operator()(std::ostream& os) const
  {}
};
int main(){
   NumberGeneration<1000>()(std::cout);
}

This now has a recursive template instantiation depth of about 10 instead of 1000, and is nearly as simple as the original version. I simply replaced single recursion with divide-and-conquer.

In C++14, efficient lists of integers via std::integral_sequence exist, and allow the above kind of thing even easier.

I also made NumberGeneration<X> into a stateless invokable type instead of having a static void out() method.

Can you elaborate a little on `stateless invokable type`? What is it exactly and why did you use it? — Patryk, Aug 29 '14 at 15:16
@Patryk a `class` with an `operator()` is invokable. It is stateless if there is no state -- no data stored in the `class`. `std::less` is an example of such a class. — Yakk - Adam Nevraumont, Aug 29 '14 at 15:33

Why this template recursion won't compile?

2 Answers2