Search code examples
sqlrecursionexecution

Base condition in recursive query using CTE?

WITH CTE 
AS(
SELECT ID,Name,ManagerID, 1 RecursiveCallNumber FROM Employee WHERE ID=2
UNION ALL
SELECT  E.ID,E.Name,E.ManagerID,RecursiveCallNumber+1 RecursiveCallNumber FROM Employee E
INNER JOIN CTE ON E.ManagerID=CTE.ID
)
SELECT * FROM CTE

How does the above code work logically? Here is my explanation:

  1. Execute the the first select statement. [Now the temporary table is known as CTE]

  2. Execute the next select statement and join with the above result. We join with a condition that reduces the steps/loops in recursion which in this case is Manager. [Now the entire thing is known as CTE]

What is the base condition here? If there no results in the join, then its a base condition? Wouldn't that break if we had a 0th IDN record forming a circular reference?

https://technet.microsoft.com/en-us/library/ms186243(v=sql.105).aspx is a good resource.

Solution

  • Recursive definitions in SQL Server with CTE are different from recursive definitions in many other programming languages (such as functional, imperative, and logical languages) in that the "base condition" is what starts, not ends, the recursion.

    In the recursion familiar to most programmers you start by asking what you want to know (say, "what's the factorial of five?"), then your recursive program gradually reduces the request to something simple, gets to the base case ("what's the factorial of one?"), and builds up your solution as it "unwinds" the recursive chain of invocations ("factorial of three is three times the factorial of two, factorial of four is four times the factorial of three, and so on").

    Here, you start with a "seed data", and proceed by expanding the seed set for as long as you can discover more things to add to it. Once there's nothing else to add, you stop, and return the results.

    In a sense, this is very similar to breadth-first search implementation that uses a queue: you add the initial element to the queue, and then your loop takes items from the queue, and enqueues its related items. The loop stops once there is nothing more to add.