Recursive structures are built by defining classes for
base & recursive cases,
both of which implement the same
BaseRects & NestedRects
both implement NestedRectsInterface
Flower & Broccoli
both implement BroccoliPart
A class represents a base case if it has no instance variable whose
type is the defined interface or one of the other classes.
As we have seen the base case is generally easy to write and verify.
A class represents a recursive case if it has one or more instance
variables whose type is the interface or one of the classes being defined.
Designing the constructors and methods of the class representing a
recursive structure requires a bit more care. The idea is that we
must make sure that the consturtors and methods always terminate
(don't run forever) and convince ourselves that the constructors
and methods work properly.
Checklist (ie, step by step instructions on how-to proceed), also from p.319...
Define an interface with all the methods that both the base
and recursive case classes must implement.
Define one or more classes representing base cases.
Make sure that all methods from the inerface are implemented.
Convince yourself that the constructors and methods work correctly.
You will probably be pretty convinced if you write a
test client and run it to see that all is well!
Define the constructors for recursive classes.
Recursive calls of the constructor should only
create objects that are simpler than the one being
built by the constructor. (ie, "closer to" the base case )
Similarly, instance variables whose types are either the interface
or class should only refer to objects simpler than the one being
constructed. In particular, the construction of simpler objects
in the constructor body should eventually end up at a base case.
Convince yourself that the constructor will be correct under the
assumption that the construction of simpler objects is correct.
Write each method under the assumption that it works correctly on
all simpler objects. Convince yourself that the methods will be
correct under the assumption that the instance variables hold
StackOverflow if you go the wrong way... ie NOT "closer to" base case