How best to build a recursive class?

[K. Frank]

Hello Group!

I desire a recursive class. Is something like the following
a good way to go?

struct RecursiveClass {
RecursiveClass (unsigned n) : n_(n), rc_((n_) ? new RecursiveClass(n-1) : nullptr) {}
unsigned n_;
std::unique_ptr<RecursiveClass> rc_;
unsigned val() { return (n_) ? rc_->val() + n_ : 0; }
};

This was about the best I could think of, but the initialization
of rc_ looks a bit cumbersome.

(Just to make the example a little less vacuous, I made
the class return "triangle numbers" via the member function
val().)

(By the way, is this a correct and sensible use of unique_ptr?)

Note, n is to be determined at run time, not compile time, so
I did not pursue a template approach, such as:

template<unsigned N> struct RecursiveClass {
RecursiveClass<N-1> rc_;
unsigned val() { return rc_.val() + N; }
};

template<> struct RecursiveClass<0> {
unsigned val() { return 0; }
};

Am I right that the template-class approach cannot be
made to work with run-time n (N in the template example)?


Thanks for any ideas.


K. Frank

[Chris Vine]

The classic example of compile time recursion is std::tuple, which you
might find instructive to have a look at. tuples are normally
implemented using recursive inheritance, something like:

template <class Head, class... Tail>
class Tuple<Head, Tail...>: private Tuple<Tail...> {
Head elt;
public:
...
};

with a specialization:

template <> struct Tuple<> { ... };

which ends recursion. I think most people go through the business of
writing their own tuple implementation at some point in their lives for
pedagogical purposes (and to learn how variadic templates work).

This is of course doing different things from your RecursiveClass.
A tuple keeps values via this recursive inheritance which can be
accessed individually by a get function such as std::get(), which would
traverse the inheritance graph. Yours provides an accessor which sums
all the values.

You are right that at compile time the size of the tuple and the types
for which it is instantiated must be known. It is part of the
tuple's type.

As regards your non-templated RecursiveClass, your use of
std::unique_ptr looks OK. If your compiler supports C++17, as an
alternative you could try std::optional, which I have never used. If
this implementation is a toy for fun, then it looks OK but in practice
to keep a collection of unsigned ints of a size determined at run time I
would use std::vector, which would be much more flexible because it
would not restrict you to summing the elements - std::accumulate can
fold over the container to do whatever you want. std::forward_list
would be a more exact container replacement for your implementation, but
be much less efficient for keeping unsigned ints.

Chris

[Chris Vine]

On Sat, 18 Feb 2017 10:51:27 +0000
Chris Vine <chris@cvine--nospam--.freeserve.co.uk> wrote:
[snip]

> As regards your non-templated RecursiveClass, your use of
> std::unique_ptr looks OK. If your compiler supports C++17, as an
> alternative you could try std::optional, which I have never used. If
> this implementation is a toy for fun, then it looks OK but in practice
> to keep a collection of unsigned ints of a size determined at run
> time I would use std::vector, which would be much more flexible
> because it would not restrict you to summing the elements -
> std::accumulate can fold over the container to do whatever you want.
> std::forward_list would be a more exact container replacement for
> your implementation, but be much less efficient for keeping unsigned
> ints.

By the way, it occurs to me that if you are interested in other
approaches to your problem, you might want to look into cons cells,
which lisps use to construct singly-linked lists. A cons cell is a
pair, and these can be strung together to produce a list (the second
element of the pair, called the 'cdr', being itself a cons cell). Your
RecursiveClass is basically a cons cell which can only be used to
construct a singly-linked list (it cannot be used as a pair only).

You can reproduce this in C++ using std::pair.

[K. Frank]

Hi Chris!

On Saturday, February 18, 2017 at 5:51:41 AM UTC-5, Chris Vine wrote:
> On Fri, 17 Feb 2017 17:41:19 -0800 (PST)
> "K. Frank" <> wrote:
> > Hello Group!
> >
> > I desire a recursive class. Is something like the following
> > a good way to go?
> >
> > struct RecursiveClass {
> > RecursiveClass (unsigned n) : n_(n), rc_((n_) ? new
> > RecursiveClass(n-1) : nullptr) {} unsigned n_;
> > std::unique_ptr<RecursiveClass> rc_;
> > unsigned val() { return (n_) ? rc_->val() + n_ : 0; }
> > };
> >
> > This was about the best I could think of, but the initialization
> > of rc_ looks a bit cumbersome.

> > ...

> > (By the way, is this a correct and sensible use of unique_ptr?)

> > ...
> ...

> As regards your non-templated RecursiveClass, your use of
> std::unique_ptr looks OK. If your compiler supports C++17, as an
> alternative you could try std::optional, which I have never used.

Could you illustrate what you have in mind for std::optional
with some sample code? I'm trying to see how I would make it
work.

I can't (I believe -- please correct me if I'm wrong.) have

std::optional<RecursiveClass> orc_;

as a member of RecursiveClass.

So it would seem I would need a pointer-to-optional
or an optional pointer, i.e.,

std::optional<RecursiveClass>* porc_;
std::optional<RecursiveClass*> oprc_;

as my class member.

But I don't see what this buys me -- the optional could
be empty or the pointer could be null (or both), but this
doesn't seem to be a simplification.

> ...
> Chris


Thanks for your thoughts.


K. Frank

[Chris Vine]

Can't you? As I say I have never used it,.

If you can't, the problem is probably that RecursiveClass is not fully
defined at the point you declare the optional of RecursiveClass
member. This is not an issue with unique_ptr but was with auto_ptr,
and maybe is with optional. Dunno. If you are just playing around with
primitive data types for ideas (which is a great thing to do) perhaps
try another language such as python or my preference for prototyping
ideas, namely scheme.