Recursive CTE’s
Recursive CTEs are unique, such that they are allowed to reference their own. With this special ability, you can use recursive CTEs in solving problems where other queries cannot. Recursive CTEs are best in working with hierarchical data such as org charts for the bill of materials.
If you’re unfamiliar with CTE’s, then I highly recommend that you read the Introduction to Common Table Expressions. Once you get familiar, then you can come back to this article. We will dig deeper into the reasons why you would want to use recursive CTEs. In addition, this article comes with some great examples.
Note: All examples provided in this article are based on the Microsoft SQL Server Management Studio and the AdventureWorks2012 database. You can get started using these FREE tools with my guide, Getting Started Using SQL Server.
Introduction
A recursive CTE is a common table expression that references itself. Try to look up for the definition of recursion on Google and you’ll see that recursion is defined as “the repeated application of a recursive procedure or definition.” Its Latin root, recurrere, means to “run back.”
We will soon find out that both the modern definition and its Latin root serve well in explaining this concept.
What is recursion?
Recursion can be quite abstract and difficult to understand. Before we go further into our learning with recursive CTEs, let us first look at the example given to have a general concept.
How Many People Are in front of me in a line?
There is no doubt that you have been in a long line before and have wondered how many people were standing before you. Sort of standing on your tippy-toes and trying to count heads, is there another way to find the answer?
Sure, you could ask the person in front of you – what place they were in line. If you know this, then you could just add one to it, in order to know your place!
Using recursion to get the answer, we could use these instructions:
At first, the instructions are passed from person to person in line. Eventually, we get to the front of the line and that person has no one else to pass the instructions forward. So instead, they tell the person behind them they are “1”.
This, in turn, signals the person behind them, to add “1” to the number they were told and pass it back to the person behind them.
This repeats until the end of the line is reached. At this point, the person who was wondering how long the line just needs to add one to get the answer.
Recursion Explained Visually
Let’s see how this works visually. In the diagram below you can see where each person is forwarding the instructions to the next person in line.
At some point, we reach the first person in the line. They see there is no one in front of them and stop passing the notes. This is the terminating condition. As you can imagine, it is important to have a terminating condition. If one didn’t exist, then we would try passing the note indefinitely. In computer terms, we would be in an infinite loop.
Finally, the first person in the line gets the instructions, realizes there is no one else to pass them to. At this point, he turns around to the person behind him and says he is “1.”
The second guy gets the number “1,” adds “1” to it, and passes back “2.”
This continues on for each person until there is no one left. At this point, the last person in line now knows their position.
Note: This example is inspired by Aaron Krolik’s answers to a recursion question on Quora.
What Makes Recursion?
A recursive routine has three main parts:
- Invocation – This is the part of your query or program that calls the recursive routine.
- Recursive Invocation of the Routine – This is the part of the routine that calls itself
- Termination Check – This is the logic that makes sure we eventually stop calling the routine, and start providing answers.
Let’s take the example instructions from the above example: and identify the three parts:
- Invocation – You hand the blue card to the last person in line.
- Recursive Invocation – Each person is told to pass the direction to the person in front.
- Termination Check – You check to see if there is no one in front of you.
Recursive CTEs
A recursive CTE is a CTE that references itself. In doing so, the initial CTE is repeatedly executed, returning subsets of data, until the complete result is returned.
Being able to reference itself is a unique feature and benefit. It allows recursive CTE’s to solve queries problems that would otherwise require the use of temporary tables, cursors, and other means.
Recursive CTE’s are well suited to querying hierarchical data, such as organization charts or production bill of materials, where each product’s components are made up of subcomponents, and so on.
The general syntax for a recursive CTE is:
WITH cte_name (column1, column2, …) AS ( cte_query_definition -- Anchor member UNION ALL cte_query_definition -- Recursive member; references cte_name. ) -- Statement using the CTE SELECT * FROM cte_name
The general layout is similar to a non-recursive CTE. It is defined using WITH, consists of a query definition, and precedes the statement using the CTE.
Yet, there are significant differences. A recursive CTE must contain a UNION ALL statement and, to be recursive, have a second query definition that references the CTE itself.
Let’s look at a simple example.
Counting to 50 Using Recursion
Below is a recursive CTE that counts from 1 to 50.
WITH cte
AS (SELECT 1 AS n -- anchor member
UNION ALL
SELECT n + 1 -- recursive member
FROM cte
WHERE n < 50 -- terminator
)
SELECT n
FROM cte;
Here are the results:
Conclusion
Common table expressions come in handy when you need to simplify a query. Though some would contend that using recursive CTEs doesn’t lend to this goal, as they can be conceptually difficult to understand, they provide a means for an elegant solution.
There are many types of queries that are difficult to solve without recursive CTE’s. Querying hierarchical data is one of these. Of course, you can write looping structures to achieve the same goal, but if you don’t have the means to write and execute a stored procedure, then recursive CTE’s allow you to do so using a SELECT statement alone.
