Re: Java Questions Again: What's So Great About Recursion

  • From: "Littlefield, Tyler" <tyler@xxxxxxxxxxxxx>
  • To: programmingblind@xxxxxxxxxxxxx
  • Date: Thu, 07 Apr 2011 11:30:12 -0600

Nothing speaks better than code. So: have some code. :)
This basically sets up a root property called foods, sets up two types of food (meat and fruits), populates the two types with food from that type, with a value and then uses recursion to print it all out. warning: untested code below. It may possibly make your compiler explode or something else odd.

#include <vector>
#include <string>
#include <cstdio>

struct Property
{
Property* parent;
std::vector<Property*> children;
std::string name;
float val;
};

/*
*Will write the property and it's children to screen.
*/
void WriteProperty(Property* prop)
{
std::vector<Property*>::iterator it, itEnd;

printf("name: %s cost: $%f.\n", prop->name.c_str(), prop->val);
itEnd = prop->children.end();
for (it = prop->children.begin(); it != itEnd; ++it)
{
WriteProperty((*it));
}
}

Property* CreateProperty(Property* parent, const std::string &name, float value)
{
Property* prop = new Property();
prop->name = name;
prop->val = value;
prop->parent = parent;
if (parent)
{
parent->children.push_back(prop);
}
return prop;
}

int main()
{
Property *type, *root;
type = root = NULL;
root = CreateProperty(NULL, "foods", 0); //the value has no meaning here.
type = CreateProperty(root, "meats", 0);
CreateProperty(type, "ham", 5.0);
CreateProperty(type, "steak", 11.0);
type=CreateProperty(root, "fruits", 0);
CreateProperty(type, "apple", 1.25);
CreateProperty(type, "orange", 1.25);
WriteProperty(root);
return 0;
}
Enjoy,
On 4/7/2011 10:58 AM, Littlefield, Tyler wrote:
Jim:
Recursion has a limited number of applications where it is actually more useful than a loop, I'll give one I use it for. In my game engine, properties are stored in a tree setup with a root property and all other properties work from there. so, you could essentially have stats.health, stats.mana, etc. stats is the root node, health are the children nodes on stats.
Now, here's where recursion comes in handy.
when I serialize this tree, I write it all in xml. so I'll serialize the stats, then I'll serialize health. what I do is something like this:
Serialize(XMLNode, property)
so lets say that stats.health has two properties: stats.health.hp, and stats.health.max_hp. in order to serialize that I would have to loop through the properties of stats.health, then if hp were to have another property I'd have to loop through those, which could get messy. Rather than do that though, I use recursion. so the serialization setup calls serialize on stats, passing the root, then that function calls serialize on stats.health passing health. I hope I explained that properly. Essentially in summary, it allows me to keep passing in each node of the tree until I am finally done. I can recurse until I get done serializing a branch, at which point I will pop back to where i was because the recursion will return when it's done.

On 4/7/2011 10:51 AM, Homme, James wrote:

Hi,

It's probably my ignorance coming out to bite me again, but I just was reading about recursion in my Java book and thinking that it isn't all that useful because you can do the same stuff with a loop. Maybe the book examples are so simple that I just don't see it's usefulness. They were even saying that recursion eats up more memory than loops do, so I'm wondering why I learned it in the first place, other than to know how it works and that it exists.

Please help.

Thanks.

Jim

Jim Homme,

Usability Services,

Phone: 412-544-1810. Skype: jim.homme

Highmark recipients, Read my accessibility blog <http://mysites.highmark.com/personal/lidikki/Blog/default.aspx>. Discuss accessibility here <http://collaborate.highmark.com/COP/technical/accessibility/default.aspx>. Accessibility Wiki: Breaking news and accessibility advice <http://collaborate.highmark.com/COP/technical/accessibility/Accessibility%20Wiki/Forms/AllPages.aspx>


This e-mail and any attachments to it are confidential and are intended solely for use of the individual or entity to whom they are addressed. If you have received this e-mail in error, please notify the sender immediately and then delete it. If you are not the intended recipient, you must not keep, use, disclose, copy or distribute this e-mail without the author's prior permission. The views expressed in this e-mail message do not necessarily represent the views of Highmark Inc., its subsidiaries, or affiliates.


--

Thanks,
Ty


--

Thanks,
Ty

Other related posts: