Factorial using CTE in PostgreSQL

Not so long ago I used Common Table Expressions for Fibonacci Numbers calculation.

Today I had a conversation with one client about SQL in general and about PosgreSQL dialect in particular. We talked about SQL’s Turing completeness also. Well my opponent is sure that SQL (Postgres dialect either) is not Turing Complete. But I know for sure that if SQL supports CTE it is Turing Complete. Well, I’m sure about it because some time ago at Oscon 2009 David Fetter said so. And my confidence in this man is boundless. 🙂

Anyway, my client proposed to implement Factorial calculation on a pure SQL. I choose Postgres dialect. He agreed.

That was his first mistake! He didn’t know that Postgres has built in “!” and “!!” operators for this purpose. 🙂

But to be more convincing, I have wrote this code:

WITH RECURSIVE fact(i, f) AS (
    VALUES (2, 1)
UNION ALL
    SELECT i + 1, i * f FROM fact
)
SELECT f FROM fact LIMIT 10;
Advertisements

Fibonacci Rides Again

Not so long ago I wrote about implementing GCD function in PostgreSQL using CTE.

Here I will show how Fibonacci Numbers may be obtained using the same technique.

So to have first 16 members of this sequence we should execute something like this:

WITH RECURSIVE t(a, b) AS (
    VALUES (11)
UNION ALL
    SELECT b, a + b FROM t
)
SELECT a FROM t  LIMIT 16;

Suppose we should add this code to Wiki Library Snippets. Any objections? 😉

UPD. Some others unnatural ways to calculate Fibonacci numbers may be found in Russian.