Skip to page content or Skip to Accesskey List.

Work

Main Page Content

Bbs Style Recursion How To

Rated 3.64 (Ratings: 2)

Want more?

  • More articles in Code
 
Picture of Ratface

Steve Cook

Member info

User since: 29 Aug 1999

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

Which we want to end up looking like this:

Developer

Tools

Reference

Tutorials

Docs

Developers

Hardware

Software

Services

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.

?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>

");

// 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>

Everything you ever needed to know about me can be found at Cookstour.org.

The access keys for this page are: ALT (Control on a Mac) plus:

evolt.org Evolt.org is an all-volunteer resource for web developers made up of a discussion list, a browser archive, and member-submitted articles. This article is the property of its author, please do not redistribute or use elsewhere without checking with the author.