Using Recursive Functions in PHP to Manage Hierarchy
The recursive function is an essential tool for anybody developing PHP sites that feature multiple levels of categories, pages etc. In fact, they are great for managing hierarchical relationships (sometimes referred to as parent/child relationships). There are many applications of this, but the example I’m going to show you is categories, such as you might use in an eCommerce site. This is one of those wonderfully simple techniques that once grasped, will open up a myriad of possibilities for the programmer.
Firstly, you need to know what a recursive function is. Simple really: it’s a function that calls itself. All will become clear.
I’ve worked with programmers of varying skill levels, and I have often seen them deal with product categories in entirely the wrong way. When a customer requests top level and sub-categories, the programmer creates 2 or more seperate tables to cope with each level. This just doesn’t make sense, so let me show you the right way to do it.
Let’s assume that our customer has requested an unlimited number of levels of categories. This is tackled with a parent/child relationship - i.e. each category apart from the top level will have a “parent” that it belongs to. Let’s build that table in MySQL:
CREATE TABLE categories (category_id INT NOT NULL AUTO_INCREMENT, category_name VARCHAR(100) NOT NULL, parent_id INT NOT NULL, PRIMARY KEY (category_id));
This SQL statement creates a table called “categories” with just three fields:
category_id
This is the ID number of the category and will be automatically assigned because we have selected the AUTO_INCREMENT option.
category_name
The name of our category. I’ve set this to a limit of 100 characters, but you can adapt for your particular scenario.
parent_id
And here is the all important parent field. This field will by default contain a 0, in which case there is no parent and therefore the category is top level. Otherwise, we can put in here the category_id of the parent record that we want this category to appear under.
This kind of setup works well and is really easy to code for drilling down the categories. You just create a page that displays all the categories that have a specific “parent_id”. You can pass that ID in the query string, and default to 0 if no ID is present (i.e. if you don’t pass an ID, it assumes 0 and therefore displays the top level categories). If you’ve found this page via Google I’m guessing you already got this far.
Now, let’s assume the client has asked for a breadcrumb trail for the categories. How do we know how many levels deep we are? How can we build that crumb trail, bearing in mind that we have to work backwards from the child up through numerous parents to the top level category, and the crumb trail needs to be written forwards on the page from the top level down. Here’s where a recursive function will solve the problem.
What we will do is create a function that when passed a category ID, extracts the name of the category and the ID number from the database and writes these values to two arrays - one containing the name and one containing the ID. (I would actually do this with one multi-dimensional array, but for the purposes of keeping things simple here for new programmers, we’ll just use two single dimension arrays. If you’re comfortable with multi-dimensionals then modify the code if you wish.) Next, the function will check if the parent_id is greater than zero, if it is then there must be a parent category, and in that case the function will call itself again (recursion). This loop will continue until the function hits the top level, by which time we will have all the data for the crumb trail in our arrays. The only problem is that the data will be in reverse (child to parent), but thanks to PHP’s array sorting functions, we can easily resolve that. Then, all that’s left is to cycle through the arrays with a foreach loop and build the crumbtrail. OK, here we go - don’t forget to put your MySQL connection string at the top of the page!
<?php
$crumb = “”;
//here we call our function - pass your ID variable for the current category here
buildCrumb($id);
function buildCrumb($id) {
//make sure we can use our arrays outside of the function
global $crumb_arr;
global $crumbid_arr;
$sql = “SELECT * FROM categories WHERE category_id=’” . $id . “‘”;
$data = mysql_fetch_assoc(mysql_query($sql));
//store values into the next key on the array
$crumb_arr[] = $data[’category_name’];
$crumbid_arr[] = $data[’category_id’];
//check that parent_id
if($data[’parent_id’] > 0) {
//call function recursively and pass ID
buildCrumb($data[’parent_id’]);
}
}
//reverse sort the arrays (sorting on the key not the value)
krsort($crumb_arr, SORT_NUMERIC);
krsort($crumbid_arr, SORT_NUMERIC);
//cycle through arrays - we only need to cycle through one as the keys will be identical on both arrays
foreach($crumb_arr as $key => $value) {
$crumb .= “<a href=’yourpage.php?catid=” . $crumbid_arr[$key] . “‘>”;
//we are pulling data from MySQL so we must clean slashes
//and protect against HTML code in the category names
//using stripslashes and htmlspecialchars
$crumb .= stripslashes(htmlspecialchars($value)) . “</a> > “;
}
//our crumb will have a trailing > character with a space either side -
//let’s chop that off
$crumb = substr($crumb, 0, strlen($crumb) - 3);
?>
And there you have it. In this example the current category will also have an <A> tag around it. You could run an IF statement to check if the ID is the sames as the current category and then in that case, not add the link code.
There is no limit to the amount of levels this code will cater for, and it has many more applications than just a crumbtrail. Hopefully, it will have provided you with a good introduction to the power of recursion. Let me know your comments and suggestions.
the article has really helped me in my project i am so helpfi\ul and i will hep others to see this example so that they can benefit from this simple but most powerful example
thanking Ch.harikrishna,india
Wow Great tips thanks
thanks, this is just what I was looking for, now let’s hope I can get it to work!
-Dan, php newbie
Sorry to disturb you, but isn’t maybe this a bit too recursive.
It seems to work OK (it takes some time), but to me it asks to download an empty file named *.php (the
script’s name).
Can you give me some suggestion please ?
It’s very very strange.
Thanks
Luckylinux
Lucky,
I don’t know if something can be “too recursive” - it’s either recursive or it isn’t. However, this script has nothing to do with opening files, and this sounds more like a server configuration error to me. If you can email me the link to the page and attach the source code you are using, I’ll take a look for you.
Cheers,
David
thanks a lot
its works for me
David
Great code. One point I noticed - the closing anchor tag seems to have gone missing.
My question is, however, how can I code your program so the anchor tags of each link are the aggregation of the previous link components?
Example: With the breadcrumb trail ‘Interests > Computing > Linux’ I want the ‘Linux’ anchor tag to read ‘a href=”/interests/computing/linux.htm”‘ and the ‘Computing’ anchor tag to read ‘a href=”/interests/computing.htm”‘
Very much appreciate your insight into this.
Thanks DMark - I’ve restored the closing tag. Wordpress is pretty crap for stripping stuff out when you don’t want it to!
There are many ways to solve your problem, the easiest (and least elegant) would be to simply store the URL string in the database too. Off the top of my head, I would probably tackle it by adding an extra field to the database for URL name, in which you can put ‘computing’, ‘linux’ or whatever it needs to be. (You could perform a variety of functions to turn the main name into the URL and do away with this extra field, but that won’t work well for long names.)
You will need another global variable to handle the URL string and you will need two more functions. The first function will be a handler that reverse sorts the array, adds the .htm on the end and returns it two the first function. Before it does that, the handler will call another recursive function that works backwards through the database in the same way as the first recursive function to build the array of URL names.
I’m sure there is a way to do it all in the one function, but I don’t have the time to sit down and figure it out, and after a day of coding, my brain is just not accepting new challenges! Anyway, this method will work, and though on the face of it, it looks like it might be a bit resource hungry, it really isn’t and will run perfectly quickly.
great work by u ………….
but i have a question how do we achieve recursion based upon values from two tables where value in one of the table is recursive to show a tree like structure
Siddiquip,
I’d need more info to give a meaningful answer on that one.
David
Well currently i have this situation ..I have two tables Files,FileFiles their definition are as follows
CREATE TABLE `FileFiles` (
`Parent_Id` int(11) NOT NULL default ‘0′,
`Include_Id` int(11) NOT NULL default ‘0′,
PRIMARY KEY (`Parent_Id`,`Include_Id`)
) TYPE=InnoDB CHECKSUM=1 DELAY_KEY_WRITE=1 ROW_FORMAT=DYNAMIC;
/*Data for the table `FileFiles` */
insert into `FileFiles`(`Parent_Id`,`Include_Id`) values (21,22),(22,23);
/*Table structure for table `Files` */
DROP TABLE IF EXISTS `Files`;
CREATE TABLE `Files` (
`File_Id` int(11) NOT NULL auto_increment,
`File_Type` tinyint(4) NOT NULL default ‘0′,
`File_Name` varchar(255) default NULL,
`File_Version` varchar(255) default NULL,
`File_Info` varchar(255) default NULL,
`File_Server` int(11) default NULL,
`File_Location` varchar(255) default NULL,
PRIMARY KEY (`File_Id`),
UNIQUE KEY `File_Name` (`File_Name`,`File_Server`,`File_Location`)
) TYPE=InnoDB CHECKSUM=1 DELAY_KEY_WRITE=1 ROW_FORMAT=DYNAMIC;
/*Data for the table `Files` */
insert into `Files`(`File_Id`,`File_Type`,`File_Name`,`File_Version`,`File_Info`,`File_Ser ver`,`File_Location`) values (1,1,’alcatel_osos_WMRM.props’,NULL,NULL,3,’/opt/Omnibus/tsm/solaris2′),(2,1,’alcatel_osos_NZLRM.props’,NULL,NULL,3,’/opt/Omnibus/tsm/solaris2′),(3,1,’lucent_g2itm1_sc.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(4,1,’lucent_g2itm2_sc.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(5,1,’mv36_ZEM1.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(6,1,’mv36_ZEM2.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(7,1,’mv36_ZEM3.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(8,1,’mv36_ZEM4.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(9,1,’mv36_NWAEM1.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(10,1,’mv36_NWAEM2.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(11,1,’mv36_NWAEM3.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(12,1,’mv36_NWBEM1.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(13,1,’mv36_NWBEM2.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(14,1,’mv36_NWBEM3.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(15,1,’mv36_NOEM1.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(16,1,’mv36_NOEM2.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(17,1,’mv36_NOEM3.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(18,1,’mv36_MEM1.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(19,1,’mv36_MEM2.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(20,1,’mv36_MEM3.props’,NULL,NULL,3,’/opt/Omnibus/probes/solaris2′),(21,2,’mttrapd.rules’,NULL,NULL,3,NULL),(22,3,’mttrapd.include.rule s’,NULL,NULL,3,NULL),(23,4,’mttrapd.lookup’,NULL,NULL,3,NULL),(24,2,’huwaei.ru les’,NULL,NULL,3,NULL),(25,2,’mm.rules’,NULL,NULL,3,NULL);
The FileFiles table is a link table that links to the Files Table
Now i wish to create a page in php to access all the files (which i managed to create) but it should also show the files which it includes in hierarchy
eg if my FileFiles table is like this
parent_id include_id
21 22
22 23
22 24
so when a user wants to find a relation for file 21 we should be shown as follows
21->22->23
->24
or if i want info about file 24 then it should show
21<-2223
for all in hierarchy .The only way that can be achieved is by using File_Type field in Files Table
such that if type =2 the file will have hieracrhy lower down the order(ie childs)
type =3 will have both parents and childs
type = 4 will have only parents and no childs
therefore i need to implement a recursion based upon a field in another table withould having
knowledge about the depth (which can be more that 20 levels in both direction)
any hint about how this can be achieved?
Thanks
So the question really is where in the hierarchy does a particular file sit, and based on this, which direction should you run the function? I’m assuming you want this to be automatic, so you can do away with the File_Type field in your example.
My example above works backwards based on the parent ID, i.e. it checks if the current record has a parent ID greater than 0 and recurses if it does. You could just as easily make a recursive function that runs forwards, however this starts to get a little more complicated, because one of the children, could also have children of it’s own. So, whereas working backwards is always straight up, working forwards can end up with a tree like structure.
The simple answer is to have two functions, one that generates the parent lineage, and one that generates the tree of children.
The second function is more difficult and won’t work so well with the global array method. However, you could run a simple query to test whether you need to run the function or not. Something like: “SELECT Include_Id FROM FileFiles WHERE Parent_Id=’CURRENT_FILE_ID’ LIMIT 1
If the above query returns a number greater than zero, then the file has children and the function should be run.
I would then create a global output variable and concatenate each level onto that. Here’s a rough outline:
function findChildren($id) {
global $ob;
$sql = “SELECT ff.Include_Id, f.File_Name FROM FileFiles AS ff LEFT JOIN Files AS f ON ff.Include_Id=f.File_Id WHERE ff.Parent_Id=’” . $id . “‘ ORDER BY f.File_Name ASC”;
$rs = mysql_query($sql);
$ob .= “< ul >“;
while($data = mysql_fetch_assoc($rs)) {
$ob .= “< li >” . stripslashes(htmlspecialchars($data[’File_Name’)) . “< /li >“;
$children_check = @mysql_result(mysql_query(”SELECT Include_Id FROM FileFiles WHERE Parent_Id=’” . $data[’Include_Id’] . “‘ LIMIT 1″), 0);
if($children_check) {
findChildren($data[’Include_Id’]);
}
}
$ob .= “< /ul >“;
}
I’m writing this code in a comment box, so apologies for any errors (hence the spaces in the HTML tags). What this code should do is create an output buffer ($ob) than can be echoed out to the browser. In this example we create nested unordered lists, and I have used a join in the query so that we can order by file name, or whatever we want. The function will literally spider down every possibility from the top to the bottom.
This sort of recursive function is especially useful for site maps.
I think from this code and the code above you should be able to resolve your issue.
As a quick note, I am happy to help people out, when I have time. I don’t always have the time to help. If my code does help you, I would appreciate a credit and a link.
Happy coding!
David
Not even a word of thanks. This is why I won’t be helping anybody with their code anymore. Very poor show siddiquip.