Sean Corfield recently posted an entry about recursionin the database. This got me thinking. I once had a teacher who was adamantly against recursion for performance reasons, saying that Towers of Hanaoi was the only example where recursion was beneficial from a performance standpoint.

I have been unable to prove him wrong; can anyone else do so?

As such, I've always been cautious of recursion.

I recently spoke to a client about an application with a similar structure (to what Sean describes in his post). It was storing part information in a self-referencing table. (One part can be made to build other parts, etc.. ). It turned out that this application was a drag, because in some cases it was recursing up to 300 times to get all the data in the 'recursive tree'. This is a situation where recursion was just not working. We spoke, and I suggested this type of solution.

For simplicity, I'll use a table like this:

view plain print about
1RecurisveExample(PKID, Data, RecurseOrder)

PKID is the primary key. Data is whatever data we are storing (whether it is part numbers or cat pedigree) RecurseOrder is a text string

For each element in the table, you give it a 3-character identifier (In my example, I'll use 3 characters, but the identifier can actually be 4 or more). The RecurseOrder field contains 'Parent's identifier' + 'Current identifier'

So, to put some data in this table:
1 Root 1 001
2 Root 2 002
3 Root 3 003
4Child 1.1 001001
5 Child 1.2 001002
6 Child 1.3 001003
7 Child 1.4 001004
8 Child 2.1 002001
9 Child 2.2 002002
10 Child 2.3 002003
11 Child 2.3.1 002003001
12 Child 2.3.2 002003002
13 Child 002003002001
14 Child 002003002002
15 Child 2.2.1 002002001
16 Child 2.2.2 002002002

The root is assigned '001', '002', '003'. The children of root 1 are assigned '001001','001002', '001003'. The children of child 1 are assigned '001001001', '001001002', '001001003', and so on.

Given any root, you can get the tree in recursive order just by sorting on the recurseorder column. To get the recurseorder on root 2, for example, you can do this:

view plain print about
1select * from recursiveexample
2where recurseorder like '002%'
3order by recurseorder

To get the tree, starting at the third child of root 2, you can do this:

view plain print about
1select * from recursiveexample
2where recurseorder like '002003%'
3order by recurseorder

In some cases, such as discussion groups (where you want to retrieve a whole thread in post order) I have found this to be an elegant solution.

With a three-character identifier, you are limited to 1000 elements before you run out of thread strings. But you use a larger identifier string if you need more.