In article <7suufc$cu0$1@nnrp1.deja.com>, rado42 <rado42@my-deja.com>
writes
>
>Hi all,
>
>Recently I had a problem which (I thought) could be solved
>using a function template. The essence is:
>
>template <size_t SIZE>
>int getIt()
>{
>std::cout << SIZE << std::endl;
>if (SIZE)
>   return getIt <SIZE-1>();
>else
>   return 0;
>}
>

I think the problem is that the compiler has no way to know when to
stop.  You know that
getIt<0>() does not need to instantiate getIt<-1>() but that requires
the compiler to look ahead.

Try specialising the function for 0 (it has the added advantage that you
throw away those if statements.

>This code compiled ok (msvc60), but this call:
>
>getIt<1>();
>
>caused infinite recusrion at run time. I expected that
>getIt<1>() and getIt(0) would be instantiated, but tracing the
>code proved that 'getIt<SIZE-1>()' actually called getIt<SIZE>().
>
>I tried another approach, using class template instead:
>
>template <size_t SIZE>
>class X
>{
>public:
>int operator()()
>   {
>   if (SIZE)
>      return X <SIZE-1>()();
>   else
>      return 0;
>   }
>};
>
>X<1>()();
>
>This one even wouldn't compile (casuing compiler stack overflow).
>
>I haven't tried it with other compilers.
>
>My question is: are recusrive templates legal, or is it yet
>another m$ bug?
>
>--
>rado
>http://members.tripod.com/~radosoft
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
>
>
>[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
>[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
>[              --- Please see the FAQ before posting. ---               ]
>[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]
>

Francis Glassborow      Journal Editor, Association of C & C++ Users
64 Southfield Rd
Oxford OX4 1PA          +44(0)1865 246490
All opinions are mine and do not represent those of any organisation
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

rado42 wrote:
>
> Hi all,
>
> Recently I had a problem which (I thought) could be solved
> using a function template. The essence is:
>
> template <size_t SIZE>
> int getIt()
> {
> std::cout << SIZE << std::endl;
> if (SIZE)
>    return getIt <SIZE-1>();
> else
>    return 0;
> }
>
> This code compiled ok (msvc60), but this call:
>
> getIt<1>();
>
> caused infinite recusrion at run time. I expected that
> getIt<1>() and getIt(0) would be instantiated, but tracing the
> code proved that 'getIt<SIZE-1>()' actually called getIt<SIZE>().

...
> My question is: are recusrive templates legal, or is it yet
> another m$ bug?

Recursive templates are legal, but you've got to terminate the
recursion. You do this by providing specializations for the terminating
value, in this case for getIt<0>. Even though getIt<0> has a clearly
droppable branch, nothing requires that it actually be dropped, merely
that it shouldn't be used, and apparantly MSVC++ doesn't drop it. In
general, if()'s on template non-type parameters are better implemented
through specialization.

Also, each implementation has it's own upper limit on the depth of
template recursion. The standard recommends that it be  7 or 14, I can't
remember which, but doesn't require that it even be non-negative. What
this means is that for recursive templates, you should provide
specializations every (7 or 14) steps along the recursion path.

Now, as to whether you have a m$ bug, that's a different issue - I've no
idea why it wouldn't evaluate the <SIZE-1>.
---
[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

Hi all,

Recently I had a problem which (I thought) could be solved
using a function template. The essence is:

template <size_t SIZE>
int getIt()
{
std::cout << SIZE << std::endl;
if (SIZE)
   return getIt <SIZE-1>();
else
   return 0;
}

This code compiled ok (msvc60), but this call:

getIt<1>();

caused infinite recusrion at run time. I expected that
getIt<1>() and getIt(0) would be instantiated, but tracing the
code proved that 'getIt<SIZE-1>()' actually called getIt<SIZE>().

I tried another approach, using class template instead:

template <size_t SIZE>
class X
{
public:
int operator()()
   {
   if (SIZE)
      return X <SIZE-1>()();
   else
      return 0;
   }
};

X<1>()();

This one even wouldn't compile (casuing compiler stack overflow).

I haven't tried it with other compilers.

My question is: are recusrive templates legal, or is it yet
another m$ bug?

--
rado
http://members.tripod.com/~radosoft


Sent via Deja.com http://www.deja.com/
Before you buy.


[ comp.std.c++ is moderated.  To submit articles, try just posting with ]
[ your news-reader.  If that fails, use mailto:std-c++@ncar.ucar.edu    ]
[              --- Please see the FAQ before posting. ---               ]
[ FAQ: http://reality.sgi.com/austern_mti/std-c++/faq.html              ]

I seem to recall that there was a thread with a subject like this
recently, but I didn't follow it at the time.  I looked in the ARM and
FAQ, but didn't see anything about this.

Is there any (good) reason why I should not be able to use a
template-class-name as a template-arg (using the labels from p. 343 of
the ARM)?  If not, are there any compilers that support this?  From
what I've been able to tell, cfront-based compilers call this a syntax
error.

For example:

 template<class T> myPointer // e. g. a reference counting pointer
 {
     ...
 };

 template<class T> myVector // e. g. a bounds checked vector
 {
     ...
 };

 typedef myPointer<myVector<int>> myIntVectorPointer; // syntax error??

myVector<int> is clearly a template-class-name which I believe means
that it's a type-name which in turn means that it's a valid
template-arg.

--
Rick Busdiecker <rfb@lehman.com> and <rfb@cmu.edu>
  Lehman Brothers     ``A classic is something that everybody wants to
  3 World Financial Center    have read and nobody wants to read.
  New York, NY 10285-0900        - Samuel Langhorne Clemens (a.k.a. Mark Twain)
  (212) 640-9419

In article <RFB.93Nov23113425@cfdev1426.lehman.com>,
Rick Busdiecker <rfb@lehman.com> wrote:
>I seem to recall that there was a thread with a subject like this
>recently, but I didn't follow it at the time.  I looked in the ARM and
>FAQ, but didn't see anything about this.

There's mention of your error in FAQ #116: "What's the syntax /
semantics for a `class template'?".  It should probably be made more
prominent.

> template<class T> myPointer { // e. g. a reference counting pointer
> /*...*/
> };
> template<class T> myVector { // e. g. a bounds checked vector
> /*...*/
> };
> typedef myPointer<myVector<int>> myIntVectorPointer; // syntax error??
>
>myVector<int> is clearly a template-class-name which I believe means
>that it's a type-name which in turn means that it's a valid
>template-arg.

That's correct, but you need to insert a space in ">>".  Otherwise it
is interpreted as the right shift operator (token parsing happens in a
very early translation phase):

 typedef myPointer<myVector<int> > myIntVectorPointer;

It's possible to create a compiler which understands your original
version.  I'm not sure why the language definition isn't changed to
allow it.  It would probably require some ugliness in the definition
and the change and burden on compiler writers is probably not
considered necessary.

Btw, I usually seen the term "recursive templates" or
"mutually-dependent" templates to mean code like:

 template<unsigned long N> struct Pow2;
 struct Pow2<0> {
     static unsigned long eval() { return 1; }
 };
 template<unsigned long N> struct Pow2 {
     static unsigned long eval() { return 2*Pow2<N-1>::eval(); }
 };

or
 template<class Letter> class Envelope : public Letter {
 /*...*/
 };
 template<class T> class List {
 public:
    void f(Envelope<List<T> >&);
 };

or
 template<class Container> class Iter {
    Container* container;
    Container::IterState state;
 };
 template<class T> class List {
 public:
    typedef Iter<List<T> > MyIter;
    typedef int IterState;
 };


I've found cfront and gnu to have major problems with code like this.
Borland does a pretty good job with it.  Watcom does even better.  In
fairness, ANSI/ISO and still mulling over this subject so I'm not
positive all this code will be legal Standard C++ (but I hope it is).

Jamshid Afshar
jamshid@ses.com

In article <RFB.93Nov23113425@cfdev1426.lehman.com> rfb@lehman.com (Rick Busdiecker) writes:

   . . .

   Is there any (good) reason why I should not be able to use a
   template-class-name as a template-arg

   . . .

    typedef myPointer<myVector<int>> myIntVectorPointer; // syntax error??

Several people pointed out that the line above is indeed a syntax
error.  It needs a space inserted and then everything works just fine:

    typedef myPointer<myVector<int> > myIntVectorPointer; // syntax error??
       ^
       |

--
Rick Busdiecker <rfb@lehman.com> and <rfb@cmu.edu>
  Lehman Brothers     ``A classic is something that everybody wants to
  3 World Financial Center    have read and nobody wants to read.
  New York, NY 10285-0900        - Samuel Langhorne Clemens (a.k.a. Mark Twain)
  (212) 640-9419

In article <CGyn9C.7KM@ses.com> jamshid@ses.com (Jamshid Afshar) writes:
>In article <RFB.93Nov23113425@cfdev1426.lehman.com>,
>Rick Busdiecker <rfb@lehman.com> wrote:
>>I seem to recall that there was a thread with a subject like this
>>recently, but I didn't follow it at the time.  I looked in the ARM and
>>FAQ, but didn't see anything about this.
>
>There's mention of your error in FAQ #116: "What's the syntax /
>semantics for a `class template'?".  It should probably be made more
>prominent.
>
>> template<class T> myPointer { // e. g. a reference counting pointer
>> /*...*/
>> };
>> template<class T> myVector { // e. g. a bounds checked vector
>> /*...*/
>> };
>> typedef myPointer<myVector<int>> myIntVectorPointer; // syntax error??
>>
>>myVector<int> is clearly a template-class-name which I believe means
>>that it's a type-name which in turn means that it's a valid
>>template-arg.
>
>That's correct, but you need to insert a space in ">>".  Otherwise it
>is interpreted as the right shift operator (token parsing happens in a
>very early translation phase):
>
> typedef myPointer<myVector<int> > myIntVectorPointer;
>
>It's possible to create a compiler which understands your original
>version.  I'm not sure why the language definition isn't changed to
>allow it.  It would probably require some ugliness in the definition
>and the change and burden on compiler writers is probably not
>considered necessary.

The issue of the (unfortunate) choice of `<' and `>' as the delimiters for
lists of template formal arguments was debated at length quite some time
ago within X3J16.  At that time, it was pointed out (by the syntax working
group) that the use of some alternative set of delimiters (e.g. parens,
square brackets, curly braces) could easily eliminate the current problems
relating to the use of `<' and `>' as template formal argument list delimiters.

I do not recall exactly what the objection was to using some more sensible
set of delimiters.  Doing so would have made the language less error prone
(for end-users), but apparently that fact was given less weight than that
accorded to some other considerations (none of which I can remember).

--

-- Ronald F. Guilmette, Sunnyvale, California -------------------------------
------ domain address: rfg@netcom.com ---------------------------------------
------ uucp address: ...!uunet!netcom.com!rfg -------------------------------

pjl@cs.uiuc.edu (Paul Lucas) writes:
: In <5225@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
:
: >pl2440@meibm31.cen.uiuc.edu (Paul Jay Lucas) writes:
: >: In <1992Nov16.220526.21566@borland.com> pete@borland.com (Pete Becker) writes:
: >:
: >: >In article <83733@ut-emx.uucp> jamshid@emx.cc.utexas.edu (Jamshid Afshar) writes:
: >: >>Has ANSI decided anything about the expansion of a recursive template
: >: >>definition?
: >:
: >: *****> Has anyone got a *real* justification for this?  This is a very
: >:  obfuscated way of writing factorial.
:
: >You should be able to base binary trees on unary trees (which are degenerate
: >trees more commonly known as linked lists), trinary trees could be
: >based on binary trees, and n-ary trees could be based on (n-1)-ary trees.
:
: *****> I'm not convinced.  List, or unary trees as you call them, serve
:  different purposes than do binary trees.  A List class would
:  have "list-type" operations on it;

Agreed.  A full-blown List class is more than a unary tree.  Still,
the operations on unary trees map nicely to the operations on lists:
Child(0) --> next(), parent() --> prev(), top() --> first(),
leftMostBottom() --> last(),
in case you really want to integrate the List and Tree concepts.

: a BinaryTree class could have
:  LeftChild() and RightChild() functions and wouldn't have
:  list-type operations.

In this context, a binary tree is instantiated as GenericTree<2>,
and has Child(0) and Child(1) functions instead.  Deriving class
BinaryTree from GenericTree<2> is trivial. BinaryTree::LeftChild()
and RightChild() just forwards the request to GenericTree<2>::Child().
I would think it is difficult to make GenericTree<2> as efficient
as a hand-crafted class BinaryTree though (but that is not my point).

:
:  Anyway, a Tree<class T,int noOfChildren> class can be
:  implemented nicely without recursive templates; I don't see that
:  the recursive definition buys you anything.

A bit stricter type checking.  Typing errors are caught at compile-time
rather than at run-time.  I sure don't need this for may everyday work,
but who knows what tomorrows programmers might need?

You lose performance though; at least I think that the recursive version
is difficult to get as fast at child lookup.

: >N-dimension matrixes should be possible to base on N-1-dimension matrixes,
: >with 1-dimensional matrixes (arrays) as the recursion-stopper.
:
: *****> What's a 5x3 matrix based on?  4x2, 3x1, 2x(oops!).

No, no.

You don't parameterize on the _size_ of the matrixes, you parameterize
on the number of dimensions.  5x3, 4x2 and 3x1 are all of type
GenericMatrix<2>.  Parameterizing (non-recursively) on the size in each
dimension may be an a useful exercise, if you do a lot of matrix work
(I don't).

Whether these recursive template definitions are really useful in
practical work is an open issue, but as someone pointed out, current
template compilers (some) support it, and why not?  It does give added
power to detect type errors at compile-time, rather than at run-time.

--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

>>>>> On Tue, 17 Nov 1992 22:46:23 GMT, pjl@cs.uiuc.edu (Paul Lucas) said:

>>N-dimension matrixes should be possible to base on N-1-dimension matrixes,
>>with 1-dimensional matrixes (arrays) as the recursion-stopper.

> *****> What's a 5x3 matrix based on?  4x2, 3x1, 2x(oops!).

Dimension. Not size.  NxNxN is based on NxN is based on N was
specified as the recursion-stopper.

--
     Alan Braggins, alanb@sdl.mdcbbs.com, abraggins@cix.compulink.co.uk
Shape Data - A division of EDS-Scicon Limited.   Cambridge, UK +44-223-316673
   "Any technology distinguishable from magic is insufficiently advanced."
 "My employer does not necessarily share my views - but I'm working on it."

In <ALANB.92Nov18175213@catalina.sdl.mdcbbs.com> alanb@sdl.mdcbbs.com (Alan Braggins) writes:

>>>>>> On Tue, 17 Nov 1992 22:46:23 GMT, pjl@cs.uiuc.edu (Paul Lucas) said:

>>>N-dimension matrixes should be possible to base on N-1-dimension matrixes,
>>>with 1-dimensional matrixes (arrays) as the recursion-stopper.

>> *****> What's a 5x3 matrix based on?  4x2, 3x1, 2x(oops!).

>Dimension. Not size.  NxNxN is based on NxN is based on N was
>specified as the recursion-stopper.

 A misread on my part.  I'm still not convinced that recursive
 templates are anything but a curiosity.
--
 - Paul J. Lucas    University of Illinois
   AT&T Bell Laboratories  at Urbana-Champaign
   Naperville, IL   pjl@cs.uiuc.edu

In article <5225@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:
|N-dimension matrixes should be possible to base on N-1-dimension matrixes,
|with 1-dimensional matrixes (arrays) as the recursion-stopper.
|
|The details are left as an exercise for the reader (:-).

Similarly there's the old example of recursively implementing a 2^n times-
the-range LongInt class based on a 2^(n-1) times-the-range implementation.

Has ANSI decided anything about the expansion of a recursive template
definition?  Consider the following class template:

 template<unsigned N>
 class A {
    int d[N];
 public:
    A<N-1> operator--() const
       { return A<N-1>(); }
    A<N+1> operator++() const
       { return A<N+1>(); }
    int& operator[](unsigned i)
       { return d[i]; }
 };

I agree
 A<0> a0;
should be an error since it results in a 0 length array, but what about
 A<1> a1;
if operator--() is never called on it?  Actually, will the effects of
even compiling code like this be defined, or could a compiler give an
"out of memory" error or crash (btw, BC++ 3.1 gives an error)?  Would
recursion-stopping specializations for A<1> and, say, A<8> make a
difference.  If so would they have to be in any particular order?

 class A<1> {
 public:
    int d[1];
 public:
    A<2> operator++() const
       { return A<2>(); }
    int& operator[](unsigned i)
       { return d[i]; }
 };

 class A<8> {
    int d[8];
 public:
    A<7> operator--() const
       { return A<7>(); }
    int& operator[](unsigned i)
       { return d[i]; }
 };

I'm hoping ANSI will allow recursive templates.  This would require
that compilers not expand a template function or member function
unless it is actually called.  I'm worried, though, that there are
situations where this is difficult or even impossible.  Has anyone
thought this through?

Thanks, Jamshid Afshar
jamshid@emx.utexas.edu

In article <83733@ut-emx.uucp> jamshid@emx.cc.utexas.edu (Jamshid Afshar) writes:
>Has ANSI decided anything about the expansion of a recursive template
>definition?

 template <unsigned n> class Factorial
 {
 public:
  unsigned eval() { return n*Factorial<n-1>.eval(); }
 };

 class Factorial<0>
 {
 public:
  unsigned eval() { return 1; }
 };

 #include <iostream.h>

 int main()
 {
 Factorial<6> f6;
 cout << f6.eval() << endl;
 return 0;
 }

 That's from memory, so I may have some of the details wrong, but it
worked in BC 3.0, and from discussions I've had the same sort of thing works
with cfront.
 -- Pete

In <1992Nov16.220526.21566@borland.com> pete@borland.com (Pete Becker) writes:

>In article <83733@ut-emx.uucp> jamshid@emx.cc.utexas.edu (Jamshid Afshar) writes:
>>Has ANSI decided anything about the expansion of a recursive template
>>definition?

> template <unsigned n> class Factorial
> {
> public:
>  unsigned eval() { return n*Factorial<n-1>.eval(); }
> };

> class Factorial<0>
> {
> public:
>  unsigned eval() { return 1; }
> };

> #include <iostream.h>

> int main()
> {
> Factorial<6> f6;
> cout << f6.eval() << endl;
> return 0;
> }

*****> Has anyone got a *real* justification for this?  This is a very
 obfuscated way of writing factorial.
--
 - Paul J. Lucas    University of Illinois
   AT&T Bell Laboratories  at Urbana-Champaign
   Naperville, IL   pjl@cs.uiuc.edu

Jamshid Afshar jamshid@emx.utexas.edu writes:

 > This would require
 > that compilers not expand a template function or member function
 > unless it is actually called.

This was discussed briefly in the ANSI/ISO committee and there seemed to
be consensus that a template member function should not be generated unless
it was used. This is therefore the most likely outcome as a more precise
specification is worked out, but it is not the only opinion that has ever
been voiced on this matter.

In article <1992Nov16.220526.21566@borland.com> pete@borland.com (Pete Becker) writes:
>In article <83733@ut-emx.uucp> jamshid@emx.cc.utexas.edu (Jamshid Afshar) writes:
>>Has ANSI decided anything about the expansion of a recursive template
>>definition?
>
Interesting...I tried running the following example with gcc 2.3.1...
> template <unsigned n> class Factorial
> {
> public:
>  unsigned eval() { return n*Factorial<n-1>.eval(); }
                                           ^^^^^^^^^^^^^^^^^^^^^
                                           what?? there's no instance here!
I used:
                static unsigned eval() { return n*(Factorial<n-1>::eval()); }
> };
>
> class Factorial<0>
> {
> public:
>  unsigned eval() { return 1; }
again, I used
                static unsigned eval() { return 1; }
> };
>
> #include <iostream.h>
>
> int main()
> {
> Factorial<6> f6;
> cout << f6.eval() << endl;
I used
        cout << (Factorial<6>::eval()) << endl;
> return 0;
> }
>
> That's from memory, so I may have some of the details wrong, but it
>worked in BC 3.0, and from discussions I've had the same sort of thing works
>with cfront.
Well, it seems that it would make more sense to have no instantations of the
class at all...
> -- Pete
Interesting that it actually works with gcc 2.3.1...impressive...

Come to think of it, there shouldn't be any reason why recursive templates
shouldn't work...anybody have an argument against it?  (besides it being a
vehicle for more obsfucated code :-))

Curiously, gcc 2.3.1 gives me a warning about shadowing member 'eval' with
member function... I guess I should use virtuals, eh?

Well, more thoughts on this later...




--
-----
Sean Chen.  hhc@athena.mit.edu
"Nunc in scutella iaceo,/et volitare nequeo,/dentes fredentes video./Miser!"
  Olim lacus colueram, _Carmina Burana_

In article <Bxu3J4.F93@news.cso.uiuc.edu> pl2440@meibm31.cen.uiuc.edu (Paul Jay Lucas) writes:
>
>*****> Has anyone got a *real* justification for this?  This is a very
> obfuscated way of writing factorial.

 Has anyone got a *real* justification for recursive functions?  They
just provide a very obfuscated way of writing factorial().
 The point of my original posting was simply that there is no work to
be done to specify how such things work, because they already work in exactly
the way you'd expect.  Whether there are useful things that can be done with
such constructs is left as an exercise for the reader...
 -- Pete

pl2440@meibm31.cen.uiuc.edu (Paul Jay Lucas) writes:
: In <1992Nov16.220526.21566@borland.com> pete@borland.com (Pete Becker) writes:
:
: >In article <83733@ut-emx.uucp> jamshid@emx.cc.utexas.edu (Jamshid Afshar) writes:
: >>Has ANSI decided anything about the expansion of a recursive template
: >>definition?
:
: > template <unsigned n> class Factorial
: > {
: > public:
: >  unsigned eval() { return n*Factorial<n-1>.eval(); }
: > };
:
: > class Factorial<0>
: > {
: > public:
: >  unsigned eval() { return 1; }
: > };
:
: > #include <iostream.h>
:
: > int main()
: > {
: > Factorial<6> f6;
: > cout << f6.eval() << endl;
: > return 0;
: > }
:
: *****> Has anyone got a *real* justification for this?  This is a very
:  obfuscated way of writing factorial.

You should be able to base binary trees on unary trees (which are degenerate
trees more commonly known as linked lists), trinary trees could be
based on binary trees, and n-ary trees could be based on (n-1)-ary trees.

N-dimension matrixes should be possible to base on N-1-dimension matrixes,
with 1-dimensional matrixes (arrays) as the recursion-stopper.

The details are left as an exercise for the reader (:-).
--
--------------------------------------------------------------------------
| Johan Bengtsson, Telia Research AB, Aurorum 6, S-951 75 Lulea, Sweden  |
| Johan.Bengtsson@lulea.trab.se; Voice:(+46)92075471; Fax:(+46)92075490  |
--------------------------------------------------------------------------

In <5225@holden.lulea.trab.se> jbn@lulea.trab.se (Johan Bengtsson) writes:

>pl2440@meibm31.cen.uiuc.edu (Paul Jay Lucas) writes:
>: In <1992Nov16.220526.21566@borland.com> pete@borland.com (Pete Becker) writes:
>:
>: >In article <83733@ut-emx.uucp> jamshid@emx.cc.utexas.edu (Jamshid Afshar) writes:
>: >>Has ANSI decided anything about the expansion of a recursive template
>: >>definition?
>:
>: > template <unsigned n> class Factorial
>: > {
>: > public:
>: >  unsigned eval() { return n*Factorial<n-1>.eval(); }
>: > };
>:
>: > class Factorial<0>
>: > {
>: > public:
>: >  unsigned eval() { return 1; }
>: > };
>:
>: > #include <iostream.h>
>:
>: > int main()
>: > {
>: > Factorial<6> f6;
>: > cout << f6.eval() << endl;
>: > return 0;
>: > }
>:
>: *****> Has anyone got a *real* justification for this?  This is a very
>:  obfuscated way of writing factorial.

>You should be able to base binary trees on unary trees (which are degenerate
>trees more commonly known as linked lists), trinary trees could be
>based on binary trees, and n-ary trees could be based on (n-1)-ary trees.

*****> I'm not convinced.  List, or unary trees as you call them, serve
 different purposes than do binary trees.  A List class would
 have "list-type" operations on it; a BinaryTree class could have
 LeftChild() and RightChild() functions and wouldn't have
 list-type operations.

 Anyway, a Tree<class T,int noOfChildren> class can be
 implemented nicely without recursive templates; I don't see that
 the recursive definition buys you anything.

>N-dimension matrixes should be possible to base on N-1-dimension matrixes,
>with 1-dimensional matrixes (arrays) as the recursion-stopper.

*****> What's a 5x3 matrix based on?  4x2, 3x1, 2x(oops!).
--
 - Paul J. Lucas    University of Illinois
   AT&T Bell Laboratories  at Urbana-Champaign
   Naperville, IL   pjl@cs.uiuc.edu

In <1992Nov17.172152.14255@borland.com> pete@borland.com (Pete Becker) writes:

>In article <Bxu3J4.F93@news.cso.uiuc.edu> pl2440@meibm31.cen.uiuc.edu (Paul Jay Lucas) writes:
>>
>>*****> Has anyone got a *real* justification for this?  This is a very
>> obfuscated way of writing factorial.

> Has anyone got a *real* justification for recursive functions?  They
>just provide a very obfuscated way of writing factorial().

*****> Some algorithms are naturally recursive; most (other) people
 would agree that factorial is naturally expressed recursively.

> The point of my original posting was simply that there is no work to
>be done to specify how such things work, because they already work in exactly
>the way you'd expect.

*****> Huh?  I don't understand that paragraph.

>Whether there are useful things that can be done with
>such constructs is left as an exercise for the reader...

*****> No, the point is whether it should be mandated that recursive
 templates be part of the standard or not.  If they're trivial to
 implement in compilers, then go ahead; if not, then I think
 justification is in order.
--
 - Paul J. Lucas    University of Illinois
   AT&T Bell Laboratories  at Urbana-Champaign
   Naperville, IL   pjl@cs.uiuc.edu