TechRepublic's free SQL Server newsletter, delivered each Tuesday, contains hands-on tips that will help you become more adept with this powerful relational database management system. Automatically subscribe today!
Recursion is one of the most elegant programming constructs in my opinion. I have used it in dozens of situations and in several programming languages. The basic concept of recursion is straightforward: a given chunk of code calls itself until some boundary condition is reached. I'll demonstrate you how to use recursion in T-SQL, using one of the classic examples of recursion: the factorial calculation.
A factorial is the multiple of any number by all the lesser numbers down to two. For example, factorial(10) is equal to 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2. (You could add * 1, but why bother?)
The following script implements the factorial algorithm:
CREATE PROCEDURE [dbo].[Factorial_ap]
@RetVal Integer OUTPUT
DECLARE @In Integer
DECLARE @Out Integer
IF @Number != 1
SELECT @In = @Number – 1
EXEC Factorial_ap @In, @Out OUTPUT
SELECT @RetVal = @Number * @Out
SELECT @RetVal = 1
Assuming that you want to calculate factorial(n), the procedure will call itself (n-2) times. SQL Server permits recursion to a depth of 32 calls, but at 13, you'll suffer arithmetic overflow. If you expect to be calculating factorials for large numbers, then you should declare the variable as BigInt rather than Integer. This will allow you to calculate factorial(20), which incidentally is 2,432,902,008,176,640,000. The results increase in size so quickly that factorial(21) breaks this implementation as well.
As pretty as the factorial algorithm is, it's unlikely that you'll have much use for it in your everyday programming. Nevertheless, it concisely illustrates the principle of recursion.
Practical applications of recursion
There are many practical situations in which recursion can be a valuable technique—among them is the classic programming problem called Bill of Materials. This problem has at least two different applications, which include:
- Given the demand for one instance of an object, produce the Bill of Materials required to build it.
- Given specific inventory levels of the constituent objects that comprise an object, how many objects of this kind can we build?
Let's assume that we have an object O, which consists of four objects X, three objects Y, and seven objects Z. Therefore, to build a single object O it's obvious that we require four objects X, three objects Y, and seven objects Z. Suppose, however, that objects Y and Z both require a certain number of object Q (e.g., screws of a specified girth, thread pattern, and head pattern). Then we have to visit objects Y and Z, determine the number of Qs they require, and see if we have that sum in stock. If not, we cannot build object O.
SQL Server 2000 does not make solving this problem easy unless you know beforehand the level of recursion. However, SQL 2005 beta goes a long way to solve this problem. SQL guru Joe Celko offers a rather clever solution to this problem, which involves tracking the levels at row-insert time. His solution works well, but requires triggers or equivalent mechanisms that update depth-level columns with every insert, update, or delete. View an example of his method, implemented in Access. You can easily port this solution to SQL Server and then modify it to suit your requirements.
I will revisit this topic soon to illustrate the dramatic advances introduced in SQL Server 2005. Stay tuned.