Larry Ullman's Book Forums

# Recursive Function

## Recommended Posts

I am trying to figure out best approach to a function similar to yours starting pg 18. But I am building an actual pedigree, 3 or 5 generations. 3 generation as an indexed array count to 6 would gather the amount info needed. I have brain fry. seems like this should be really easy.

Fields are horseid, horse name, sireid, damid. Sire and dam id are horse id of course. I will be printing into divs rather than ul/li. That is why I need to get accurate return in order. Playing with uksort. Do you think Sire and dam separate or single functions?

Any suggestions are much appreciated.

BHB

##### Share on other sites

Pretty much impossible to follow your logic without some example data. I'm not a horse expert and don't intend to become one. Secondly, how will you display it? Printing it to a div instead of an unordered list tells me exactly nothing about what you want. I don't even have any code to judge this by, so I can basically do nothing more for you than teaching you recursion theory, which Larry already does brilliantly in the book.

Sorry for being a bit direct here, but there's literally nothing anyone can do to help you by looking at your post. Try again. Explain the problem not using horse terminology, provide example data, provide code and provide an explanation of what you need to do to explain everything as intended.

• 2
##### Share on other sites

Ok Antonio, I know everyone here is brilliant... Pedigree of a horse is no different than a person really. Table:I'd, name, fatherid, motherid. I have a field for gender but I don't think that is necc.

If I had some code that worked I would not be here with my first cup coffee. . And on iPad,.. Typing is slow.

I have built SELECT statements that do work, they just get really long and ugly to keep up with:

'SELECT I'd, name, fatherid, motherid FROM genealogy WHERE Id = \$id'

UNION

sELECT a.I'd, a.name, a.fatherid, a.motherid FROM a.genealogy WHERE fatherId = I'd

uNION,... Not typed correct but this works.

To print to DIV tags in HTML I need result to be rows not ul/li. If you think about it in logic, Larry's example is top of pedigree down (example would return oldest known, each child, down to youngest.). My need goes the other way. Start with one single person, find their father and mother, grandparents,.. Etc.

array:

