Recursion with recursive WITH

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:

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
UNION ALL
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"
UNION ALL
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)
SELECT * FROM Factorial;

   OPERAND TOTAL_SO_F
---------- ----------
         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
UNION ALL
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)
SELECT MAX(operand) || '! = ' || MAX(total_so_far) AS RESULT FROM Factorial;

RESULT
-----------------
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
UNION ALL
SELECT operand-1, total_so_far * (operand-1) FROM Factorial
WHERE operand > 1)                             -- This is going to get me nowhere fast...
SELECT * FROM Factorial;

  OPERAND TOTAL_SO_F
---------- ----------
         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
UNION ALL
SELECT operand-1, 
CASE                                           -- Factorial (0) = 1
  WHEN operand=0 THEN 1
  ELSE (total_so_far * (operand-1))
  END
FROM Factorial
WHERE operand >= 0)
SELECT MAX(operand) || '! = ' || MAX(total_so_far) AS RESULT FROM Factorial;

RESULT
------------------------------------------------------------------------------------
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
UNION ALL
SELECT operand+1, output * (operand+1) FROM Factorial
WHERE operand < 5)
SELECT * FROM Factorial;

   OPERAND     OUTPUT
---------- ----------
         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;
     else
        return reverseString(word.substring(1, word.length())) + 
            word.substring(0,1);
  }

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
--------
cat 
at   c
t    ac
     tac

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
   UNION ALL
   SELECT substr(INPUT,2,LENGTH(INPUT)-1), substr(INPUT,1,1) || output
   FROM wordReverse
   WHERE LENGTH(INPUT) > 0
  )
SELECT * FROM wordReverse;

INPUT    OUTP
-------- ----
CAT
AT       C
T        AC
         TAC

NOTE: if using 11.2.0.3 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 11.2.0.4 and 12.1.0.1, 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:

WITH
params AS
  (SELECT 'supercalifragilisticexpialidocious' phrase FROM dual),
WordReverse (inpt, outpt) AS
  (SELECT phrase inpt, CAST(NULL AS varchar2(4000)) outpt FROM params
   UNION ALL
   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.