Factorial in Oracle SQL – using both new Recursive Subquery and classic Connect By approach

5

I regularly teach a masterclass on Oracle SQL. One of the topics I explore in depth is the use of the CONNECT BY query style to perform not just hierarchical queries but also networking or even generic recursive SQL. In Oracle Database 11g, the recursive subquery was formally introduced, the SQL Standard’s approach to this style of querying. The Recursive Subquery even stronger suggest recursive operations to be performed of course, but classic connect by can do that job as well.

One archetypical example of a recursive operation is the calculation of a factorial: n! = 1* 2 * 3 *…. * (n-1) * n.

In this short post I will show both the new, straightforward 11g based solution as well as the classic approach with CONNECT BY – that may not looks as recursive, but still very much is.

The 11g Recursive Subquery Factoring will have you quickly create the query to calculate factorials:

Image

The first subquery is used to inject the operand into the query. Here we are going to calculate the factorial of 5. The recursive subquery is called factorial. It will return f (operand) and outcome (factorial for operand). The first iteration is for f == 0 with outcome 1. The factorial for the next operand value is calculated taking the previous outcome and multiplying it with the operand. This recursive calculation is done in the second part of the factorial subquery – the one that refers to ‘itself’. The iterations are performed for as long as the operand value is smaller than the required value in params.

The result of this query is:

Image

with params as
( select 5 p
  from   dual
)
, Factorial (f, outcome) as
( select 0 f
  ,      1 outcome
  from   dual
  union all
  select f+1
  ,      outcome * (f+1) outcome
  from   Factorial
         join
         params
         on (f < p)
)
select *
from   Factorial
       join
       params
       on (f = p)

Now the classic CONNECT BY approach. It is really not very different at heart, even though it looks quite different:

Image

The params subquery is the same as before. The factors subquery traverses the values 1..params.p, in this case 1 through 5. For each value, the path string is composed as (*1*2*…*(n-1)*n).

The final trick in the last query is to use the xmlquery operation to evaluate the string (minus the first *) and calculate the factorial outcome.

The result:

Image

with params as
( select 5 p
  from   dual
)
, factors as
( select level f
  ,      sys_connect_by_path( level ,'*') path
  from   params
  connect by level <= p
)
select f
,      xmlcast( xmlquery( substr(path, 2)  returning content ) as number(4)) result
from   factors
Share.

About Author

Lucas Jellema, active in IT (and with Oracle) since 1994. Oracle ACE Director for Fusion Middleware. Consultant, trainer and instructor on diverse areas including Oracle Database (SQL & PLSQL), Service Oriented Architecture, BPM, ADF, Java in various shapes and forms and many other things. Author of the Oracle Press book: Oracle SOA Suite 11g Handbook. Frequent presenter on conferences such as JavaOne, Oracle OpenWorld, ODTUG Kaleidoscope, Devoxx and OBUG. Presenter for Oracle University Celebrity specials.

5 Comments

  1. indeed the logarythm of the product is the sum of the logarythms. 
    And exp(ln(x))=x 
    Then exp(ln(x1*x2*x3))=exp(ln(x1)+ln(x2)+ln(x3))=exp(sum(ln(x)))

    I have not been to conferences for a while. But next time you come to Switzerland drop me a line :-)

  2. Laurent often comes up with neat tricks like this :)
    I had to look this up, and I found a layman’s explanation in http://en.wikipedia.org/wiki/Natural_logarithm
    ln(xy) = ln(x) + ln(y)
    So Laurent is actually multiplying the logarithms of 1, 2, 3, etc. by adding them. Then the exponent is just the logarithm in reverse to get back the real value he wants.

  3. Hi Laurent,

    Thanks – that one works as well. Although I am not sure why exp(sum(ln( n))) gives the factorial. I suppose the Maths behind this is beyond me. I just was looking for a demonstration of recursive-ness…

    How are you doing by the way? Will I meet you again one of these days on a conference somewhere?

    Lucas

  4. alternatively :

    <code>
    SQL> select rownum,exp(sum(ln(rownum)) over (order by rownum)) from dual connect by level<10;
        ROWNUM EXP(SUM(LN(ROWNUM))OVER(ORDERBYROWNUM))
    ———- —————————————
             1                                       1
             2                                       2
             3                                       6
             4                                      24
             5                                     120
             6                                     720
             7                                    5040
             8                                   40320
             9                                  362880
    </code>

  5. Hi Lucas, it is nice to see that you actually programmed the factorial in SQL. I use a PL/SQL function to do the same thing and saw that a lot of the examples on the internet don’t correct for the factorial of zero to be one. When I used the factorial to program the Erlang-C formula in PL/SQL I found out that the factorial is not part of standard SQL. I think it might be a nice enhancement for Oracle SQL to make the factorial standard SQL.
    Regards, Gerwin

Leave a Reply