3
\$\begingroup\$

I was tasked with writing a Matryoshka doll program that manages the following:

  • howManyDolls : returns an integer based on how many dolls are inside the stack
  • howManyWearingBabushkas : returns an integer based on how many dolls are wearing a Babushka. The boolean variable babushka determines this.
  • totalWeight : returns a double based on the weight of all the dolls in the stack

I would appreciate feedback on the recursion part of the code, if it's the most efficient/proper way to use recursion in this context. I am very new to recursion, so I want to make sure I am doing the best I can going forward.

public class Matryoshka {

    private String name;
    private double weight;
    private boolean babushka;

    private Matryoshka innerDoll;

    public Matryoshka(String name, double weight, boolean babushka) {
        this.name = name;
        this.weight = weight;
        this.babushka = babushka;

        this.innerDoll = null;
    }

    public Matryoshka(String name, double weight, boolean babushka, Matryoshka doll) {
        this.name = name;
        this.weight = weight;
        this.babushka = babushka;

        this.innerDoll = doll;
    }

    public String getName() { return this.name; }
    public double getWeight() { return this.weight; }
    public boolean getBabushka() { return this.babushka; }

    public boolean hasInnerDoll() {
        return this.innerDoll != null;
    }

    public Matryoshka getInnerDoll() {
        return this.innerDoll;
    }

    public int howManyDolls() {
        if(this.innerDoll == null) { return 1; }
        return 1 + this.innerDoll.howManyDolls();
    }

    public int howManyWearingBabushkas() {
        if(!this.hasInnerDoll()) { return 0; }
        if(!this.getBabushka()) { return 0 + this.getInnerDoll().howManyWearingBabushkas(); }
        return 1 + this.getInnerDoll().howManyWearingBabushkas();
    }

    public double totalWeight() {
        if(!this.hasInnerDoll()) { return this.getWeight(); }
        return this.getWeight() + this.getInnerDoll().totalWeight();
    }

}
\$\endgroup\$
3
\$\begingroup\$

Naming

Field babushka should be named wearingBabushka, since that is what the field describes. The method accessing it becomes isWearingBabushka(). For some reason Java-people like exceptions in naming standards and are adamant that it's vital to have a non-standard getter name for boolean typed methods (yes I'm bitter about this, no need to go into it any deeper).

Final modifiers

The fields should be final, as they are not meant to be changed. Non-final fields always increase the cognitive load on the reader as they have to figure out where the fields are modified.

Constructors vs. static factory methods

In this application it could be useful to instantiate the objects with static factory methods.

public abstract class Matryoshka {

    public static Matryoshka of(String name, ...) {
        return new RootMatryoshka(name, ...);
    }

    public static Matryoshka of(String name, ..., Matryoshka innerMatryoshka) {
        Objects.requireNonNull(innerMatryoshka);
        return new OuterMatryoshka(name, ..., innerMatryoshka);
    }
}

Static factory methods allow you to return a different implementations when needed. The root matryoshka would return static values from the methods that calculate weight etc. The outer matryoshkas would simply perform recursion and addition with no need for null checks (as the factory method prevents null values). There are rules on how classe that use static factory methods should be written, I won't replicate them here.

But that's pretty much a matter of taste. The current implementation is just fine too.

Bugs

If the root matryoshka wears a babushka, the calculation returns an incorrect answer.

Style

I find the unnecessary use of this distracting. In my opinion it should be used only when there is a naming conflict. When done so, the number of references to this can be used as a metric for bad naming or problematic structure.

Tail recursion

Since you asked about efficiency, I have to talk about tail recursion. But be aware that this all is total and complete premature optimization. Each of the recursive methods could be replaced with a loop, which would eliminate the need for populating the stack on each recursion:

public int howManyDolls() {
    int dollCount = 0;

    Matryoshka currentDoll = this;
    while (currentDoll != null) {
        dollCount++;
        currentDoll = getInnerDoll();
    }
    return count;
}

It probably won't affect running time, but at least you're not limited by the stack size. You can have millions of matryoshkas! But you will fail the recursion task, since now this has none.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.