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]
(
@Number Integer,
@RetVal Integer OUTPUT
)
AS
DECLARE @In Integer
DECLARE @Out Integer
IF @Number != 1
BEGIN
SELECT @In = @Number – 1
EXEC Factorial_ap @In, @Out OUTPUT
SELECT @RetVal = @Number * @Out
END
ELSE
BEGIN
SELECT @RetVal = 1
END
RETURN
GO
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.
