Recursive SQL queries

Recursion

Recursion is the technique in which a function calls itself from within its own body.
You can find out more about what is recursion and see some examples in various programming languages, a good resource is this one.

Common Table Expression

It is possible to achieve a recursion within a SQL query.
This is possible with the help of a CTE (common table expression). CTEs are representing a temporary named result set, generated by a query and defined within the execution scope of a SELECT, INSERT, UPDATE, DELETE or MERGE statement.

What that means is that if we want to have a temporary data-set structure, and we aim to use it just once directly after it is created, then the CTE is our best friend.

Furthermore, we are going to use it for the creation of a recursion.

Example

Let’s visualize the technique with a concrete example.

We are going to implement a Fibonacci sequence with a recursive SQL query by using self-called CTE and return to the user the n-th number from the sequence. Sounds cool, right? OK, let’s jump in it.

A refresher for those who have forgotten what are the Fibonacci numbers – the sequence starts with the numbers 0 and then 1 and every next number is equal to the sum of the previous two. So if we want to see the sequence of the first 6 elements it looks like this:

{ 0, 1, 2, 3, 5, 8 }

And if we want to return the value of the n-th element (where n = 6 in our example), then it will be:

8

Now if we want to achieve that in SQL then we can wrap that in a function:
dbo.Fibonacci and have an input parameter that receives the length of the sequence – the count of the elements. At the end, our function will return the value of the last element.

Here is the implementation:

CREATE FUNCTION dbo.Fibonacci (@count int)
RETURNS int
WITH EXECUTE AS CALLER
AS
BEGIN
    DECLARE @result int;

    ;WITH cte_fibonacci(n, currentNum, nextNum)
	AS
	(
		SELECT		
			0, 0, 1
		UNION ALL
			SELECT n + 1, nextNum, currentNum + nextNum 
			FROM cte_fibonacci
		WHERE n < @count
	)
	SELECT @result = MAX(currentNum) 	
	FROM cte_fibonacci

	RETURN @result;
END;
GO

You can see that cte_fibonacci calls itself inside the SELECT query in its body.

Finally, let’s test our new function with the following query:

select dbo.Fibonacci(6) AS [Result]

Result
8