June 7, 2013 1 Comment
These queries will be using that database that was set up in a previous posting on the CTE_DEMO Sample Database, if you haven’t set up the sample database, download it and set it up now.
What is Recursion
Recursion is a concept in programming where a function calls itself. Many of the typical C programming interview questions around data structures like trees, linked lists, and other structures often times use recursion. For instance in the following T-SQL example, the scalar function Fibonacci calculates the Fibonacci sequence using recursion, by calling itself. This is accomplished by calling the function name inside of the body of the function.
CREATE FUNCTION dbo.Fibonacci (@Num integer, @prev integer, @next integer) RETURNS VARCHAR(4000) AS BEGIN DECLARE @returnValue as VARCHAR (4000) = cast(@prev as varchar(4000)); IF (@Num > 0) BEGIN IF (LEN(@returnValue) > 0) BEGIN SET @returnValue = @returnValue + ','; END SET @returnValue = @returnValue + dbo.Fibonacci(@Num - 1, @next, @next + @prev) ; END RETURN @returnValue; END GO
To call the function you simply include in a select statement, with the first parameter being the number of Fibonacci numbers to calculate, and the second and third parameters are always 0 and 1. The second and third parameters are set to 0 and 1 to prime the recursive function, and are used internally to pass the recursive call the current and previous values.
select dbo.Fibonacci(10, 0, 1);
Recursion With a CTE
Doing recursion as shown above with a function could be considered the brute force way of doing it. The common table expression way of doing recursion is much more elegant, and you can use it even if you don’t have the database permissions needed to create stored procs or functions.
Here is an example of a recursive CTE that queries a heirarchy of store departments:
use [cte_demo]; -- Recursive CTE ;WITH DepartmentCTE(id, Department, Parent, Level) AS ( SELECT id, department, parent, 0 as Level FROM Departments WHERE parent is NULL UNION ALL -- and now for the recursive part SELECT d.id, d.department, d.parent, DepartmentCTE.Level + 1 as Level FROM Departments d INNER JOIN DepartmentCTE ON DepartmentCTE.id = d.parent) SELECT * FROM DepartmentCTE ORDER BY Parent;
The first time I looked at a recursive CTE, I was just confused by the syntax. Lets walk through the different parts and it may make more sense, to start with I will add some white space to the query to split it up a bit:
The anchor query is the part of the CTE that starts the recursion. This is the part of the query that is run first that the recursive part will build from.
The UNION ALL keyword is used to separate the anchor query from the recursive part.
After the UNION ALL comes the Recursive Query
What makes the recursive part of the CTE query recursive is the way that it references itself
Executing the Recursive CTE
Once the recursive CTE has been written, it can be executed just like any other CTE, SELECT everything FROM the CTE name, in this case we are also using ORDER BY to sort the results.
With the CTE complete, lets take a look at the results.
Now lets break the results up into what was generated by the anchor and what was generated by the recursive query.
Now that you understand recursive CTE’s we can get into some really interesting recursive options over the rest of CTE month at SteveStedman.com. Stick around something new most every day.
Common Table Expressions Book
If you enjoyed this posting, and want to learn more about common table expressions, please take a look at my book on CTE’s at Amazon.com. The book is titled Common Table Expressions – Joes 2 Pros® – A CTE Tutorial on Performance, Stored Procedures, Recursion, Nesting and the use of Multiple CTEs.