Storing a Variable during Recursive calls

[Michael Grünau]

Hello Friends,

hope everyone is doing great.

I am working on a task for my University Project and I am super stuck a this point.
The task contains a tree in which we need to build a string with char concatenation.

My problem is that we need to write a method which counts the names we have build in this tree via recursive method calls.
What I don't understand is how I can save my count or add-up to this count during my recursive calls, I don't want to store the count in a parameter which gets called by a method.

Hope this is somewhat clear...

My approach using a Support-Method:

    public int size() {
        return size(0);
    }

    public int size(int count) {
        if(penguin != null)
            count++;
        for(int i=0; i < children.length;i++) {
            if(children[i] != null) {
                return children[i].size(count);
            }
        }
        return count;
    }

Thank you very much for the help!

[Campbell Ritchie]

All's well here except for the ice.

Please explain more. In a recursive call you would usually pass arguments and receive a returned result.

public static int recursiveMethod(XYZ xyz)
{
   return xyz.something() ? 0
                          : 1 + recursiveMethod(xyz.someReduction());
}

[Campbell Ritchie]

Please don't edit posts like that; it makes it look as if I hadn't read the code, which wasn't there when I replied

[Michael Grünau]

Sorry, my bad.
I just think it is always better to provide some code to questions so people can see how I tried to deal with the problem.

Thank you very much for the quick reply btw.



My problem is, that I understand how you can use recursion for Binary-Trees when you basically just have a right-left option.
In my case there is the probability of 26 nodes afterwards each representing a character in the alphabet (children = array with a length of 26).

I don't find a nice way to iterate through all these options and check if there is an object stored in them and check the next options again...hope this makes somehow sense.
So I can store the variable in a parameter call but aren't there ways where I can do it without it?

[Carey Brown]

   public int size(int count) {
       if(penguin != null)
           count++;
       for(int i=0; i < children.length;i++) {
           if(children[i] != null) {
               return children[i].size(count);
           }
       }
       return count;
   }

I don't see why you'd need to pass the count down through the recursion. As you descend each level you'd want to return the sum of the sizes of all of its children plus one for itself. So you should only be passing the count back up the chain, not down.

public int size() {
    int count = 1; // itself
    for( var child : children ) {
        if( child != null {
            count += child.size();
        }
    }
    return count;
}

[Michael Grünau]

Thank you very much for the reply!
Correct, I want to pass the count back up the chain.


My problem is, that I saw a solution like your multiple times when I search the web but I don't want to count every node.
I only want to count the node if there is a penguin inside so: penguin != null .

How do I add my case to the count += child.size() ?

[Carey Brown]

I question what kind of Collection you are using to hold "children". I would think that you wouldn't want any null child to be stored in your children Collection.

[Michael Grünau]

So the task is about concating chars to a String.

There are random names and each node beginning with an empty "" stands for a Character in the Alphabet.
So we basically have the option of 26 leaves per node to create names.

If we reach a node which builds a name together with its prior Chars we register the penguin(name) at this node. Otherwise we leave the nodes "empty".

For example:

Name: Allan

First Node: ""

Second Node: A

Third Node: AL

....

End: ALLAN - Register Penguin Allan

[Michael Grünau]

And sorry.

Children is an array of Nodes with the length 26 - where children[0| stands for A, children[1| stand for B etc.

[Carey Brown]

Michael Grünau wrote:I don't want to count every node. I only want to count the node if there is a penguin inside so: penguin != null .

Can the parent node be a penguin or only child nodes? So, if a node is found that IS a penguin you want to pass that count up the chain, ELSE you want to pass 0 up the chain. Correct? So, in the end you return the sum of penguin nodes.

[Michael Grünau]

It is possible that every node is a Penguin.

So it is basically just node count method based on a specific parameter.

[Carey Brown]

So, only count self if it's a penguin.

[Michael Grünau]

Exactly, and if it is a penguin we want to add +1 to the count and if not just check if the children are a penguin.

[Carey Brown]

Michael Grünau wrote:Exactly, and if it is a penguin we want to add +1 to the count...

Show us how you'd do that.

...and if not just check if the children are a penguin.

No, you always want to sum up the count of the children otherwise you wouldn't be counting their penguins.

[Campbell Ritchie]

Michael Grünau wrote:Sorry. . .

Apology accepted

. . . it is always better to provide some code . . .

A new post would be better. And it increases your total post count.  

[Carey Brown]

"size()" no longer represents just the size, "numberOfPenguins()" would be better. Also, providing an "isPenguin()" method to hide the "penguin != null" would make the intent more obvious.

[Michael Grünau]

@Carey Brown: That might be true, but I am unfortunately just the poor student working on the tasks, restricted by the cruelty of our education system spending 10 hours on a Saturday to implement three methods.


So I came up with the following approach for my size() Method:

    public int size() {
        int count = 0;
        if(penguin == null) {
            for(int i = 0; i < children.length;i++) {
                if(children[i] != null) {
                    count += children[i].size();
                }
            }
        }
        else {
            count++;
            for(int i = 0; i < children.length;i++) {
                if(children[i] != null) {
                    count += children[i].size();
                }
            }
        }
        return count;
    }

To be honest, I don't really think it is working because the count variable should reset every time when I call the method.
I have no idea how I can include the variable and keep it in the recursion and the loop without using another method.

[Carey Brown]

Your logic was correct but you needed to refactor your code a bit to eliminate the redundant code. Also note that for each call of size() a new local variable "count" is created and initialized to zero. You don't need to reset it because they are not shared even if they have the same name.

    public int size() {
        int count = 0;
        if(penguin != null) {
            count++;
        }
        for(int i = 0; i < children.length;i++) {
            if(children[i] != null) {
                count += children[i].size();
            }
        }
        return count;
    }

[Michael Grünau]

Thank you very much for the help!

I actually saw that it was redundant and changed my code accordingly just a Minute ago.