Is Recursion Interesting to Anyone?
Date: Fri, 9 Jul 2010 14:17:53 -0700 (PDT)
Message-ID: <16381c0c-d0af-4fa2-850e-74b673f6d9e4_at_d37g2000yqm.googlegroups.com>
In our installation of DB2 I don't have access to a dummy table, but DB2 does have VALUES.
This got me to looking into converting some of my old work for other db's routines for generating sequences & results using iteration & recursion.
Thought I'd share at my own peril, :)
Here are a few worked examples that are best viewed in monospace font.
--jim
counting numbers (plus zero) - not recursive
uncomment lines and adjust the final FROM statement to get 10x the previous result
WITH
T1 as ( select * from (values 0,1,2,3,4,5,6,7,8,9) as T(n) ) ,T2 as ( select * from ( select 10*i1.n+i2.n from T1 i1,T1 i2 ) as T(n) )
,T3 as ( select * from ( select 10*i1.n+i2.n from T2 i1,T1 i2 ) as T(n) )
- ,T4 as ( select * from ( select 10*i1.n+i2.n from T3 i1,T1 i2 ) as T(n) )
- ,T5 as ( select * from ( select 10*i1.n+i2.n from T4 i1,T1 i2 ) as T(n) )
- ,T6 as ( select * from ( select 10*i1.n+i2.n from T5 i1,T1 i2 ) as T(n) )
- ,T7 as ( select * from ( select 10*i1.n+i2.n from T6 i1,T1 i2 )
as T(n) )
select * from T3;
integer ranges via recursion
Note intPrm holds the parameters for the range
with
intPrm as ( select * from ( values (-3,19) ) prm(min,max) ) , ints(num) as (
select * from (select min from intPrm) t(n)
union all
select num+1 from ints
where num < (select max from intPrm)
)
select * from ints;
arithmetic series via recursion
with
intPrm as ( select * from ( values (-3,19,3) ) prm(min,max,inc) ) , integers(n) as (
select * from (select min from intPrm) t(n) union all
select n+(select inc from intPrm) from integers where n+(select inc from intPrm) <= (select max from intPrm) )
select n from integers;
factorial via recursion
not very useful--note overflow using max>12
WITH
intPrm AS ( select * from ( VALUES (1,12,1) ) prm(min,max,inc) ) , factorial(n,f) AS (
SELECT n,1 FROM (SELECT MIN FROM intPrm) t(n) UNION ALL
SELECT n+1,f*(n+1) FROM factorial
WHERE n < (SELECT max FROM intPrm)
)
SELECT * FROM factorial;
fibonacci sequence
WITH
intPrm AS ( select * from ( VALUES (0,10,1) ) prm(min,max,inc) ) , factorial(n,f0,fib) AS (
SELECT n,0,1 FROM (SELECT MIN FROM intPrm) t(n) UNION ALL
SELECT n+1,fib,f0+fib FROM factorial
WHERE n < (SELECT max FROM intPrm)
)
SELECT n,fib FROM factorial;
combinations nCr via recursion
WITH combPrm AS ( select * from ( VALUES (10,3) ) t(n,r) ) , intPrm AS ( select * from ( VALUES (1,(select n from combPrm),1) ) t(min,max,inc) )
, factorial(n,f) AS (
SELECT n,1 FROM (SELECT MIN FROM intPrm) t(n) UNION ALL
SELECT n+1,f*(n+1) FROM factorial
WHERE n < (SELECT max FROM intPrm)
)
,dummy as (select * from (values 1) as t(n)) SELECT (select f from factorial where n=(select n from combPrm))/
(select f from factorial where n=((select n from combPrm)-(select r from combPrm)))/
(select f from factorial where n=(select r from combPrm)) FROM dummy;
Euclidean Algorithm, GCD, & LCM via recursion
function gcd(a, b)
if b = 0
return a
else
return gcd(b, a mod b)
gcd(1071,462) = 21
1071 = 2 × 462 + 147 462 = 3 × 147 + 21 147 = 7 × 21 + 0
**************************************************
WITH
intPrm AS ( select * from ( VALUES (0,1071,462) ) prm(step,a,b) )
, Euclidean(n,a,b) AS (
SELECT n,a,b FROM intPrm t(n,a,b)
UNION ALL
SELECT n+1,b,MOD(a,b) FROM Euclidean
WHERE b > 0
)
, GCD(n) AS ( SELECT min(a) FROM Euclidean)
, LCM(n) AS ( SELECT min(a)*(select b from intPrm) FROM Euclidean)
select * from Euclidean;
-- select n from LCM;
-- select n from GCD;
Received on Fri Jul 09 2010 - 23:17:53 CEST