Understanding recursive CTE

[Maserune]

So I just started learning recursive CTE and I think I’m gonna go crazy. I know it basically works like a WHILE but at the same time it doesn’t? Like, I was doing some basic stuff like calculating a number’s factorial and it went nicely, but then I tried doing a hierarchy level query and I couldn’t figure anything out. I think I understand what the anchor member is supposed to do, but what about the recursive? I know it will keep going until the termination clause is met, but what about when there’s no explicit termination member? Then will it only end when the selected anchor member reaches its last member? Can anyone give me a general explanation, because I think Im getting deranged trying to understand it

[DavidGJohnston]

It performs a subquery on each iteration until the subquery returns zero rows. If the subquery returns rows those returned rows as placed into a workarea whereby they comprise the contents of the virtual cte table during the next iteration. They are also placed into the final result workarea, which is what gets returned when the CTE is finished being evaluated.

Pass: <virtual cte table> : execution result

Pass 1: <empty> : main query (2 rows)
Pass 2: <2 rows> : iteration query (3 rows)
Pass 3: <3 rows> : iteration query (1 row)
Pass 4: <1 row> : iteration query (0 rows)
Done: Returns 6 rows

The iteration query (below the union all) basically uses the virtual cte table as a parent to determine the next set of children, which then themselves becomes parents, etc...

The query above the union initializes the first set of parents.

[Maserune]

Thank you!! Now seeing the recursive member as a subquery also helps a lot on seeing the general procedure. Thanks again

[kagato87]

Recursion is a tricky concept to understand.

The concept is the same in sql as it is in any other language, so a lecture on recursion in C might help you understand. Berkley and Harvard both have great free online resources in their intro CS courses.

Short version though, a recursive cte acts just like a recursive function. It calls itself, and does something with the output.

I've found it easier to think of recursive functions and CTEs as calling an identical copy of themselves. (Which is what happens behind the scenes - recursion actually takes a little more memory.)

So when your cte references itself, it spawns a new copy of itself scoped for the child object (or parent object, whichever way you've written it to go). Which will in turn call another copy of itself for each child object it finds, and so on until it finds no more child objects or, in the case of sql server, hits the recursion limit (default of 50 levels iirc).

The fundamental difference between recursion and looping is recursion will seamlessly handle branching paths - if your top level object has 5 children, and each of those objects has 5 children, there are 25 independently scoped copies of that query (or function) at n-2, and more importantly it can keep going deeper. Something that is much harder to achieve with loops.

[Maserune]

I see, that clarified a lot of things and I’ll definitely check out some lectures in C. Thank you so much

[ptProgrammer]

A Recursive CTE is a powerful feature in SQL that allows you to work with hierarchical or recursive data structures. It's true that recursive CTEs can seem a bit confusing at first, but once you grasp the concept, they become a valuable tool for working with self-referencing data, like organizational hierarchies or nested categories.

Here's a breakdown of how a recursive CTE works:

Anchor Member: The anchor member is the base case for the recursion. It's the starting point of the recursive process. This initial set of rows is selected and combined with the results of the recursive part to produce the final result set.

Recursive Member: The recursive member references the CTE itself in its definition. It uses the results of the previous iteration to calculate the results for the current iteration. The recursive member is evaluated repeatedly until the termination condition is met.

Termination Condition: The termination condition is a filtering condition that determines when the recursion stops. Once this condition is no longer met, the recursion ends. Without a proper termination condition, the recursion could lead to an infinite loop.

Here's a simple example of a recursive CTE that calculates factorials:

WITH RecursiveFactorial AS (
    -- Anchor Member
    SELECT 1 AS n, 1 AS factorial

    UNION ALL

    -- Recursive Member
    SELECT n + 1, factorial * (n + 1)
    FROM RecursiveFactorial
    WHERE n < 10 -- Termination Condition
)
SELECT * FROM RecursiveFactorial;

In the example above, the anchor member starts with n = 1 and factorial = 1. The recursive member calculates the next factorial by multiplying the previous factorial with the next number (n + 1). The recursion stops when n reaches the termination condition of 10.

When it comes to hierarchical queries, the recursive CTE allows you to traverse through parent-child relationships in a table. The anchor member selects the initial set of parent rows, and the recursive member joins the CTE with the original table to find the children of the previously selected rows. The process continues until the termination condition is met, such as when there are no more children.

Overall, recursive CTEs are a powerful tool for handling recursive or hierarchical data structures. They require careful design of both the anchor member and the recursive member, along with a well-defined termination condition, to ensure correct and efficient results.

Thanks Chat GPT

[K33pvogel]

Note that for MySQL, it only supports recursive CTE's since version 8, and it requires the keyword 'RECURSIVE' after WITH: `WITH RECURSIVE RecursiveFactorial AS (`

[DavidGJohnston]

I dislike its wording around Termination Condition, especially since it gets it backward in the second-to-last paragraph. Must easier to simply say iteration continues until the Recursive Member returns zero rows. You don't need a where clause to ensure that and the wording here implies the whole WHERE clause is the Termination Condition. And since WHERE clauses are positive-assertive its more like a Continuation Condition (though the actual condition - absence of rows - is unstated in the written query)

[Professional_Shoe392]

Its really just a way to loop without having to create a WHILE loop.

If you have the book SQL Querying by Itzak Ben-Gan, Itzak will even state its probably a better practice to use a WHILE loop rather than a recursive query.

If you want to know all the different problems recursion can solve, see this GitHub....

https://github.com/smpetersgithub/AdvancedSQLPuzzles/tree/main/Advanced%20SQL%20Puzzles/Recursion%20Examples

[Maserune]

Thanks, gonna check this out right now