Recursive Fibonacci sequence up to nth number in SQL

fib.sql

WITH RECURSIVE fib (a, b, n) AS (
    SELECT 0, 1, 1
  UNION ALL
    SELECT b, a+b, n+1 FROM fib
)
SELECT a FROM fib WHERE n<=8;

Eso hice con WITH RECURSIVE porque soy demasiado pendejo hacerlo bien con una función :)

Challenge!

Create a function in SQL or PL/SQL that accepts a number which represents the Nth Fibonacci number you want to output (and bonus points for all previous numbers).

Example

SELECT fib(6);

Output

fib
8

OR

Nth	Fibonacci
0	0
1	1
2	1
3	2
4	3
5	5
6	8

etc.

Alright it wasn't so hard after all in plpgsql. No bonus points for me though.

CREATE OR REPLACE FUNCTION fib(n INTEGER) RETURNS INTEGER AS $$
BEGIN
  IF (n < 2) THEN
    RETURN n;
  END IF;
  RETURN fib(n - 1) + fib(n - 2);
END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION fibLinear(n INTEGER) RETURNS INTEGER AS $$
DECLARE
  prevFib INTEGER := 0;
  fib INTEGER := 1;
BEGIN
  IF (n < 2) THEN
    RETURN n;
  END IF;

  WHILE n > 1 LOOP
    SELECT fib, prevFib + fib INTO prevFib, fib;
    n := n - 1;
  END LOOP;

  RETURN fib;
END;
$$ LANGUAGE plpgsql;

CREATE OR REPLACE FUNCTION fibFormula(n INTEGER) RETURNS INTEGER AS $$
BEGIN
  RETURN round(pow((pow(5, .5) + 1) / 2, n) / pow(5, .5));
END;
$$ LANGUAGE plpgsql;

select fib(6);

Output

 fib 
-----
   8

Wow I really need to learn plpgsql. Nevertheless, I think doing it with plpgsql misses most of the fun - which is forcing your brain to think in SQL's declarative paradigm! I know how to solve most simple algorithmic problems imperatively, and even functionally, but with declarative SQL? It's like learning to program all over again.

Plus, declarative programming can be surprisingly elegant for certain classes of problems.

Yes you are right, there is no fun in imperative functions.. I'll try to create something declarative then 😄 (based off your gists)

Current snippet causes an error

$ psql -f fib.sql 
psql:fib.sql:6: ERROR:  integer out of range

Kluged it by

WITH RECURSIVE fib (a, b, n) AS (
    SELECT 0, 1, 0
  UNION ALL
    SELECT b, a+b, n+1 FROM fib WHERE n < 45 -- Integer out of range kluge
)
SELECT n AS nth, a AS fibonacci FROM fib WHERE n<=8;

Outputs

 nth | fibonacci 
-----+-----------
   0 |         0
   1 |         1
   2 |         1
   3 |         2
   4 |         3
   5 |         5
   6 |         8
   7 |        13
   8 |        21
(9 rows)

TIL Recursion in SQL is just iteration

TIL Recursion in SQL is just iteration

Consider what 'recursion' means in old-school Von Neumann style computer science. All iteration, including recursion, is just a bunch of GOTOs. This is how assembly works to this day. All loops are just conditional JMP instructions. Recursion (in assembly) just saves your current stack pointer and then puts the stack pointer somewhere fresh, runs some code, then jumps back to where it was (and restores the old stack pointer!). So recursion in this model is just a special approach to iteration.

If this is the meaning of recursion you have in mind, then SQL recursion is basically not recursion. The values aren't being pushed onto any stack, no stack-frames are being saved or new contexts created or anything like that. So in that sense, this is just normal iteration. (on the other hand, you COULD implement SQL recursion that way - it's just that SQL has tail call optimization for all recursion by definition, so why would you?)

However, if by recursion you mean in the symbolic / mathematical way of thinking about the term as a self-referential function, and we take the liberty of considering "SELECTing a value from a table" to roughly equate to "calling a function given a value" (with the table representing the function, the value representing...the value, and SELECT to represent calling the function) then SQL style recursion is very much normal recursion.

In the sense that a function just expresses a 1:1 x->y table of values, SQL's approach is almost 'purer' than the normal f(x)=f(x) type representation of recursion. After all, a table of inputs and outputs is every bit as valid as a representation of a function as the (irl less common) algebraic notation f(x).

Fair enough, all functions drill down to some clever JMP instructions. What boggles my mind is that the "body" of the recursive CTE where the UNION ALL is iterating the result does not care about it's outer scope wanting to have just n<=8 results. I feel like the base case is missing. There is no returning of a value, it is iterating till infinity.

Don't get me wrong I'm convinced this is a recursive pattern and I enjoyed reading your comment!

Here is another implementation I made today in plpgsql, tail recursion:

CREATE OR REPLACE FUNCTION fibTailRecursive(n INTEGER, prevFib INTEGER DEFAULT 0, fib INTEGER DEFAULT 1)
RETURNS INTEGER AS $$
BEGIN
  IF (n = 0) THEN
    RETURN prevFib;
  END IF;
  RETURN fibTailRecursive(n - 1, fib, prevFib + fib);
END;
$$ LANGUAGE plpgsql;

When I was coding my solution in TablePlus it DID notice that it's outer scope only cares about n=8. That's why it ran forever for you but not for me. TablePlus is smart about that stuff. But I see what you mean, haha.

Recursion has sort of come under the dominion of functional programming, and this is a clearly non-functional approach to recursion. Do you have Hangouts? I'd love to chat more. It warms my heart to see people pursuing curiosity and intellectual gratification.