递归with真是个好东西

tree_new_bee

装上11g, 先玩一下递归with语句， 真是个好东西。
以前觉得单行SQL实现很费劲的几个问题， 现在解决起来轻松多了。



把做过的几个问题在这里归纳一下：

1. 阶乘。  2#，12#

2. 质因数分解。  我的在3#, 很笨。  请看5# newkid的版本

3. 2个数的gcd. 15#

4. 多个数的gcd.  17#

5. 多个数的lcm.  18# 简单递推版本，  23# newkid的辗转相除版本

6. 菲波纳契数列.  19#

[ 本帖最后由 tree_new_bee 于 2010-12-11 09:37 编辑 ]

tree_new_bee

1. 阶乘。

以前用connect by来实现，性能到了8，9，就已经不可接受了。 用with语句写一下， 性能很强劲！

with targ as (select 6 d from dual)
,t as (select rownum n from targ connect by level<=30)
, prod(lastnum, lastprod) as
(select min(n), min(n)  from t union all
select n, n*lastprod from t, prod where n = prod.lastnum+1
)
select * from prod where lastnum = (select max(n) from t)


   LASTNUM   LASTPROD
---------- ----------
         6        720

Executed in 0.047 seconds

SQL>

   LASTNUM   LASTPROD
---------- ----------
        30 2.65252859

Executed in 0.125 seconds

SQL>

tree_new_bee

2. 质因数分解：

初练， 感觉到写的很笨重， 不过运行的效果不错。

with t as (select 720 d from dual)
,t1 as (select rownum rn, rownum+1 n from t connect by level<d)
, fact(f_rn, f_n, f_num, canmod) as (
select 1, 2, d, sign(mod(d,2)) from t
union all
select rn, decode(canmod,0, f_n, f_n+1), decode(canmod,0, f_num/f_n, f_num),
sign(mod(decode(canmod,0, f_num/f_n, f_num), decode(canmod,0, f_n, f_n+1)))
from t1, fact where  rn = f_rn + 1  and f_num>1
)
select f_n from fact  where  canmod=0


11  /

       F_N
----------
         2
         2
         2
         2
         3
         3
         5

7 rows selected

Executed in 0.156 seconds

SQL>

tree_new_bee

先不玩了， 睡觉去。

newkid

哈哈，就知道你会喜欢，希望你玩出新意思来！

质因子分解挺有意思，我也来献丑：
WITH t(c,n,m,r) AS (
SELECT 1,2,720,1 FROM DUAL
UNION ALL
SELECT c+1
      ,CASE WHEN MOD(m,n)>0 THEN n+1 ELSE n END
      ,CASE WHEN MOD(m,n)>0 THEN m ELSE m/n END
      ,MOD(m,n)
  FROM t
WHERE c<720 AND m>1
)
SELECT n FROM t WHERE r=0;

前阵子我写了个辗转相除法求n个数的最小公倍数，你要不要来试一下？

newkid

阶乘用CONNECT BY也不差嘛，你是怎么写的？

SELECT EXP(SUM(LN(LEVEL))) FROM DUAL CONNECT BY LEVEL<=10;

EXP(SUM(LN(LEVEL)))
-------------------
            3628800

Elapsed: 00:00:00.01

你还可以试一下MODEL。

tree_new_bee

原帖由 newkid 于 2010-12-10 03:23 发表
哈哈，就知道你会喜欢，希望你玩出新意思来！

质因子分解挺有意思，我也来献丑：
WITH t(c,n,m,r) AS (
SELECT 1,2,720,1 FROM DUAL
UNION ALL
SELECT c+1
      ,CASE WHEN MOD(m,n)>0 THEN n+1 ELSE n END
      ,CASE WHEN MOD(m,n)>0 THEN m ELSE m/n END
      ,MOD(m,n)
  FROM t
WHERE c1
)
SELECT n FROM t WHERE r=0;

前阵子我写了个辗转相除法求n个数的最小公倍数，你要不要来试一下？

我就说我写的看着那么笨重， 看你写的清楚多了。


刚琢磨这个东西， 对于哪个部分要怎么递归还总要来回瞎试， 所以写到最后逻辑都混乱了。

tree_new_bee

原帖由 newkid 于 2010-12-10 03:26 发表
阶乘用CONNECT BY也不差嘛，你是怎么写的？

SELECT EXP(SUM(LN(LEVEL))) FROM DUAL CONNECT BY LEVEL

这个powr+log的我知道。
我说的是以前提到过的那个sys_connect_by_path后数数的方式。

[ 本帖最后由 tree_new_bee 于 2010-12-10 08:24 编辑 ]

tree_new_bee

另外，请教一下啊newkid:
with子查询，在文档中称为subquery factoring clause
这里的 factoring 翻译成中文怎么说？

newkid

我把它称为“分解子查询”，自己杜撰的翻译。