Fibonacci in PostgreSQL

Posted by Daniel Lyons on August 12, 2009

I should have brought this up in the previous post. The question on everyone's mind must be, if SQL has recursion, how do you compute the Fibonacci sequence? Here's how:

        SELECT fib FROM
        (WITH RECURSIVE fibonacci(fib, fib1) AS (
          SELECT 1, 0
          UNION
          SELECT 1 :: NUMERIC, 1 :: NUMERIC
          UNION
          SELECT fib + fib1, fib FROM fibonacci
        )
        SELECT * FROM fibonacci) AS fibs LIMIT 1000;

I couldn't see a way to refer to the previous two rows, so instead I just carry along the previous row's value inside the current row, so the next calculation can see the previous two values. I wrapped the whole thing in a SELECT to hide fib1. The NUMERIC type gives you arbitrary-precision math (or at least to 1000 decimals). Without it, the maximum number you can calculate is 46 because 1134903170 + 1836311903 overflows the normal integer.