Main Page Content
Bbs Style Recursion How To
A moderately common programming task is to write a script to create an indented, hierarchical list. It's something that I've had to do several times and each time I've forgotten the basic technique. Having spent too many hours recently puzzling the technique out again, I thought I would write an article about it to share the message and to ensure that I have a copy of my code somewhere where I can't delete it :-) Because I've been programming in PHP a lot lately, the code is PHP and the database is mySQL, but I'll try and explain the technique so that you can implement it in your language of choice. The first thing you need is some information in a database table. I'm using a table called Categories with the following fields:
Here's an extract of information from the table:
Which we want to end up looking like this:
| Field | Type | Null | Key | Default | Extra | Comment |
| CatID | bigint(21) | PRI | 0 | auto_increment | - individual key | |
| CatName | varchar(32) | - Text field containing my category name | ||||
| CatParent | bigint(21) | YES | NULL | - contains the CatID of the parent record, or NULL for the top level |
| CatID | CatName | CatParent |
| 1 | Developer | NULL |
| 7 | Tools | 1 |
| 8 | Reference | 1 |
| 9 | Tutorials | 8 |
| 10 | Docs | 8 |
| 11 | Developers | 1 |
| 12 | Hardware | 11 |
| 13 | Software | 11 |
- Developer
- Tools
- Reference
- Tutorials
- Docs
- Developers
- Hardware
- Software
- Services
- Software
- Reference
?php/* BBS_style_recursion.php Steve Cook december 2000 cookie@yoyo.org / sck@biljettpoolen.se Feel free to make use of this code - I would be interested in hearing of any improvements! The script starts by setting up some variables, and
creating the database connection.*/$link = mysql_connect ("localhost", "username", "password") or die ("Could not connect");mysql_select_db("wapwarp");/* The SELECT statement orders the results so that the categories are placed in groups with the same parent.*/$result = mysql_query ("SELECT * FROM Categories ORDER BY CatParent, CatID ASC;") or die ("Invalid query");$i = 0;/* The results are placed in a 2d array. In an ASP script I would keep the results in a dynamic resultset and navigate through that, but in PHP we don't have the same result structure and so we need to use an array.*/while ($result_row = mysql_fetch_row($result)) { $result_array[$i] = $result_row; $i++;}// Here we get some information from the script// that we use later to initialise our recursive// functions.//// These are our startup variables for our// recursive functions... you'll see!$parentID = $result_array[0][0];
$arr_size = count($result_array);$depth = 1;$startSeed = 1;// Just a tiddly little function to print // indentations in front of the resultsfunction depth($depth) { for ($i=1; $i<= $depth; ++$i) { print " "; }}?>
<html><head><title>BBS Style recursion</title></head><body><?php/* Here's where the real meat of the program starts. It's actually the second of two functions that format our results. Because functions are defined before they are called in PHP it comes first in the script. You might want to read the description of find_child first! Okay, step-up is called by the find_child function
when it cannot find any more children in a particular branch of categories.*/function step_up ($parentID, $startSeed, $depth) { global $result_array; global $arr_size; // The first thing we'll check is that $start_seed // hasn't gone off the end of our result_array. // If it has, we'll stop execution of this function. if ($startSeed > $arr_size) { return; } else { // if the CatParent of the last category is // equal to the CatParent of the next category // then they are on the same level. We'll move // along to it and check to see if it has children // This was why we chose to order our results by // CatParent first in our SELECT statement. if ($result_array[$startSeed-1][2] == $result_array[$startSeed][2]) { $depth--; return find_child($result_array[$startSeed-1][2], $startSeed, $depth); // Otherwise, if the last CatParent was NULL and // the current is 1, we stop processing // as we have covered all the top level // (again, we know this thanks to our SELECT // statement ordering) } else { if ($result_array[$startSeed-1][2] == "" && $result_array[$startSeed][2] == 1) { return; } // If they were unequal, and we haven't reached // the end of the list, we need to // climb back to this category's parent and // restart this checking process. More recursion! for ($j = 0; $j <= $arr_size; ++$j) { if ($result_array[$j][0] == $result_array[$startSeed-1][2]) { $depth--; return step_up($result_array[$j+1][0], $j+1, $depth); } } // I've forgotten what this return does, but it's // probably something important! // Best leave it there :-) return; } }}/*
The find_child function is the part of our recursive process that steps down the category list. It is fed the CatID of the last category we got from our results. This is the potential "parent" of other categories, so I have called it $parentID. It is also fed a $startSeed, which is the position of the current result we are looking at in $result_array. There's also a $depth variable which is used for formatting purposes.*/function find_child ($parentID, $startSeed, $depth) { global $result_array; global $arr_size; // This for loop starts us where we left off in // $result_array and steps through the results. for ($k = $startSeed; $k <= $arr_size; ++$k) { // If we find a result where the catParent is // equal to the CatID of our current result // then we've found a child. if ($result_array[$k][2] == $parentID) { // We can then do whatever we need to do // with our category. // In this case we'll print it out with some // depth formatting. depth($depth); print ($result_array[$k][1] . "<br>"); // then we need to reset our startup variables - our // current result could now be a parent itself. $parentID = $result_array[$k][0]; $startSeed = ++$k; $depth++; // Finally we recall find_child with our new values // to see if this category contains sub-categories. // This is recursion at work! return find_child($parentID, $startSeed, $depth); } elseif ($result_array[$k][2] > $parentID) { // Simply a little code to save some processing time. // We'll break out of the loop if we've gone // past the parent value break; } } /* If we didn't find a child, then we've gone as far down this particular branch of categories as we can. We need to keep our startup variables the same and use our second function - step_up to either find further results on the same level, or to take us back up the category tree. */ step_up ($parentID, $startSeed, $depth);}/* Okay, we've defined all our recursive functions, all we need to do now is print the first category which we got from the results right at the beginning and then kick the whole operation into action. With any luck, it should run all the way through the results, finding it's way down the lists of categories and climbing back up again to start down new branches until it reaches the end of the results list.*/print $result_array[0][1] . "<br>";find_child($parentID, $startSeed, $depth);?>
</body>
</html>
