Home > Articles > Data > SQL Server

SQL Server Reference Guide

Hosted by

Toggle Open Guide Table of ContentsGuide Contents

Close Table of ContentsGuide Contents

Close Table of Contents

Design Elements Part 13: Recursion

Last updated Mar 28, 2003.

All major programming languages, including Transact-SQL, have the concepts of code formatting, scope, error handling, variables, math and statistical functions, and loops. Let's add one more fundamental programming concept to your arsenal.

One of the most powerful tools in programming is recursion. Recursion is similar to a loop, with has one major difference. A loop sets up a condition and then executes a block of code until the condition is met. In contrast, recursion calls itself a number of times, using answers that it provides as an input. Let's examine that a bit further.

By now, you know that the loop construct in T-SQL uses the WHERE clause. A simple loop looks like this:

DECLARE @x INT
SET @x = 1
WHILE @x < 11
	BEGIN
		SELECT @x
		SET @x = @x + 1
	END
PRINT 'All Done'

Once the condition is set, the system "loops" through the code until it is met. There are no outputs required except the final answer.

Recursion is a bit different. A recursive process also loops until a condition is met, but the process returns an answer at each phase of the process, and then calls itself again using that answer as an input.

A useful example when discussing recursion is a mathematical factorial.

A factorial number is the product of a number's products. What that means is that "4 factorial" — 4 * 3 * 2 * 1 — would look like this:

4 * 3 = 12
12 * 2 = 24

So 4 factorial, which is written as 4!, is 24. See the progression of 3 (4-1) and the 2 (3-1) in there?

NOTE

It's very common to use factorials to illustrate recursion. But don't let that freeze your notions about factorials. Recursion is just one way to solve a factorial. Among the other methods are Moessner Factorial, Naive Product, Recursive Product, Boiten Split, Recursive Split, Hyper Simple, Hyper Double, Swing Simple, Swing Double, Swing Rational, Swing Rational, Prime Factorization and Repeated Squaring, Prime Factorization and Nested Squaring, and Swing Factorization, to name just a few!

The reason factorials lend themselves so well to the discussion of recursion is that the algebraic formula (as you might have guessed from the numbers above) to compute a factorial is:

N! = N ( N – 1 )

Whenever we see that famous "N" variable repeating itself through iteration, the algorithm we're looking for is most likely a recursive one. That formula shows us where the 3 and the 2 used in the 4! example came from.

To compute the factorial algorithm using recursion we need something that calls itself N times, decrementing by one each time, and multiplying itself by that number.

To see recursion in action, let's create a User Defined Function (UDF) to create a Factorial algorithm. (To learn more about functions, check out my previous article here at InformIT.) We'll break this function down line by line to show how it works. We'll use line numbers this time to illustrate, but be sure to take them out to run the code!

1. CREATE FUNCTION dbo.Factorial(@x int )
2. RETURNS INT
3. AS
4. BEGIN
5. DECLARE @i int
6. 	IF @x <= 1
7. 		SET @i = 1
8. 	ELSE
9. 		SET @i = @x * dbo.Factorial( @x - 1 )
10. RETURN (@i)
11. END

In the first line, we've prefaced the function as required with the owner name. This function accepts one input, an integer value.

On the second line we see why we've used a User Defined Function. UDFs can return a value to the calling program. In the case of recursion, the calling program is the function itself. We'll use that feature to complete the first multiplication, and then feed the product back into itself.

The fifth line sets up the feedback value for the whole process. It provides the the value that we need for the next pass.

We've handled the 0 problem in the sixth and seventh lines. Curiously enough, the factorial of 0 (or 0!) is 1, so we handle that separately here. This line also serves as the exit condition for the function.

The ninth line is the primary algorithm. Looking closely we can see the n! = n(n-1) there. The n! part is the i we're working with at that moment. The x is multiplied by a number that this very program provides! To see this in action, let's run the function:

SELECT dbo.factorial(4)

Here's what happened, blow by blow:

  • The function was called and passed the value 4.

  • The function checked to see if the passed value was 1 or 0. It wasn't.

  • The variable @i was set to 4 multiplied by the function with an input of 4 (the original @x) minus 1, which is three. i = 4 ( 4-1). That answer was twelve.

This caused the function to be called again, this time with an input of 12. Steps 1 through 3 were processed again, each time decreasing the first input by 1. This means that 12 was fed back into the function, and this time multiplied by 2 (which is 24). When the decrement went to one the check at line two stopped the process, and the number 24 was returned.

While you might not run into factorials very often, they are useful for understanding recursion. The key things to remember about recursion are how it is both like and unlike a loop. It's important to know when to choose each. The rule of thumb is this: to use a product of an algorithm as its own input, pick recursion. To repeat a block of code a certain number of times, use a loop.

Online Resources

One of the neatest algorithms around showing recursion in Java can be found here. A Java applet walks through this same sort of formula. If you have any confusion in reading this article, set the speed to "slow" on that applet and it will help you understand how the algorithm works. This is way cool!

Recursion often leads to a discussion of handling a "tree" hierarchy. While I normally do this in another programming language, you can do it in T-SQL. There's a great article over at the SQL-Team's Web site that shows you how.

InformIT Tutorials and Sample Chapters

Recursion is used everywhere. Here's an example by Sriranga Veeraraghavan on using recursion in UNIX shell scripts.