• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Paul Clapham
  • Ron McLeod
  • Bear Bibeault
  • Liutauras Vilda
Sheriffs:
  • Jeanne Boyarsky
  • Tim Cooke
  • Junilu Lacar
Saloon Keepers:
  • Tim Moores
  • Tim Holloway
  • Stephan van Hulst
  • Jj Roberts
  • Carey Brown
Bartenders:
  • salvin francis
  • Frits Walraven
  • Piet Souris

Storing a Variable during Recursive calls

 
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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:



Thank you very much for the help!
 
Marshal
Posts: 71730
312
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Campbell Ritchie
Marshal
Posts: 71730
312
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
Saloon Keeper
Posts: 7618
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator


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.
 
Michael Grünau
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7618
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7618
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
It is possible that every node is a Penguin.

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

 
Carey Brown
Saloon Keeper
Posts: 7618
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
So, only count self if it's a penguin.
 
Michael Grünau
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Saloon Keeper
Posts: 7618
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Marshal
Posts: 71730
312
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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
Saloon Keeper
Posts: 7618
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
"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
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
@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:



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
Saloon Keeper
Posts: 7618
68
Eclipse IDE Firefox Browser MySQL Database VI Editor Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Michael Grünau
Ranch Hand
Posts: 65
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thank you very much for the help!

I actually saw that it was redundant and changed my code accordingly just a Minute ago.
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic