Recursion

from the Artful SQL Server & Access Tips List

As I see it, recursion is one of the most elegant programming constructs. 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:

1. Given the demand for one instance of an object, produce the Bill of Materials required to build it.

2. Given specific inventory levels of the constituent objects that comprise an object, how many objects of this kind can we build?

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.
Return to the Artful SQL Server & Access tips page