Main Page Content
BBS style recursion How-To
Rated 3.63 (Ratings: 2) (Add your rating)
Log in to add a comment
(5 comments so far)
Steve Cook
User since: August 29, 1999
Last login: August 02, 2000
Articles written: 11
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:
| 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 |
Here's an extract of information from the table:
| 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
Many of the scripts I have seen around to do this use a set maximum number of levels. One can then use either SQL JOINS or a set number of tables, or an extra field for depth to make the scripting simpler. In my case I don't know how deep the recursion can go, so I need to write something that will handle any level of depth. The magic word here is "recursion", which basically is a technique for writing short pieces of code which keep running themselves in a controlled loop until the task at hand is completed.
I'll explain the script as it goes along using PHP comments.
<small>
<pre>
?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 results
function depth($depth) {
for ($i=1; $i<= $depth; ++$i) {
print "&nbsp;&nbsp;&nbsp;&nbsp;";
}
}
?>
<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>\n");
// 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>\n";
find_child($parentID, $startSeed, $depth);
?>
</body>
</html>
</pre>
</small>
