Monday, October 04, 2004

Recursion Alternative; or Non-Recursive Recursion

I learned a really neat trick today, (thanks again Karl) -- which I'll intentionally missname "non-recursive recursion".

I've used classic recursion (a funtion that calls itself until some condition is met) in the past to traverse up and down parent-child relationships. Recursion is especially nice when you don't know at the beginning how many decendants or progenators there will end up being at the end. The classic example is something like this: return all decendants of a given category where each category has x number of children (and x can be greater than or equal to zero).

I asked Karl about recursion in C# this morning, and he basically confirmed to me that it works the same way as I have been used to in ColdFusion, then with a smirk -- he offered an alternative. An alternative? There's an alternative to recursion? I was quite eager.

Here's how it works: a for loop is set up that loops over the contents of an ArrayList. Inside the loop you add to the ArrayList the child elements of the parent in the current iteration of the loop. If a child is found (and subsequently added to the ArrayList), then the ArrayList grows by x number of children elements. Now here's the rub:

The exit test on the for loop is always testing to see if the index is less than the count of the ArrayList.

As long as at least one child is found, the index will never be as great as the count of the ArrayList, and the loop continues. Beautifull!

In other words... if a child is found, this of course means the for loop will execute at least one more time, which itself returns the immediate children of the new parent (the current itteration of the loop)... et cetera, et cetera, until there are no children and the index of the for loop finally catches up with the count of the ArrayList, and the for loop exit condition is met.

So simple. So elegant. So.. je ne sais quoi!

No comments: