Recursion with recursive WITH

Natalka Roshak's picture

I recently had the opportunity to talk with Tom Kyte (!), and in the course of our conversation, he really made me face up to the fact that the SQL syntax I use every day is frozen in time: I’m not making much use of the analytic functions and other syntax that Oracle has introduced since 8i.

Here’s a brief history of these additions to Oracle SQL, from Keith Laker, Oracle’s Product Manager for Analytical SQL:

8i Window functions
9i Rollup, grouping sets, cube, enhanced window functions
10g SQL Model clause, statistical functions, partition outer join
11g SQL Pivot clause, Recursive WITH, Listagg, Nth value
12c Pattern matching, Top N

Not only do these make complex queries much, much simpler and easier, they are also much faster for the same result than non-analytic SQL, as Tom Kyte has shown repeatedly on his blog and in his books.

So, I was sold and I wanted to jump in with Recursive WITH. The WITH clause lets you define inline views to use across an entire query, and the coolest thing about this is that you can define the subquery recursively – so that the inline view calls itself.

Recursive WITH basic syntax:

WITH Tablename (col1, col2, ...) AS
(SELECT A, B, C... FROM dual                   --anchor member
SELECT A', B', C'... from Tablename where...   --recursive member
select ... from Tablename where ...

Refactoring the Factorial

One fun thing about recursive WITH, aka recursive subquery refactoring, is the ease with which we can implement a recursive algorithm in SQL. Let’s warm up with a classic example of recursion: finding the factorial of a number. Factorial(n) = n! = 1*2*3*…*n . It’s a classic example because Factorial(n) can be defined recursively as:

Factorial(0) = 1
Factorial(n) = Factorial(n-1) * n

Here’s a first pass at implementing that directly in SQL to find the factorial of 5, using a recursive WITH subquery:

WITH Factorial (operand,total_so_far) AS
(SELECT 5 operand, 5 total_so_far FROM dual    -- Using anchor member to pass in "5"
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)
SELECT * FROM Factorial;

---------- ----------
         5          5
         4         20
         3         60
         2        120
         1        120

and to display just the result, we select it from Factorial:

WITH Factorial (operand,total_so_far) AS
(SELECT 5 operand, 5 total_so_far FROM dual    -- Find the factorial of 5
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)
SELECT MAX(operand) || '! = ' || MAX(total_so_far) AS RESULT FROM Factorial;

5! = 120

Ahem! I have cheated a little for simplicity here. The query doesn’t take into account that Factorial(0) = 1:

WITH Factorial (operand,total_so_far) AS
(SELECT 0 operand, 0 total_so_far FROM dual    -- Find the factorial of 0
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)                             -- This is going to get me nowhere fast...
SELECT * FROM Factorial;

---------- ----------
         0          0

To do it properly, we need to include Factorial(0) = 1 in the recursive subquery:

WITH Factorial (operand,total_so_far) AS
(SELECT 0 operand, 0 total_so_far FROM dual    -- Find the factorial of 0
SELECT operand-1, 
CASE                                           -- Factorial (0) = 1
  WHEN operand=0 THEN 1
  ELSE (total_so_far * (operand-1))
FROM Factorial
WHERE operand >= 0)
SELECT MAX(operand) || '! = ' || MAX(total_so_far) AS RESULT FROM Factorial;

0! = 1

We can also reverse direction and recursively build a table of factorials, multiplying as we go.
That’s the approach Lucas Jellema takes in his excellent blog post on factorials in SQL.

WITH Factorial (operand,output) AS
(SELECT 0 operand, 1 output FROM dual
SELECT operand+1, output * (operand+1) FROM Factorial
WHERE operand < 5)
SELECT * FROM Factorial;

---------- ----------
         0          1
         1          1
         2          2
         3          6
         4         24
         5        120

There are two nice things about this approach: first, every row of the subquery result contains n and n! , and second, the rule that 0! = 1 is elegantly captured in the anchor member.

denrael ev’ew tahw gniylppA

Now let’s do something more interesting – reversing a string. Here’s some sample code in C from the CS 211 course at Cornell:

 public String reverseString(String word) {
     if(word == null || word.equals(""))
        return word;
        return reverseString(word.substring(1, word.length())) + 

Let’s run through an example word to see how it works. For simplicity I’ll write reverseString(“word”) as r(word). Using “cat” as the word, stepping through the algorithm gives:

r(cat) = r(r(at))+c = r(r(r(t))+a+c = r(r(r(r())+t+a+c = ''+t+a+c = tac

Now to rewrite the same function in SQL. Using the same example string, “cat,” I want my recursively defined table to look like this:

in   out
at   c
t    ac

In C, the initial letter in the word is the 0th letter, and in SQL, it’s the 1st letter. So the C expression word.substring(1,N) corresponds to SQL expression substr(word,2,N-1) . With that in mind, it’s easy to rewrite the C algorithm in SQL:

WITH WordReverse (INPUT, output) AS
  (SELECT 'CAT' INPUT, NULL output FROM dual
   SELECT substr(INPUT,2,LENGTH(INPUT)-1), substr(INPUT,1,1) || output
   FROM wordReverse
SELECT * FROM wordReverse;

-------- ----
AT       C
T        AC

NOTE: if using or earlier, you might get “ORA-01489: result of string concatenation is too long” when reversing anything longer than a few letters. This is due to Bug 13876895: False ora-01489 on recursive WITH clause when concatenating columns. The bug is fixed in and, and there’s an easy workaround: Cast one of the inputs to the concatenation as a varchar2(4000).

We could make this query user-friendlier by using a sql*plus variable to hold the input string. Another approach is to add an additional subquery to the with block to “pass in” parameters. I picked this up from Lucas Jellema’s post mentioned above, and wanted to give it a try, so I’ll add it in to my WordReverse query here.

Let’s use this to reverse a word that’s really quite atrocious:

params AS
  (SELECT 'supercalifragilisticexpialidocious' phrase FROM dual),
WordReverse (inpt, outpt) AS
  (SELECT phrase inpt, CAST(NULL AS varchar2(4000)) outpt FROM params
   SELECT substr(inpt,2,LENGTH(inpt)-1), substr(inpt,1,1) || outpt
   FROM wordReverse
   WHERE LENGTH(inpt) > 0
SELECT phrase,outpt AS reversed FROM wordReverse, params
WHERE LENGTH(outpt) = LENGTH(phrase) ;

PHRASE                             REVERSED
---------------------------------- ----------------------------------------
supercalifragilisticexpialidocious suoicodilaipxecitsiligarfilacrepus

Now you might not have needed to know how to spell “supercalifragilisticexpialidocious” backwards, but one recursive requirement that does come up often is querying hierarchical data. I wrote a series of posts on hierarchical data recently, using Oracle’s CONNECT BY syntax. But recursive WITH can also be used to query hierarchical data. That’ll be the subject of my next post.

Republished with permission. Original URL: