- Table of Contents
- Microsoft SQL Server Defined
- Microsoft SQL Server Features
- Microsoft SQL Server Administration
- Microsoft SQL Server Programming
- An Outline for Development
- Database Services
- Database Objects: Databases
- Database Objects: Tables
- Database Objects: Table Relationships
- Database Objects: Keys
- Database Objects: Constraints
- Database Objects: Data Types
- Database Objects: Views
- Database Objects: Stored Procedures
- Database Objects: Indexes
- Database Objects: User Defined Functions
- Database Objects: Triggers
- Database Design: Requirements, Entities, and Attributes
- Business Process Model Notation (BPMN) and the Data Professional
- Business Questions for Database Design, Part One
- Business Questions for Database Design, Part Two
- Database Design: Finalizing Requirements and Defining Relationships
- Database Design: Creating an Entity Relationship Diagram
- Database Design: The Logical ERD
- Database Design: Adjusting The Model
- Database Design: Normalizing the Model
- Creating The Physical Model
- Database Design: Changing Attributes to Columns
- Database Design: Creating The Physical Database
- Database Design Example: Curriculum Vitae
- The SQL Server Sample Databases
- The SQL Server Sample Databases: pubs
- The SQL Server Sample Databases: NorthWind
- The SQL Server Sample Databases: AdventureWorks
- The SQL Server Sample Databases: Adventureworks Derivatives
- UniversalDB: The Demo and Testing Database, Part 1
- UniversalDB: The Demo and Testing Database, Part 2
- UniversalDB: The Demo and Testing Database, Part 3
- UniversalDB: The Demo and Testing Database, Part 4
- Getting Started with Transact-SQL
- Transact-SQL: Data Definition Language (DDL) Basics
- Transact-SQL: Limiting Results
- Transact-SQL: More Operators
- Transact-SQL: Ordering and Aggregating Data
- Transact-SQL: Subqueries
- Transact-SQL: Joins
- Transact-SQL: Complex Joins - Building a View with Multiple JOINs
- Transact-SQL: Inserts, Updates, and Deletes
- An Introduction to the CLR in SQL Server 2005
- Design Elements Part 1: Programming Flow Overview, Code Format and Commenting your Code
- Design Elements Part 2: Controlling SQL's Scope
- Design Elements Part 3: Error Handling
- Design Elements Part 4: Variables
- Design Elements Part 5: Where Does The Code Live?
- Design Elements Part 6: Math Operators and Functions
- Design Elements Part 7: Statistical Functions
- Design Elements Part 8: Summarization Statistical Algorithms
- Design Elements Part 9:Representing Data with Statistical Algorithms
- Design Elements Part 10: Interpreting the Data—Regression
- Design Elements Part 11: String Manipulation
- Design Elements Part 12: Loops
- Design Elements Part 13: Recursion
- Design Elements Part 14: Arrays
- Design Elements Part 15: Event-Driven Programming Vs. Scheduled Processes
- Design Elements Part 16: Event-Driven Programming
- Design Elements Part 17: Program Flow
- Forming Queries Part 1: Design
- Forming Queries Part 2: Query Basics
- Forming Queries Part 3: Query Optimization
- Forming Queries Part 4: SET Options
- Forming Queries Part 5: Table Optimization Hints
- Using SQL Server Templates
- Transact-SQL Unit Testing
- Index Tuning Wizard
- Unicode and SQL Server
- SQL Server Development Tools
- The SQL Server Transact-SQL Debugger
- The Transact-SQL Debugger, Part 2
- Basic Troubleshooting for Transact-SQL Code
- An Introduction to Spatial Data in SQL Server 2008
- Performance Tuning
- Practical Applications
- Professional Development
- Application Architecture Assessments
- Business Intelligence
- Tips and Troubleshooting
- Additional Resources
Design Elements Part 13: Recursion
Last updated Jul 9, 2004.
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?
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:
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.
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.