\$people[]= array('id=> \$id, 'name'=>\$name, 'fatherid'=> \$fatherid, 'motherid'=>\$motherid) { do something}

Need function to use fatherid and return that array, then motherid and that array,. Father of father array, Mother of father, father of mother, mother of mother.. And so on. Does not really matter the final order of arrays as long as there is a consistent index with the position in family. Ie Array[1] is father. I would like to be able to go as many generations deep as I choose.

I have been searching Internet for some time but do not find a good clean short example. I like Larrys code language and have many of his books. No different than learning French with a dialect. I think this is worthy of posting.

I don't mind being given clues to figure this out by myself. Just point me in the right direction.

BHB

##### Share on other sites

Embarrassing possibly, but here we go:

ie page 20

\$peoples= array();

While(list(I'd, name, fatherid, motherid) = mysqli_fetch_array(\$r, Mysqli_num) {

\$peoples [id][fatherid][motherid] = \$people;

find_fathers(\$people[0]);

Function_find_fathers(\$father) {

Global \$peoples;

For each (\$fatherid as \$id => \$father) {

if(isset(\$peoples[\$fatherid]);

Find_fathers(peoples[\$fatherid]);

}

}

Just a start,.. I don't like the infinite side. Unnecessary. Recursion makes my brain hurt. No matter how I approach I do not see being able to handle father and mother in same function. But that may just be my 'greeness',.. A new horse term: to be green is to have little experience.

##### Share on other sites

Very good. Thanks for providing some context here. That you want a reversed order starting with the latest child is important. Without that, it's hard to provide data. Considering that, the OLDEST generation need to reflect that in the DB. I'll assume you use NULL on father_id and mother_id for that generation. (Or 0, -1, "" or some other value)

Starting with Child X, we need to find father X and mother X and repeat (until the father/mother is null). This sounds like a binary tree. Solutions here requires a good algorithm not be very slow. We therefor need to make sure of your needs first.

My question is: What are you going to use this tree for? Do you only need to print the generations from newest to oldest, on something like this form:

Last Child

Father of child

Mother of child

Father of father of child

Mother of father of child

Father of mother of child

Mother of mother of child

Father of father of fater of child

Mother of father of fater of child

Father of father of mother of child

Mother of father of mother of child

Father of mother of fater of child

Father of mother of mother of child

etc.... ?

I need to be able to visualize what you want to do determine how to solve this. If you have some data in your database, could you attach that here as well?

• 1
##### Share on other sites

horses

id name

1 Joey

2 Secretariat

3 Recursius Maximus

4 The Stud

5 Pam

6 Ed

7 Cyndi

relations

id mom_id father_id

1 2 3

2 5 4

3 7 6

4 NULL NULL

5 NULL NULL

6 NULL NULL

7 NULL NULL

Basically, I'd have all the horse data in one table, and all the familial relations in another.

From here, I found an article that very clearly explains a way to perform recursion on the SQL side, thus greatly limiting the number of queries that you need to execute. Here's the link:

http://www.sitepoint.com/hierarchical-data-database-2/

If you're looking to solve this on your own, that should be enough of a nudge for now.

Good luck, and post again if you're stuck (or find success!).

Thanks.

##### Share on other sites

Yeah, a clue. I do have my table as above with the I'd, name, fathered, motherid. ( Going to whack spell check),..When I add a horse there is auto fill of 0- unknown father and 1-unknown mother. This is important for adding a horse who does not have parents already in database. Once horse name, year born, proper search that horse does not already exist,.. Is entered then one can edit update and go through same process for parents. That is more than need know for this venture. My search is pretty cool though. Have not used Ajax yet but,..

Back to pedigree and goals. I am building a massive database that will provide XML data for my many web horse farm clients. I am tired of hand coding pedigrees!!!!! Links to each in pedigree goes to horses detail page with pics, etc. Plan is that all data entered in one place, ..help maintenance that way rather than copying db to multiple servers every time it is updated. Many of us breeders have same sire lines (father lines) in our pedigree. So there is a lot of repition.

I like the idea of SQL doing the work and only sending necc. This will help my XML goal. Stored procedures: I have just enough reading to know they exist and I will like them. ( have read much of eccomerce book of larrys)

Antonio, yes you have the right idea with data returned. Each having an index/key after query complete allows me to place by number into correct div id with my CSS.

Thank you both soooooo much for helping. I know my english and comm skills not great. I appreciate your patience.

##### Share on other sites

1for unknown father and 2 for unknown mother, not 0, 1.

##### Share on other sites

I don't think those values make sense as they are perfectly legal values that COULD point to a horse. I don't think there's a need to use different values eighter. Use null, -1 or 0 as they won't appear as keys.

As I said, could you provide simple data for 10-20 horses? It would make it much easier to confirm we have the right algorithm. Now, I have to create example data by myself. It would sure be easier to work with some real data. Just do a print_r() on the result from a query, and you'll have those example for us.

I think we could make this work pretty quick.

• 1
##### Share on other sites

I don't see the connection on that link. The id in my database is not because of position, it is an autoid in a list of maybe thousands of horses. I can see that position will need a number but example has position being the id. First horse queried based on variable sent to form. Then query should retrieve fatherid as an array(id, name, fatherid, motherid), motherid as an array (id, name, fatherid, motherid), etc. trick is in writing a function to shorten long worded query.... It is long. I got to second grandmother and knew was best to abort and get function to do work. Maybe I want a six generation pedigree link instead of three. That would be insane code.

I will keep reading link see if I can't translate the info into what I need.

##### Share on other sites

Ok Antonio. I will fire up the computer. Give me a minute.

##### Share on other sites

While getting file, here is a link of an old page. Pedigree does not link, static text probably in a table.

##### Share on other sites

BHB, perhaps I am simply misunderstanding your English, but I think you're misunderstanding the connection.

That article I sent you is absolutely relevant.

For one, no matter how big your DB is, the query is always super short, and you can use it to return any ancestors or descendants of any horse of your choosing.

Also, because it's all running on the SQL side with one to two queries max, you are speeding things up by 10-1000 fold (no joke).

The only downsides are that you are going to have to write the initial algorithms that come up with the left and right metric values, and you're also gonna have to reorder things whenever a new record (i.e., horse) is entered into the DB. It will make the SELECT queries (which I imagine will make up the majority of your site) lightning fast though.

Also, you really should have the familial relations in a separate table in the DB, as I suggested.

Anyway, I'm not saying you have to do it the way I suggested, I just don't want you to dismiss it, because it is very much a valid and solid way to handle recursion.

As an additional note, if you don't want to go the recursion route, then you'll have to come up with some sort of custom ID that allows you to very quickly establish a horses location in relation to others. Given that there is no finite number of generations though, that could get messy.

In general, when you don't know how many generations/levels you're going to have, recursion is your best choice.

##### Share on other sites

hmmm, much to digest. I guess I don't understand why I would separate the tables. would I not take chance of duplicate entries for sire/dam? It takes time for me to absorb, so my initial reaction is just confusion. descendants as a word to me means top down, not bottom up.

Here is some data. Not that I have entered enough to get really good charts yet. Most is sire => 1 and dam=> 2. I can add more flushed out pedigrees is that helps.

Array ( [horse_id] => 1 [horse_name] => Unknown Stallion [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 2 [horse_name] => Unknown Mare [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 3 [horse_name] => CHINN [sire_id] => 1 [dam_id] => 15 ) Array ( [horse_id] => 4 [horse_name] => R-Saluut II [sire_id] => 1 [dam_id] => 1 ) Array ( [horse_id] => 5 [horse_name] => C-Picasso [sire_id] => 3 [dam_id] => 2 ) Array ( [horse_id] => 6 [horse_name] => BROADWAY boogie-woogie [sire_id] => 1 [dam_id] => 15 ) Array ( [horse_id] => 7 [horse_name] => Captain America [sire_id] => 6 [dam_id] => 2 ) Array ( [horse_id] => 8 [horse_name] => R-Flash Gordon [sire_id] => 4 [dam_id] => 2 ) Array ( [horse_id] => 9 [horse_name] => Destiny [sire_id] => 4 [dam_id] => 20 ) Array ( [horse_id] => 10 [horse_name] => Biscotti [sire_id] => 4 [dam_id] => 14 ) Array ( [horse_id] => 11 [horse_name] => Berolina [sire_id] => 5 [dam_id] => 2 ) Array ( [horse_id] => 12 [horse_name] => Byacinthe II [sire_id] => 4 [dam_id] => 2 ) Array ( [horse_id] => 13 [horse_name] => American Girl [sire_id] => 4 [dam_id] => 14 ) Array ( [horse_id] => 14 [horse_name] => Pristine [sire_id] => 3 [dam_id] => 2 ) Array ( [horse_id] => 15 [horse_name] => Frascatti [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 16 [horse_name] => Zu Zu [sire_id] => 5 [dam_id] => 2 ) Array ( [horse_id] => 17 [horse_name] => La Bella [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 18 [horse_name] => VicTaurus [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 19 [horse_name] => Olivia [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 20 [horse_name] => October Secret [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 21 [horse_name] => White Shoulders [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 22 [horse_name] => Daisy [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 23 [horse_name] => Farlapp [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 24 [horse_name] => cZur [sire_id] => 3 [dam_id] => 2 ) Array ( [horse_id] => 25 [horse_name] => Belle [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 26 [horse_name] => Lydia [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 27 [horse_name] => Limbo [sire_id] => 1 [dam_id] => 2 ) Array ( [horse_id] => 28 [horse_name] => Royal Prospect [sire_id] => 1 [dam_id] => 2 )

##### Share on other sites

I can see entering 100 horses a day easy, maybe more. So the reorder each time a record is added sounds scary.

##### Share on other sites

BHB, I've never done recursion myself, so this is all new to me, but after doing so more research, I can assure you that the aforementioned approach is the best one to take. I apologize though, as the article I linked to before was only one page of a three-page article. Here's the entire article:

http://www.sitepoint.com/hierarchical-data-database-2/

Also, here's another link that explains the above approach in more detail (with specific queries):

http://mikehillyer.com/articles/managing-hierarchical-data-in-mysql/

Both articles are very good and are linked to from numerous sources. Something good about both articles is that they explain the traditional approach to recursion (the one you want to take), and why it's bad. Please heed this advice, as this approach of using left and right values is something that seems to have been around in the SQL DB industry for many years. In other words, it's established and proven to be the best way to handle recursion.

Both articles do admit that using the left/right values is a different approach and way to think about recursion, but once you get used to it, it's actually easier to handle. Also, the performance gains are huge and not even comparable to the traditional method.

As for using one table versus two tables, I'm seen arguments for both. For the sake of simplicity and easier queries though, one table should be fine if that's what you want.

Anyway, if you want to use a DB structure for your horse DB, I think the above method is your only viable choice. If you'd rather use XML, that is an option, but it will be slower for sure.

For my last two points, "descendant" means something below something else. That same phrase and usage exists in XML as well. Also, as a general rule, there's always a trade-off in the performance of SELECT statements and INSERT/UPDATE statements. If you optimize a DB for SELECT statements (which you should do), then INSERT/UPDATE statements will be a bit slower.

Since I imagine your clients will mostly be using SELECT statements though, you'll definitely want to design your DB to be optimized for SELECT statements, even though it'll add a little (probably not even noticeable) time to the processing required to insert and update records.

##### Share on other sites

Ok, reading this. Being my experience level I can not argue approach. Right off I am seeing that this returns position (design). I want to be able to produce CSS div tags. Will I be able to with this method? This is mandatory for me. I wish I had 12 hour days to study and learn everything out there but I only get a couple hours/ day.

Another important criteria is to produce XML. You must understand if I want to produce information to 100, 800 domains on many servers i have only one method to do this that makes me feel as a business owner will satisfy producing my product. XML data.

I have to this point really only learned Larry Language. I can wrap my brain around other but will take me some time to get it. I ask these questions ahead (divs and XML ) so I know I am climbing the right tree!! Ha ha ha!! If nothing else it will help me learn to think outside my box. I still must learn this chapter in Larry's book as well. It is not ok with me to hit a dead end when I set out to learn something. Correct method or not, these are most worn pages in any of my books.

So back to page 19-20? That function I wrote will go up single line of sireid right? Makes me think I must encorporate the damid into single function. Array with just three id should be iterated each to three id each,.. I can call the names after id are found with a stop.

Array(horseid, sireid, damid)

##### Share on other sites

Hmmm, hartley-how do you auto fill left and right position for tree? This must be entered by hand or an algorithm? I am not very patient am I?

##### Share on other sites

Good gracious! This is way over my head. I am in kindergarten code I guess. I don't see me writing this amount of code to produce pedigrees,.. The depth of these queries is unbelievable! I am just starting with stored procedures. This method is a bit familiar; I think I had come across it before. I am only 18 months self taught in my spare time. Makes the self join loop in Larry's task example look so simple.

You have not use recursive functions? You want me to learn this, I think you should make a recursive function!!! In jest,. you must be a genius and it would only take you 10 minutes. What about CSS? Do you have design in your bag of tricks?

##### Share on other sites

The CSS and layout is really inconsequential and has no relation to the DB design.

The CSS and HTML layout can be whatever you want it to be, and it can easily be adapted to any DB design, regardless of how you return the data. If you want divs instead of lists, that's very easy to do.

Given you current level of knowledge, I think we can both safely say that going with straight XML files/XML in the DB will likely be the best solution. Just know that going with straight XML will be slower and less efficient. If you can come up with a good way to centrally manage the XML and always keep it up to date with everyone using it though, I'd go that route and stop worrying about recursion.

I apologize for apparently talking over your head. That was not my intention, but please keep a couple of things in mind:

1) You posted your question in the advanced PHP forum, so a lot of knowledge is assumed.

2) You asked about the best way to handle hierarchical data, and I answered your question. At this point, I really don't think there's any debate about the best method. I think the question instead needs to be: What's the best method for you at your skill level and time you have available.

If there's anything else I can do to help, please lemme know. Otherwise, you may want to start seriously thinking about how to structure your XML and also think about writing some basic API functions for simplifying data insert and retrieval.

##### Share on other sites

Well thank you, I understand. I would like to further understand this books chapter. Maybe then i will better understand your method.

Anyone willing to attempt helping me on the books method??

##### Share on other sites

What, exactly, are you wondering about the book's method?